Coding Interview Key Patterns

Question 1

Linked Lists

Answer 1

List manipulation

• Iterate through the list
• Recurse through the list

Slow / fast pointers

Use two pointers

Question 2

Two Pointers

Answer 2

Head and tail pointers move toward the middle.

Slow and fast pointers.

Sliding Window.

Question 3

Binary Search

Answer 3

Collection must be sorted.

Can find in O(log n) time.

Avoid integer overflow:

int mid = left + ((right - left) / 2);

Can be implemented recursively or iteratively

Question 4

Binary Search Tree

Answer 4

A special characteristic of BST is that its in order traversal yields a sorted array. Note that the definitions of BST might be different for different problems. Moreover, you can recover a binary search tree from its preorder traversal.

Question 5

Stack and Queue

Answer 5

The main characteristics of stack and queue are LIFO (Last In First Out) and FIFO (First In First Out) respectively.

Stack and queue are frequently used in tree and graph traversal problems, leveraging stack for DFS and queue for BFS.

Question 6

Hash table and set

Answer 6

Hash table/set is one of the most frequently asked data structures in coding interviews. When stuck, try hash table. Hash table and hash set are also very useful to make time-space trade off. They enable O(1) time of searching.

Question 7

Tree

Answer 7

Most of tree problems are traversal problems. Traversal algorithms such as DFS including ‘pre-order’, ‘in-order’, and ‘post-order’, and BFS or level order traversal are extremely important.

Generally speaking, the time complexity of DFS algorithm is O(n) where n is the number of nodes and the space complexity is O(h) where h is the height of the tree due to implicit stack used in recursion.

Additionally, BFS problems generally have complexity of O(n) in time and O(w) in space, where w is the maximum width of a tree. Moreover, it is very important to know concepts such as ‘depth’, ‘height’, ‘level’, ‘complete tree’, and ‘perfect tree’, etc.

Question 8

Graph

Answer 8

Graph problems are generalization of tree problems.

DFS and BFS traversals are extremely important algorithms in graph problems.

One key difference between graph and tree problems is that graph traversal requires a visited variable to memorize nodes that have been visited before.

Moreover, use DFS to solve connected problems and BFS to solve shortest path problems.

The complexity of graph traversals is generally O(V+E) in time and O(V) in space, where V is the number of vertices/nodes and E is the number of edges.

Question 9

Divide and Conquer

Answer 9

Divide and conquer approach refers to decomposing a big problem into smaller problems, then combine the results obtained from these smaller problems which are solved recursively.

When stuck, think about the base case (the smallest problem), and see if we can build up a solution recursively from there.

Merge sort and quick sort algorithms both leverage divide and conquer approach.

1. Divide. Divide the problem into a set of subproblems:
2. Conquer. Solve each subproblem recursively.
3. Combine. Combine the results of each subproblem.

Question 10

Greedy Algorithm

Answer 10

Greedy algorithm is a simple and heuristic algorithm that follows the problem-solving heuristic of making the locally optimal choice which might but not necessarily end up a global optimal solution. It builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Sometimes, we solved a problem using our instinct without even realizing it is a greedy algorithm problem.

The difference between greedy algorithm and dynamic programming (DP) is subtle. Detailed comparison is highlighted in this article. In general, greedy algorithm is simpler and myopic, and make heuristic decision based on locally optimal choice. DP is generally harder, and makes decision at each step considering current problem and solution to previously solved sub-problems.

In practice, a problem might be able to solved in both ways, as pointed out in this article “beneath every greedy algorithm, there is almost always a more cumbersome dynamic programming solution”.

Question 11

Backtracking

Answer 11

Backtracking is an exhaustive search algorithm for solving combination, permutation, subset, and constraint satisfaction problems. It solves a problem recursively by trying to build a solution incrementally while removing solutions that fail to satisfy the constraints of the problem. The time complexity of backtracking algorithm is generally large, e.g., at least C(n, k) for combination problem and at least P(n, k) for permutation problem reference. This video gives a great tutorial on how to implement backtracking algorithm for combination and permutation problems.

There are three key pillars in backtracking algorithms: (1) the base case, exit condition or the goal to achieve, (2) the choices to make to go to the next building step, and (3) pruning that discards solutions that fail to satisfy the constraints of the problem.

def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return

