面经：Google两轮背靠背

如题，谷歌两轮背靠背电面。两轮都是废话不多说直奔coding，虽然第一轮的中国大哥还是花了一点点时间了解了一下我的背景、毕业时间、research方向。说好的research面呢？

中国大哥出的题:

Given a set of integers, print out all the subsets
For example, {1, 2, 3}
output: {}, {1,2}, …., {1,2,3}

我的解法：

public ArrayList<ArrayList<Integer>> findsubsets (int[] S) {
    Arrays.sort(S);
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> set = ArrayList<Integer>();
    for (int i=0; i<S.length(); i++) {
        helper(set, res, S, i, 0);
        }
        return res;
}

public void helper(ArrayList<Integer> set, ArrayList<ArrayList<Integer>> res, int[] S, int i, int starter) {
    if(res.size() == i) {
        res.add(new ArrayList<Integer>(set));
        return;
        }
        for (int j=starter; j<S.length(); j++) {
        set.add(S[j]);
        helper(set, res, S, i, j+1);
        set.remove(S[j]);
        }
}
        

问的问题我大概十分钟写出来，但是花了二十分钟给他讲懂。他先没懂。一直在纠结这个Recursion最后怎么终止的，举了个例子比如length=10, starter=8, i=5, 我跟他说这个循环自己就会终止，因为starter始终无法超过s.length，当starter到了s.length, 自然就终止了。他最终懂了，说是对的。这样就过了30分钟，我让他赶紧进下一个问题，他说没太多时间了，就不问了，各种瞎聊，我问了各种问题，从PhD的要求到谷歌的文化。最后实在没可聊的了，就让他出了一道题，我大致讲了一下方法。

Given A list of books in a library, sorted in a predefined order. Books have height {h1, h2, h3, …. hn} and assume all books have thickness 1.
Arrange them on bookshelves that can hold k books at most on each level. The height of each level is the max height of the books on that level.
Find out the minimum total height of all the bookshelves necessary to accommodate all books.

我大致讲了贪心算法和DP的思路，没时间了。他最后的评价是：Generally, what you did is ok. For future you still need more practice, for fulltime job.

第二轮上来的印度大哥口音实在是。。。他没一个问题我都要他写下来。

第一个问题：Write a function to return a copy of a list with duplicates removed.

我问了他好一些问题，比如是不是LinkedList, 还有这个list是不是sorted，还有比如11123，是删成123呢，还是23. 然后就是什么样算是Copy，把这些都搞清楚了之后，我给他讲了大致的方法：O（N），从前到后Scan，每次不重复就把node value存到一个HashSet里面，然后拷贝这个点到新的List里面，代码如下：

public Class ListNode {
    int val;
    ListNode next;
    ListNode (int x) {
    this.val = x;
    this.next = null;
}
} 


public ListNode copy(ListNode head) {
    if (head == null) return null;
    HashSet<Integer> set = new HashSet<Integer>();
    ListNode dummy = new ListNode(-1);
    ListNode cur = head;
    ListNode runner = dummy;
    while (cur != null) {
    if (set.contains(cur.val)) {
    cur = cur.next;
}
else {
    ListNode newNode = new ListNode(cur.val);
    runner.next = newNode;
    set.add(cur.val);
}
}
return dummy.next;
}

有点小错，比如23行，我忘了移runner了，不知道考官发现没有。这一轮状态不是太好，还有电面我不是太喜欢，不说话总感觉冷场，感觉没机会好好把问题分析透彻。他就问了个问题：Does it preserve the order of the original list? 我给他解释了。他说Java有的interface可以直接用，或者自己定义，我说我prefer自己定义的。

第二个问题：Find max of an strictly ascending then strictly descending array.

我先给了个O（N）的naive算法，他问能不能提高，我说可以用O（logN）类似binary search的方法，用 Recursion来做，每次取whole array的中点，取名a1, 把array一分为二，取前一个array的中点，取名a2, 后一个array的中点，取名a3. 然后比较a1,a2,a3大小关系：

1. 如果array[a1] > array[a2] && array[a1] > array[a3] (我开始的时候比较index去了，后来自己发现了，改了)，说明max在 a2, a3之间，下一次recursion进这个range

2. 如果array[a1] > array[a2] && array[a1] < array[a3], 说明max在a1右侧（我开始讲成a3右侧了，他让我再想想，我一下子反应过来了）

3. 如果array[a1] < array[a2] && array[a1] > array[a3], 说明max在a1左侧

这是我考场想到的情况所有情况，我问他怎么看，他think that's it. 电面果然不容易想清楚所有情况，下来想想，其实第2种情况应该是array[a1] > array[a2] && array[a1] <= array[a3]，第3种情况应该是array[a1] <= array[a2] && array[a1] > array[a3]，但是临场那种紧张情况下我确实想不到那么多细节了。临场写下的code如下：

public int FindMax(int[] array) {
    if(array == null || array.length < 2) return -1;
    return helper(array, 0, array.length-1);
}

public int helper(int[] array, int l, int r) {
    if (l >= r) return array[l];
    int a1 = (l + r) / 2;
    int a2 = (l + a1) / 2;
    int a3 = (a2 + r) / 2;
    if (array[a1] > array[a2] && array[a1] > array[a3]) {
    return helper(array, a2, a3);
}
else if (array[a1] > array[a2] && array[a1] < array[a3]) {
    return helper(array, a1, r);
}
else {
    return helper(array, l, a1);
}
}

第7行的停止条件最开始忘了，他问这个Recursion怎么停止，我才发现忘写base case，立马加上，在提醒下改正错误，不知道这扣不扣分。然后第3行s.length-1忘-1. 哎，小错不断啊。最后他让我举个例子推一推：

1 2 3 4 5 4 3 2 1 
0 1 2 3 4 5 6 7 8 

helper(0, 8)
a1 = 4     5
a2 = 2        3
a3 = 6        3

helper(2, 6);
a1 = 4        5
a2 = 3        4
a3 = 5        4

helper(3, 5)
a1 = 4        5
a2 = 3        4
a3 = 4        5

helper(3, 4)
a1 = 3
a2 = 3
a3 = 3

因为之前的=错误，我推到后面有点不对，正在想办法改，考官说

I'm sorry to cut the interview abruptedly. I didn't realized that I will lose the conference room at 3:45 sharp. Thank you for applying for Google. You should hear from your recruiter in a week or so. Have a nice day!

 好吧。。第一次用google doc电面，多少还是多少有点不适应。然后电面这种模式感觉没有面对面的时候更放得开思维广一点，有时候空对空更不容易跟面试官讲清楚自己的做法。总的来说，第一轮第一题应该没什么问题，第二题是我自己要来的，随便讲了讲思路，大致方向(greedy和DP应该是对的)。第二轮第一题忘了runner指向下一个了，不知道面试官发现没有（有时候就在想，他们发现问题了是跟你指出看你发现没有呢，还是嘴上不说心里默默记下该扣分了？）第二题想到这么多我也是尽力了，=的情况确实在当时那种心理状态下没想到无可厚非。以后还要加强这种Corner Case思考的训练。然后写的时候，出了两个小错，在他提醒下改正了。他最后的评价是：You did mostly correct.

哎，人事已尽，成败看天..祈祷