FB面经（沉舟侧畔千帆过，你们加油）

Job Hunting Interview
, , , ,
1

Position: SDE intern PhD Summer 2020
面试一共两轮。第一轮两个面试官，第二轮一个面试官。
第一轮第一个面试官：（白男）两道题，LC 199 + LC 680。很容易秒过。先跟面试官说了要用什么方法，再给的例子上演示了一遍，解释的非常清楚。然后面试官让我实现。实现完了面试官让我用给的例子把代码跑一遍，验证结果。

第一轮第二个面试官：（白女）可能是第一个人做的太顺利还是？第二个面试官上来就考了一道新题，group Caesar cipher string。就是给了一个string list 把相同的 Caesar cipher 的string组合到一起。
Example ： [“abc”, “ace”, “xyz”, “fhj”]
result: [[“abc”, “xyz”],[“ace”, “fhj”]]
一开始只想到了N^2的方法。后来面试官提示以后，想到了用dictionary，key是各个字母的距离，比如：abc -> key = 11, ace -> key = 22。 然后在dictionary.value 就是答案。

第二题貌似是个变题，Ordered Set 让我设计一个数据结构。跟set相同不过就是要保持element 加入的顺序。
add(val), remove(val), show()
add(1)
add(5)
add(8)
show() -> [1,5,8]
remove(5)
add(9)
show() -> [1,8,9]

这个还是用dictionary来做，这次的key是插入的val，value是一个全局变量idx，初始化为0，
当add()的时候 idx += 1 付给新add进来的val。O(1)
remove()的时候，问了面试官能不能 O(n) 面试官说可以，那就是删除val的时候，得到相对应的idx。 然后遍历所有在dictionary 中的values 刚 value > idx: value - 1 这样就能保持输出的idx不会乱。然后全局变量idx也要-1.
show()的时候就是创建一个list，把key填到value的index位置。

第二轮跟第一轮差了两个星期。第二轮一个面试官 （挂了）
面了一道非常高频的 143. Reorder List … 长期没做过linked list的题了。当时瞬间脑子就乱了，想错了，也就写乱了。也就挂了。

因为 Linked List是我开始刷题的时候第一个写的 tag 所以一直都觉得“没问题”，所以复习的时候就没有做到Linked list的题。后悔吗？嗯！但是也没有用了。。。所以大家还是把能做的题都做了比较保险。

第二轮面试官是个（印男）不过跟种族没关系，自己的问题。

就这些吧。给了我一年的 cool off 不知道还能不能argue一下。。。大家加油！

2

这题论坛有： 脸熟实习

3

这题不就是 LRU， LinkedHashMap的实现吗？

你这轮跟 脸熟实习 一模一样

4

感觉这个思路是错的

FIFO就应该是 LRU 的思路吧

5

你不能打开自己的代码直接抄么？

6

按照你说的，是第二轮没答好。确实看上去题目不难，没答出来是performance不够好。
那按照标准就是1年冷冻期，你想argue什么？

7

啥？好吧，我还真没做个那道题。。。感觉碰到Cache都很难，就没做。一会儿给做了！啊哈哈

8

可以看下这个视频讲解

9

由于长时间没做了，当时想找也不知道题号是什么。。。就没找。。。

10

好吧，那就算了

11

这题也是FB高频题了，而且你其实可以临时放狗搜下的，比自己硬刚来的不容易错

12

我抄網上的。怎樣解释這是正碓的？ 這是唯一解嗎？

Convert string to position in alphabet string and minus minimum index from the rest:

String letters = "abcdefghijklmnopqrstuvwxyz";
public List<List<String>> groupCipher(List<String> lst) {
    List<List<String>> res = new ArrayList<>();
    if (lst.size() == 0) return res;

    Map<String, List<String>> group = new HashMap<>();

    for (String s : lst) {
        int[] cnt = new int[s.length()];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int dist = s.charAt(i) - 'a';
            cnt[i] = dist;
            min = Math.min(min, dist);
        }
        for (int i = 0; i < s.length(); i++) {
            cnt[i] -= min;
        }
        group.computeIfAbsent(Arrays.toString(cnt), k -> new ArrayList<>()).add(s);
    }

    for (List<String> v : group.values()) {
        res.add(v);
    }
    return res;
}
13

面FB先得把所有tag题题目全都背上:hear_no_evil:都是经验之谈

14

思路说一下吧