目录
今年又面了一波,集齐了FANMG的offer,发现刷题在找工作中的比重越来越低。这有多方面的原因,但是最大的因素是刷题对我来说已经不是那么的困难了。
回头看,刷题其实是一劳永逸的,熬过之后收获是持续性的,完成一次完整系统的刷题,之后再找工作只需要稍加温习即可。而且随着level越来越高,算法题的比重也越来越低,更多的是考察系统性知识、leadership和culture fit。
最近做了一些分享,发现很多人还在刷题的煎熬中,甚至有些迷茫,这边我整理下我的刷题方法,希望对大家有帮助。
几个重点
- 刷题只需要200-300道即可,不是以量取胜的,加量会透支自己的精力(当然如果精力旺盛的话,尽管刷)
- 不是能写出来答案就能过面试,需要理解为什么用这个解法,各种解法之间的trade off,写代码之前如果能做好沟通,能大大的给你加分
- 别把刷题看的很难,对比于高考来说这都是小儿科,而且核心的算法就那么几个,解法也就那么多,把每一个解法都吃透了,不会碰到太出格的。
- DP不在今天讨论范围,常见的可以看下,除非你要找特定公司,不然的话DP纯浪费青春
- 面试是看缘分的,不要害怕被问到一道不会的题目,就想去把所有奇奇怪怪的题都刷了,大多数面试题都是高频常见的,面试官也是人,他只是想考察你的能力,太难的并不利于考察也不利于招聘,当然那些不怕招不到人的公司除外,如果真的被问到了不会的,尽力去做就好,这是缘分。换句话说,有些时候你答的很好,也会被拒,不要太放在心上,缘分到了啥都来了。
- 系统设计和BQ不在这次讨论之中
刷题方法
我每次刷题都是按照以下的步骤,如果是第一次刷题,需要花更多的时间在每一题的理解上,而非仅仅把他做出来。时间线大约是1个月,如果第一次的话一般需要3个月。不推荐安排3个月以上,一来消耗自己的精力,二来每次刷题如果不够专注的话并不能让你深刻理解。
- 基础知识复习:这方面基本上就是看下各种算法优劣点、时间复杂度、适用场景,这个自己整理好,每次都能拿出来用。
- 按照解法、题型刷题(题型整理在后面),标记那些自己觉得没把握的(没有彻底理解的),这一块根据自己的能力推进,切记完全搞懂了再推进下一个,不然就白刷了。除了我列出来的题目,可以在leetcode上按照右侧的tag刷一下该题型的高频,确定自己理解透彻了。
- 查漏补缺,把之前标记的题拿出来混做一下
- 【投简历之后】开始按照面经和公司tag高频刷一下,边面试边刷。投简历的时候自己分一下tier,把不想去的最先投,练练手。要是简历投了没回应,请到这里:北美找工作(简历修改)咨询服务
题型、解法整理
这里只是给你整理了典型的题型和解法,具体怎么解,模板自行网上搜,或者留言提问。如果实在搞不清楚,上面那个链接的咨询服务可以用来答疑
Binary Search
这是最最最基础的,一定要熟记并且知道什么时候用。基本上有排序的数组,然后找个一个数字都应该想到binary seach。排序的时间复杂度是NLog(n),搜索的时间复杂度是Log(n),所以比O(n)遍历更加的解法就是他了。
这里给一套我用的模板,注意我这边是start + 1 < end 所以在结束的时候是相邻的,需要检查下相邻的两个哪个是结果。
class Solution: def search(self, nums: List[int], target: int) -> int: start = 0 end = len(nums) -1 while start + 1 < end: mid = start + (end-start)//2 if nums[mid] >= target: end = mid if nums[mid] < target: start = mid if nums[start] == target: return start if nums[end] == target: return end return -1
- https://leetcode.com/problems/binary-search/
- https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
- https://leetcode.com/problems/first-bad-version/
- https://leetcode.com/problems/search-in-a-sorted-array-of-unknown-size/
- https://leetcode.com/problems/search-in-rotated-sorted-array/
- https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
- https://leetcode.com/problems/search-a-2d-matrix/
- https://leetcode.com/problems/search-a-2d-matrix-ii/
- https://leetcode.com/problems/find-peak-element/
Tree
如果新手的话,树的题目会比较难上手,不过他都是有两种解法——Traverse 和 Divide Conquer,体会两者的不同,为后面的DFS打基础。Tree 这部分会比较煎熬,但是一定要掌握。
- https://leetcode.com/problems/binary-tree-inorder-traversal/
- https://leetcode.com/problems/binary-tree-preorder-traversal/
- https://leetcode.com/problems/binary-tree-postorder-traversal/
- https://leetcode.com/problems/maximum-depth-of-binary-tree/
- https://leetcode.com/problems/diameter-of-binary-tree/
- https://leetcode.com/problems/binary-tree-paths/
- https://leetcode.com/problems/maximum-subarray/
- https://leetcode.com/problems/balanced-binary-tree/
- https://leetcode.com/problems/maximum-average-subtree/
- https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
- https://leetcode.com/problems/validate-binary-search-tree/
- https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
- https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
- https://leetcode.com/problems/binary-search-tree-iterator/
- https://leetcode.com/problems/insert-into-a-binary-search-tree/
- https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
BFS
这部分是我觉得仅次于二分法简单的,不过代码比较长,但写起来很享受,有很多时候BFS和DFS都可以的话,推荐写BFS,容易理解也不容易出错。当然我也碰到面试官一定要你写DFS的,毕竟BFS过于简单了。
BFS的模板我就不提供了,简单的来说就是用一个queue,把初始点放进去,然后while循环直到queue空为止,每次操作把处理到的附近节点都放到queue里面去,记得要用个set去check是否已经放过了,不然会死循环。
**另外BFS里面涉及到图的题目,这里也放进去了。
- https://leetcode.com/problems/binary-tree-level-order-traversal/
- https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
- https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
- https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
- https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
- https://leetcode.com/problems/graph-valid-tree/
- https://leetcode.com/problems/clone-graph/
- https://leetcode.com/problems/number-of-islands/
- https://leetcode.com/problems/number-of-distinct-islands/
- 【这题虽然关系不大,但考察操作】https://leetcode.com/problems/spiral-matrix/
- 【用DFS更好】https://leetcode.com/problems/word-ladder/
拓扑和图
拓扑(Topological Sort)和图相关的,极度高频,掌握怎么用indegree去寻找入口
- https://leetcode.com/problems/course-schedule/
- https://leetcode.com/problems/course-schedule-ii/
- https://leetcode.com/problems/sequence-reconstruction/
DFS
基本上就是找排列或者组合的题目,DFS的入门比较难,但是只要入门了,就是非常厉害的一个工具,不像DP,学了半天也不知道怎么用。
- https://leetcode.com/problems/combination-sum/
- https://leetcode.com/problems/combination-sum-ii/
- https://leetcode.com/problems/subsets/
- https://leetcode.com/problems/subsets-ii/
- https://leetcode.com/problems/palindrome-partitioning/
- https://leetcode.com/problems/permutations/
- https://leetcode.com/problems/permutations-ii/
- https://leetcode.com/problems/n-queens/
- https://leetcode.com/problems/word-ladder/
Linked List
这个概念要先掌握,不然会一团浆糊,特别是指针,不是很懂的推荐先去看看书。linkedin list最重要的一个技巧就是用dummy node
- https://leetcode.com/problems/partition-list/
- https://leetcode.com/problems/merge-two-sorted-lists/
- https://leetcode.com/problems/reverse-linked-list/
- https://leetcode.com/problems/reverse-linked-list-ii/
- https://leetcode.com/problems/swapping-nodes-in-a-linked-list/
- https://leetcode.com/problems/reorder-list/
- https://leetcode.com/problems/rotate-list/
- https://leetcode.com/problems/copy-list-with-random-pointer/
- 【绝对不会考,但是学习下技巧】https://leetcode.com/problems/linked-list-cycle/
- https://leetcode.com/problems/sort-list/
- https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
- https://leetcode.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
- https://leetcode.com/problems/reverse-nodes-in-k-group/
Array
array的题目特别多,特别杂,一部分可以用hashmap/hashset或者PriorityQueue解决,不过还是推荐有空多刷一刷,没空的话,就看看下面几个典型的
- https://leetcode.com/problems/implement-strstr/
- 【三目翻转】https://leetcode.com/problems/rotate-array/
- https://leetcode.com/problems/intersection-of-two-arrays/
- https://leetcode.com/problems/merge-sorted-array/
- https://leetcode.com/problems/median-of-two-sorted-arrays/
- https://leetcode.com/problems/k-closest-points-to-origin/
前缀和数组
- https://leetcode.com/problems/maximum-subarray/
- https://leetcode.com/problems/subarray-sum-equals-k/
双指针
- https://leetcode.com/problems/move-zeroes/
- https://leetcode.com/problems/remove-duplicates-from-sorted-array/
- https://leetcode.com/problems/valid-palindrome/
- https://leetcode.com/problems/rotate-string/
- 【和hashmap解法的区别】https://leetcode.com/problems/two-sum/
- 【本质上是2sum】https://leetcode.com/problems/3sum/
- 【本质上是3sum】https://leetcode.com/problems/4sum/
- https://leetcode.com/problems/3sum-closest/
- https://leetcode.com/problems/sort-colors
Priority Queue
非常强大且容易掌握的数据结构,但是一定要知道他是怎么实现的(heap)
- https://leetcode.com/problems/ugly-number/
- https://leetcode.com/problems/ugly-number-ii/
- https://leetcode.com/problems/top-k-frequent-elements/
- https://leetcode.com/problems/merge-k-sorted-lists/
- https://leetcode.com/problems/high-five/
- https://leetcode.com/problems/k-closest-points-to-origin/
- https://leetcode.com/problems/merge-k-sorted-lists/
- https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
其他
- 非常高频以及综合的一道题:https://leetcode.com/problems/lru-cache/
- https://leetcode.com/problems/meeting-rooms-ii/
- https://leetcode.com/problems/insert-interval/
- 【常见的DP题目】https://leetcode.com/problems/trapping-rain-water/
- 【买卖股票的终极DP】https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
- https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/
- https://leetcode.com/problems/random-pick-with-weight/
- https://leetcode.com/problems/insert-delete-getrandom-o1/
- https://leetcode.com/problems/valid-sudoku/
其他资源
Blind 75极致快速刷题:https://leetcode.com/discuss/general-discussion/460599/blind-75-leetcode-questions
ct6ial
crtopg
vm1fq4
wqwnrd
bqia37
谷歌搜刷题发现了您的博客,发现您的career path有很多转换赛道的决定,很有趣!从云到互联网,金融到电商。我身边的同龄人选择了大包不断进步,但上次找工的时候刷题没有克服自己效果不佳。感谢您的输出,让我可以在某些论坛之外发现晒包和争吵之外的真正价值。
请问看你资料你现在是senior manager了,面试还要考这些吗?
现在的趋势是都要会写代码,虽然平时工作不需要,但这是基本的,我之前见过director往上也考算法的,其实有过一次完整准备,之后复习一下很快的
不错!点赞。