Hathaway Zhu

[latexpage]本文基于

[1] Grokking the Coding Interview: Patterns for Coding Questions

[2] The Ultimate Strategy to Preparing for the Coding Interview

如何解决算法问题的5个步骤How To Approach Any Algorithm Interview Without Panicking：

• Step 1: Rephrase the problem in your own words
• Step 2: Input and output types
• Step 3: Examples and Edge Cases
• Step 4: Data Structure(s)
• Step 5: Pseudocode and then the real code.

如何淡定面对算法面试题

关键点：将碰到的新面试题转换成以前你解决过的问题

Over time, I developed a set of problem-patterns that helped me quickly map a problem to an already-known one. Here are some examples of these patterns:

1. If the given input is sorted (array, list, or matrix), then we will use
   • a variation of Binary Search 
   • or a Two Pointers strategy.
2. If we’re dealing with top/maximum/minimum/closest $K$ elements among $n$ elements, we will use a Heap.
3. If we need to try all combinations (or permutations) of the input, we can either use recursive Backtracking or iterative Breadth-First Search.
4. Most of the questions related to Trees and Graphs can be solved by using:
   • Breadth-first search
   • Depth-first search
5. Every recursive solution can be converted to an iterative solution by using a stack.
6. If there exists a brute-force solution in $O(n^2)$ time and $O(1)$ space, and then there must exist two other better solutions:
   • Using a map or a set in $O(n)$ time and $O(n)$ space.
   • Using sorting for $O(nlog(n))$ time and $O(1)$ space.
7. If the problem is asking for optimal value (e.g. maximum or minimum), use Dynamic Programming.
8. If we need to find some common sub-string among a set of strings, use:
   • Hashmap
   • Trie
9. If we need to search among a bunch of strings, the best data structure is Trie.
10. If the problem involves a Linked List and we can’t use extra space, then use the Fast and Slow Pointer approach.