面试大厂的必考题 - 刷题的必经之路

大米奇缺，求大米！需要看站里的包裹细节帮我谈包裹！！感谢！！！


本人刷题1600+，contest 2100，历时大约一年半吧，刚过买它面试。个人认为算是有些overkill了，尤其在DP上花了几乎一半的脑力，迄今为止没有在面试的时候碰到过DP题。如果刚开始刷题的同学看到DP可以考虑先躲开，以后有空了再学。


我是基本上沿着古城的slides上路的，古城的slides做的整体上很好，可惜的就是在各个slides之间。题与题之间很难看出重点，类似的问题在其它刷题总结，刷题网站里面也会有。


这个帖子，希望能帮上一下刚上路的，或者没空准备1000+题的同学。


如果以下题目不能做到立即能听懂，不用思索就能快速写出来，建议别急着面试：

• binary-tree-vertical-order 这题是重中之重，LC里面有两题，而且可以很容易想出变种，比如同一level和column的顺序没有要求（这两题就是从左到右，和从小到大的区别），但如果没有要求，code怎么写最简短？dfs和bfs两种解法都必须会。
• LCA. 这题LC至少4题吧，但是熟练掌握bst的，和基本的binary tree的应该就可以了。比较简单，往往是面试时一题medium，一题easy的时候，那道easy的。
• LRU，LFU，LFU碰到的可能性小，但这两题因为超高频，而且是所有LC题目里面，非常难得的，有实际应用价值的题目，可以说是经典。相当于吃川菜必须尝尝水煮肉片一样。会做了，到底你在做什么，cache的意义在哪儿。比如如果你没设capacity，那cache必然会run out of space。
• calculator，什么时候stack可以不用。
• number of islands，人人都会做，而且变种题极多。UF没空就别练了，毕竟写起来繁琐，而且其实理解了不难，所以考官不是很喜欢让人用UF。dfs往往比bfs写起来快，建议直接把dfs背熟了。
• first bad version。binary search的经典，三种template自己选一个背熟。考官往往是把题目改一下，比如猴子吃香蕉啥的。但基本BS的while loop能写，都不难。
• reverse linked list。一个reverse，一个快慢指针，基本上覆盖了所有linked list题。reverse比快慢指针更重要。

不想把这个list弄的很长，我也知道这是远远不够的，但这几题可以说是我自己碰到过的超高频题。如果不能把editorial里面所有解法都熟练掌握，follow up questions都轻松答出来，就别急着面试。


没空就别学DP，跳过所有hard的题目。只盯着公司前50道里面的easy和medium反复练，然后就是看个人运气了。


如果还没空，graph的题目除了schedule of sources也跳过吧，毕竟出现的频率低些。


还有个现象，我面试时没做出来的题目，往往是前500题里面的，不熟练，或者干脆就没做过。我想，可能许多面试官当年进大厂的时候，LC还只有几百题，所以他们对前500题都很熟练了。毕竟如果总共只有500题，一年刷下来应该每题都刷过N次了。现在这些当年只有几百题可刷的同学，现在level上去了，做了面试官，他们各自选了一题自己当年喜欢的，但因为其它面试官overlap低，所以不会被列入各个公司的top题里。所以有时间的同学，刷完了top 题，可以回过头来，把LC前500题过一遍。


如果有同学能做个网页，或小程序，能把各个大厂的top 100比较一下，筛选出overlap的，可以贴在下面，应该会很有用。


希望大家帮帮忙，给个大米赞助，在team match，包裹还没谈，需要大米看别人包裹细节。感谢！！

匿名用户 发表于 2024-12-2 12:20
请问一下，editorial里面所有解法 是指什么

新手往往会一种解法，或者学会了最优解就move on去下一题了。

但是这几道超高频题，最好把editorial里面所有的解法都全面掌握，因为你做的慢了吧，怕下一题来不及。做的很快吧，两三分钟就结束战斗了，面试官又没有准备下一题，他很尴尬，就可能问你，你刚才做的dfs，能不能用bfs做一遍。或者你用的iterator，能不能用recursion做一遍。这时候就有点考验水平了。因为我们往往用惯了recursion的，所有类似题目都用recursion。

这里就有一个比较公认的观点：刷题宁愿一题多解，而不是一解多题。就是说，学了一种算法，这题熟练了，别急着用同一个算法去套用其它题目提高LC上的刷题量，而是应该把熟练的题目的多种解法都摸透，这样刷题效果更好。

毕竟我们的目的是进大厂，上岸，不是LC上的数字。刷3000，进不了大厂也是自娱自乐。

虽然我现在面试不怎么考刷题了，还是得说一下对于新手来讲，刷题是最简单的部分，所以在没有经验或经验较少的情况下，别搞砸了。

HarderQ 发表于 2024-12-2 12:47
一般 DFS 和 BFS 会，就能应付大多数面试了。

是的，这两个是基础，如果不能闭着眼睛写，学习dijkstra, Bellman Ford, Floyd Warshall, Prim, Kruskal都是胡闹了。我早期觉得graph非常好玩，过早得投入大量时间学习所有graph相关的题，但最终只碰到过course schedule，这些graph的算法现在许多大学CS专业也教，不过面试官本人毕业多年，自己未必还记得，甚至他们也未必就学过。如果自己都不熟练，也问不出高质量的follow up question。

大厂面试官都是对自己出的题非常了解，非常熟练的。所以题目本身往往容易描述，不会需要画几个图才能解释清楚要求是什么。

碰到过的，最复杂的graph的题，应该就是围棋了。这个也是dfs或bfs解决。

Schedule of source的题号是多少？lc没搜到啊

wzhang23 发表于 2024-12-2 10:29
Schedule of source的题号是多少？lc没搜到啊

207， 210

所有graph的algorithm可能是最好玩的，但是写下来多多少少需要时间，这个topo sorting相对写的快些，也是graph的入门题。

wuwendongxi 发表于 2024-12-2 09:51
虽然我现在面试不怎么考刷题了，还是得说一下对于新手来讲，刷题是最简单的部分，所以在没有经验或经验较少 ...

说的很对。BQ和design虽然整体投入的时间少些，但是难以衡量自己是否ready，除非你找到已经上岸的高手帮你mock。

刷题仍然是最容易的一步，而且是最花时间精力的，这个不过关，就别折腾了。

米加了
你也可以直接买通行证解锁功能

请问一下，editorial里面所有解法 是指什么

一般 DFS 和 BFS 会，就能应付大多数面试了。

赞！
给你大米！