talk on onsite interview from FLG

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对后一场的发挥压制很大。