Coding Interview Patterns

BONUS PDF

Alex Xu | Shaun Gunawardane

Contents

Two Pointers........................................................................................................................4

Shift Zeros to the End................................................................................................................................................. 4

Next Lexicographical Sequence..............................................................................................................................9

Hash Maps and Sets........................................................................................................16

Longest Chain of Consecutive Numbers.......................................................................................................... 16

Geometric Sequence Triplets................................................................................................................................20

Linked Lists........................................................................................................................27

Palindromic Linked List............................................................................................................................................27

Flatten a Multi-Level Linked List..........................................................................................................................31

Fast and Slow Pointers.................................................................................................. 36

Happy Number Time Complexity Analysis......................................................................................................36

Binary Search................................................................................................................... 39

Find the Median From Two Sorted Arrays.......................................................................................................39

Matrix Search.............................................................................................................................................................. 46

Local Maxima in Array..............................................................................................................................................52

Weighted Random Selection.................................................................................................................................58

Stacks..................................................................................................................................65

Repeated Removal of Adjacent Duplicates.....................................................................................................65

Implement a Queue Using Stacks........................................................................................................................68

Maximums of Sliding Window.............................................................................................................................. 74

Heaps.................................................................................................................................. 81

Sort a K-Sorted Array...............................................................................................................................................81

Trees.................................................................................................................................... 88

Binary Tree Symmetry............................................................................................................................................. 88

Binary Tree Columns................................................................................................................................................ 92

Kth Smallest Number in a Binary Search Tree................................................................................................97

Serialize and Deserialize a Binary Tree.......................................................................................................... 102

Graphs.............................................................................................................................. 109

Shortest Path............................................................................................................................................................ 109

Connect the Dots.................................................................................................................................................... 117

Backtracking.................................................................................................................. 124

Combinations of a Sum......................................................................................................................................... 124

Phone Keypad Combinations.............................................................................................................................129

Dynamic Programming...............................................................................................133

Largest Square in a Matrix...................................................................................................................................133

Sort and Search............................................................................................................. 141

Dutch National Flag............................................................................................................................................... 141

Math and Geometry.................................................................................................... 146

The Josephus Problem........................................................................................................146

Triangle Numbers....................................................................................................................................................150