Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
http://www.1point3acres.com/bbs/thread-226117-1-1.html
经验;
这次出去onsite了一圈,发现大多数题目还是dfs bfs dp, 二分,sliding window,还有一些实现题
(包括 拓扑排序 双指针 位运算 实现数据结构LRU LFU,stack/queue,Trie,外排序, 甚至是数据结构的设计等) 其他题目没怎么碰到。
其中dfs bfs dp的题目加起来超过了65%+的算法题
本来想这次努力刷题,接下来这辈子都不用刷题了,自然 现实又让我碰个头破血流,只能祈求接下来3年不要再刷题。(可能也是奢望吧)
如果需要再次刷题,可以看看下面重点题目,应该可以再短时间准备出能勉强去三流公司面试的做题水平。
1.dfs
比较简单直接, 循环加递归 +dfs“枝丫”(由递归产生)的终止条件(终止递归)
当然 这个循环可以是for循环,
如Combinations
还可以是是树里面遍历各个children node
如 Minimum Depth of Binary Tree
终止条件可以再循环内 也可以在循环外(其实本质是一样,就是终止这一支的递归)
另外现在市场上还出现了一种 需要多重排列组合来得到最终结果的(1个排列组合得到的"半结果"还要去和另外一个“半结果”去排列组合),那么就是dfs里嵌套dfs
dfs的时间复杂度是O(b^m) b是分支系数(有多少个child/邻居) m是树/图的最大深度
2.bfs (经常需要和建立图一起使用)
还是比较简单直接, 就是找到一个起点,然后入queue 然后再出queue的时候把他的孩子都放入queue
如Binary Tree Level Order Traversal
当然,如果是bfs树,那么他的邻居就是他的孩子,
如果是bfs矩阵,那么它的邻居就是他周围的node
如果是bfs 其他东西(类似) 类似word ladder1 那么你就要稍微写点业务逻辑来找邻居。
某大公司之前还碰到一题是 a/b =2 c/d =4 e/f =6 b/d=5 等等一堆(当然 原题比这个要隐晦许多) 然后问你a/e是多少
我之前往错误的方向想了半天,实际上是建立一个图 然后bfs看看是否有联通的路径
当然想往难的考可以 比如word ladder2
BFS + Dijkstra's algorithm +找到距离后dfs找最短路径
返回从词A到词B的各种路径 BFS + Dijkstra's algorithm
Dijkstra's algorithm 是用来求 在一个有向图里的两点 是否存在路径,如果有的话,最短路径是多少
在这里的ladder就是路径和他们之间所需的距离, 如果没有路径 那么他们的距离就 Integer.MAX_VALUE
如果有多个不同的路径的话,我们会动态更新最短路径并且存在ladder这个map里 eg:(AB,3)->(AB->2)
对于不含负权(距离为负)的有向图,这是目前已知的最快的单源最短路径算法。
1.首先建立图 Map<String,List<String>> map; 每个合法的String和他的邻居,邻居就是变位一个词后能 生成的合法新String
2.同时建立一个map来存每2个词之间的min ladder
//ladder表示2点(2个词)之间的最短距离,如果没有就是无限大的距离
//在这里 他们表示当前是String和 beginWord的距离
Map<String,Integer> ladder = new HashMap<String,Integer>();
某个面试官对 bfs找到最短路径后我用dfs找actual path 非常不满意,说可以不用dfs ,在之前bfs时候就记录路径 然后直接可以在找到最短距离时候得到结果。我查了一下地里,的确有 “对于ladder II这种寻找path的题 如果求所有路径的是需要先bfs然后dfs,但是如果是只要一条最短路径,只需要一次bfs。具体来说在bfs的过程中,在把下一层节点i加入queue的时候,用一个map记录,key是下一层节点i的id, value是本层的节点id。这样到最后,就可以从结束点开始往前找parent,一直找到开头的点。因为加入queue的过程就是确定下一层点的parent的过程,所以每个点只进入queue一次,这个用set来保证。我说的这个只是针对输出一个最短path的解法,不过感觉现在确实好多面经是输出一条,个人感觉这样面试官更好看,输出那么多他也看不完~~”
当时只剩几分钟了 ,没想出来,跪。
3. DP
DP的本质是什么, 就是从一个局部的,确定的解,推导出 所有由这个确定的局部解可能发生的情况,然后再这些情况里找到 最大/最小/最xxx,然后进一步推导 更大的局部解,
然后直到全局解。
比方说最简单例子 一维dp fibonacci 就是由f1 f2...推导出fn , f1 f2就是初始的确定局部解
然后矩阵dp[j] 确定局部解可能是 dp[0][0] 和其中一条或者 两条边 dp[0] dp[0][j] 甚至是对角线dp
如PascalTriangle ,paint house II
当然 其中可能不是1 1对应这么简单,在推导的过程中需要采用一定的业务逻辑
如RegularExpressionMatching
最后有可能题目不是很直接, 连确定的局部解都比较难找,那么可以换一种思路。
如 BurstBalloons
“ dp的本质是什么 是从确定的子问题推到到全局
那么这个pop气球的问题比较特殊 因为假设你第一次pop2(产生平行宇宙1)
那么你接下来就变成 134 adjacent 如果你第一次pop3(产生平行宇宙2) 那就变成124 adjacent
adjacnt的变化导致你在 你在平行宇宙1 2 里 哪怕都是第二次pop4 产生的结果也是不一样的 而且对未来的总结果有影响
所以并不符合 dp 是从确定的子问题推到到全局
所以 另一种经常的dp思路 是从最后一个开始推导
因为最后一个被干爆的气球 数组里只剩他一个了 nums[-1]*nums*nums[n] 然后 nums[-1] = nums[n] = 1
所以最后一个干爆气球是i 得到coin是完全确定的
那么在最后一个干爆气球是i是确定的情况下, 倒数第二个干爆的气球是啥 会产生什么coin, 也是确定的
这样 就能从后往前推导出整个 pop的顺序, 然后都试一下得到最大的
符合了 dp的本质
4.二分
比方说想各种 sorted rotated array 或者/\这样的array 的稍微练习下他们的具体实现。
教训:
1. 第一个面试,哪怕电面一定要是你不想去的公司。因为第一个面试搞砸的可能性很高
2. 不要去太忙的公司/组上班, 如果一个candidate 上班都能刷题,另外一个candidate 要加班 oncall release 等等 要等10点 11点才可以开始刷题,你说那个candidate 有优势?
3. 一个人的命运啊,当然要靠自我奋斗,但是也要考虑到历史的行程, 特别是公司的bar 的高度并不是一直不变的。
4.肯定不会去的公司/组,只要去一个练兵就够了,人的精力是有限的, back on back onsite对后一场的发挥压制很大。
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.