# iterate all possible candidates.
for next_candidate in list_of_candidates:
    if is_valid(next_candidate):
        # try this partial candidate solution
        place(next_candidate)
        # given the candidate, explore further.
        backtrack(next_candidate)
        # backtrack
        remove(next_candidate)

Question 12

Dynamic Programming

Answer 12

Dynamic programming (DP) is an algorithm to solve problems by breaking it down into simpler and smaller subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solutions to these subproblems. DP algorithm is similar to Greedy and Divide & Conquer algorithms in breaking down the problem into smaller subproblems. However, these subproblems are not solved independently, and results of these smaller subproblems are remembered and used for similar and overlapping subproblems.

DP has two forms: top-down (recursion + memoization) and iterative bottom-up. The main goals of DP are reducing time complexity of a problem solved by using recursion from exponential to lower ones such as linear or finding counting and global optimal solution to a problem. The key to solve a DP problem is to find an iterative or recursive formula.

Asking DP problems in coding interviews has been a little bit controversial. It is highly likely that an interviewee either solves the problem in several minutes or gets stuck for the whole coding session. Additionally, a lot of DP problems are really involved and complicated. However, DP is one of the most important algorithms in practice, and proven to be very useful to solve optimal control/decision problems.

Question 13

Miscellaneous - String

Answer 13

Some of the most famous string problems include anagram, palindrome, substring, and rotation. If you are not familiar with the definition of anagram or palindrome, it might be a good idea to understand these concepts before the interview.

Question 14

Miscellaneous - Array

Answer 14

Index plays an important role in array problems. In some problems, values in array are used as indices as well. Quick select is a great algorithm to find the k-th smallest element in an array in O(n) time, which outperforms heap/priority queue and sorting algorithms which have time complexities of O(nlog(k)) and O(nlog(n)) respectively.

Question 15

Miscellaneous - Math

Answer 15

Typical math problems include finding prime numbers, gcd (greatest common divisor), lcm (least common multiple), converting base, and check if a number is a power of 2/3/4, etc.

There are a couple of tips related to gcd and lcm.

find gcd, def gcd(a, b): return a if b == 0 else gcd(b, a%b), time complexity O(log(min(a, b))).

find lcm, def lcm(a, b): return a*b//gcd(a, b).

Question 16

Miscellaneous - Bit manipulation

Answer 16

Bit manipulation problems can be very tricky. If you don’t know the concept, it is highly likely you will not be able to solve the problem, and there is generally no workaround by using other algorithms.

The fundamental operations of bit manipulation are:

x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
where 0s and 1s represent a sequence of 0s and 1s respectively.

There are a few tips that might help solve bit manipulation problems.

Leverage x ^ 0s = x and x ^ x = 0, we can remove or find duplicate number, e.g., 1^1^2 = 2.

x&(x-1) will remove the last 1 in the binary representation of x, and x&(-x) will get the last 1 in the binary representation.

The binary representation of -k as a n-bit number is concat(1, bin(2^(n-1)-k)) where bin denotes binary representation.

In Java, Integer.toBinaryString(x) will convert an integer into a binary string of 1’s and 0’s.

Question 17

Advanced Topics - Trie

Answer 17

Trie is a special tree data structure that stores the letters of a string in an ordered manner. It enables fast search of a string by traversing down a branch path of the tree. It behaves as a dictionary, we can navigate to the next letter from the current letter. Each Trie node has a children variable and a is_word variable. The children variable is generally a hash table with letter as key and Trie node as the value, and the is_word variable is boolean.

There are three common methods for Trie data structure, insert, search, and start_with. The difference between the search and start_with functions is the is_word flag is true or not after iterating through the searched string. When encountering key words such as prefix, dictionary, search, and word, etc. in a coding problem, think about the Trie data structure.

Question 18

Advanced Topics - Topological Sorting

Answer 18

Topological sort is only feasible for DAG (directed acyclic graph). One way to implement topological sorting is use BFS. First add nodes with in-degrees/out-degrees equal to 0 to queue. Then pop a node, traverse to its neighbors, and subtract 1 from the in-degrees/out-degrees of the neighbors. If the current in-degree/out-degree of a neighbor is equal to 0, add it to the queue.

Question 19

Advanced Topics - Union Find

Answer 19

Union Find algorithm or disjoint-set data structure aims to find if two nodes are in the same set in amortized O(1) time. There are two operations in the UnionFind class: find and union. To enable amortized O(1) time of find, two optimizations need to be done for the UnionFind class: path compression and union by rank.