- The possible algorithms to use based on the subject condition:
比如一个数组的长度如果给了最多10³,那基本可以用O(n²)解法。如果是10⁵,那必须控制在O(NlogN)。如果到10⁹了,那就得O(n)甚至O(logN) - 重点放在Graph, Tree, Recursion, Linked List, binary search上。DP感觉投入产出比一般,我这次是一道DP也没遇上。Graph要尤其滚瓜烂熟,DFS, BFS, Topo sort, Bipartite, Dijkstra, union find这几个算法要可以不动脑子写出来。尤其是union find这个平时根本用不到的数据结构,写法和时间复杂度要弄懂。我三次面谷歌每次都有union find的题。。Tree的话主要练习inorder和postorder traversal。Linked list要熟练运用slow fast pointer和dummy head pointer。binary search建议用two pointer,注意边界条件。结束条件是l <= r还是l < r? 结束以后是return l 还是r?
- General Questions and their solutions
1> Subsequence: (1) longest Palindrome subsequence — DP (2) longest subsequence, sorted array — Binary search