非死不可面经

非死不可电面, 面试官是美国人, 说话巨快。

上来面试官自我介绍和解释自己的组, 然后就开始做题。

  1. 第一道FB高频题, merge三个sorted list
  2. 第二道求一棵树任意两个node中间相隔的hubs的最大数, 比如说
         30
       /   \
      2   12
    /  \
    7   3

这棵树节点9和节点11中间相隔4个节点, 返回值就是2

用dfs算树的depth = max(neft, right) + 1, 同时更新longest = max(longest, left + right - 2)
237. Lowest Common Ancestor of a Binary Tree

onsite感觉基本都是原题合集。

  1. 给一棵树, 实现中序遍历的迭代器,就是每调用一次next()返回下一个中序遍历的值。
    follow up:pre-order, 有原题

  2. 系统设计, 输入提示 type suggestions.

  3. 给一个二维字符串数组, 例如[ [“abc”, “a”], [“b”, “c”]],每个数组取一个出来按顺序组成新字符串
    , 求所有的字符串。 答案就是[“abcb”, “ab”, “abjc”, “ac”]
    4, 给定两个字符串a,b, 以及一个order 例如"cdab"。 如果字母的大小是按order先后顺序(这里
    就是c < d < a < b),求按照这个顺序的a和b

  4. 求一棵树任意一对节点的最远距离,这一对节点不一定需要经过root节点, 貌似有原题

第一题:利口 623
第二题:应该也是利口原题,给一个number set,找出所有大小为k的permutation
followup:如果number set里有duplicate咋办