Coding Interview Patterns

what is the sliding window used for and how does it work?

performing a required operation on a specific window size of a given array or linked list

how does sliding window work?

start at the first element, keep shifting right by one element, and either shrink/maintain/increase window size

when should you use sliding window?

1. when the problem structure is a linear data structure, like a linked list, array, or string

2. when you’re asked to find the longest/shortest substring, subarray, or a desired value

what is the two pointer approach?

when two pointers iterate through a data structure in tandem until one or both pointers meet a certain condition

when should you use two pointer approach?

1. when looking for a set of elements that satisfy a constraint in a linked list or sorted array

2. when the set of elements in the array is a pair, triplet, or subarray

what is the fast and slow pointer approach?

using two pointers that move through an array/linked list/sequence at different speeds

when should you use the fast and slow pointer approach?

1. the problem will deal with a loop in a linked list or array

2. when you need to find the location of a particular element or the length of a list

what is the merge intervals approach?

an efficient technique to deal with overlapping intervals, based on six key relations between intervals

when should you use the merge intervals approach?

1. if you’re asked to produce a list with ONLY mutually exclusive intervals

2. if you see the term “overlapping intervals”

what is the cyclic sort approach and how does it work?

deals with problems involving arrays containing numbers in a given range; iterate over the array one number at a time, if current number is not at the right index, swap with the number at the correct index

when should you use the cyclic sort approach?

1. when you have a sorted array with numbers in a given range

2. when finding the missing/duplicate/smallest number in the array

what is the in-place linked list reversal approach and how does it work?

reversing a linked list while using existing nodes and no additional memory; reverse one node at a time starting with one variable (current) pointing to the head of the linked list, and one variable (previous) will point to the previous node that you have processed

what is the tree BFS approach and how does it work?

use BFS to traverse a tree and use a queue to keep track of the nodes of each level; first push root node to queue, visit the node at the head of the queue, pop the head, push the head node’s children, and iterate until queue is empty

what is the tree DFS approach?

use DFS to traverse a tree and use a stack to keep track of all of the previous parent nodes while traversing

how does tree DFS approach work?

Start at root, if root not a leaf

1) decide whether to process current node now (preorder), or between processing two children (in order), or after processing children (post order)

2) make two recursive calls for both children to process them

when should you use Tree DFS?

1. if asked to traverse a tree with preorder, inorder, or postorder DFS

2. if problem requires searching for something where the node is closer to a leaf

what is the two heaps approach?

when given a set of elements that can be split into two, and want to find smallest number in one part and biggest element in other part

how does the two heap approach work?

store first half of numbers in a Max Heap and second half of numbers in a Min Heap and calculate median of current list of numbers by looking at top element of both heaps

when should you use the two heap approach?

1. situations like priority queues, scheduling

2. if the problem requires finding the smallest/largest/median elements of a set

3. sometimes, if problem uses binary tree structure

what is the subsets approach?

a BFS approach for dealing with permutations and combinations of a given set

how does the subsets approach work?

Example

Given a set of [1, 5, 3]

1. Start with an empty set: [[]]

2. Add the first number (1) to all the existing subsets to create new subsets: [[], [1]];

3. Add the second number (5) to all the existing subsets: [[], [1], [5], [1,5]];

4. Add the third number (3) to all the existing subsets: [[], [1], [5], [1,5], [3], [1,3], [5,3], [1,5,3]].

what is the modified binary search approach?

a binary search strategy used for finding a certain element in a sorted array, linked list, or matrix

how does the modified binary search approach work?

The patterns looks like this for an ascending order set:

1. First, find the middle of start and end. An easy way to find the middle would be: middle = (start + end) / 2. But this has a good chance of producing an integer overflow so it’s recommended that you represent the middle as: middle = start + (end — start) / 2

2. If the key is equal to the number at index middle then return middle

3. If ‘key’ isn’t equal to the index middle:

4. Check if key < arr[middle]. If it is reduce your search to end = middle — 1

5. Check if key > arr[middle]. If it is reduce your search to end = middle + 1

what is the top k elements approach?

finding the top/smallest/frequent ‘K’ elements among a given set

how does the top k elements approach work?

Use a heap to solve multiple problems dealing with ‘K’ elements at a time from a set of given elements. The pattern looks like this:

1. Insert ‘K’ elements into the min-heap or max-heap based on the problem.

2. Iterate through the remaining numbers and if you find one that is larger than what you have in the heap, then remove that number and insert the larger one.

when to use the top k elements approach?

1. if asked to identify the top/smallest/frequent k elements of a given set

2. if asked to sort an array to find an exact element

what is the k-way merge approach?

another approach to problem solving for sorted arrays

how does the k-way merge approach work?

1. use a Heap to efficiently perform a sorted traversal of all the elements of all arrays

2. push the smallest element of each array in a Min Heap to get the overall minimum

3. after getting the overall minimum, push the next element from the same array to the heap

4. repeat this process to make a sorted traversal of all elements

when should you use the k-way merge approach?

1. The problem will feature sorted arrays, lists, or a matrix

2. If the problem asks you to merge sorted lists, find the smallest element in a sorted list.

what is the topological sort approach?

finding a linear ordering of elements that have dependencies on each other

how does the topological sort approach work?

1. Initialization
   a) Store the graph in adjacency lists by using a HashMap
   b) To find all sources, use a HashMap to keep the count of in-degreesBuild the graph and find in-degrees of all vertices

2. Build the graph from the input and populate the in-degrees HashMap.

3. Find all sources
   a) All vertices with ‘0’ in-degrees will be sources and are stored in a Queue.

4. Sort
   a) For each source, do the following things:
   —i) Add it to the sorted list.
   — ii)Get all of its children from the graph.
   — iii)Decrement the in-degree of each child by 1.
   — iv)If a child’s in-degree becomes ‘0’, add it to the sources Queue.
   b) Repeat (a), until the source Queue is empty.

when should you use the topological sort pattern?

1. The problem will deal with graphs that have no directed cycles

2. If you’re asked to update all objects in a sorted order

3. If you have a class of objects that follow a particular order