Google onsite面经

Job Hunting Interview
, , , , ,
12

我和他们说我有pending offer, 所以比较快。大概是面试完之后3天就联系我，同时进行team match，然后就是等所有面试成绩出来是7天后，大概成绩出来的同时就开始了team match

13

啊，team match完了，感觉都还不错。第一个组的manager感觉比较严肃，像是面试一样问了许多bq，并且一开始不告诉我他们组做什么，最后才介绍他们组。第二个组感觉更加随和一点，一直在和我介绍他们的工作。都是非常不错的组，能有这么一个机会也是非常的开心~最后选择了第二个组AdWords，总包裹大概17k左右

1 Like
14

是170K，少了个零吧

15

啊啊，是的，是170k，写错了，少了个0:joy:

16

adwords贡献谷歌80%的收入吧，cashcow

17

这个我也店面考到了，面的狗家电面，应该是白人小哥一上来就开始做题。恢复二叉树：即二叉树中多了一个edge，要求把这个edge找出来并且去掉。之前看的面经里这道题，面试官会给个follow up：现在树中多了不止一条edge，全部找出来并去掉。但是感觉无follow up的代码可以达到同样的效果？

18

楼主方便说下第三题是哪两种方法吗谢谢了

19

一种是 binary search 吧

20

对，优化解法就是用额外的map对每个key存历史上出现过的snapshot ids，这个ids 是递增的，因此可以binary search。
这里每个生成的snapshot存储的是与上个snapshot之间的put操作，也就是只存变化。另外删除操作需要用一个特定的object来表示，而不能用null。
第一种解法自然是存全量啦。

21

这题是一样的，描述差不多：

Google Snapshot。实现三个functions， get, set, take snapshots。其实就是一个长度为N的Array。Set可以设置Index i的值，每次take snapshot， version + 1，并且记录下当前version下 Array里面的值。然后get方法可以得到某一个Version下，每一个Index的Array的值

22

这题有很多细的follow up，比如怎么标记删除

23

这题就 DFS 解决，需要记下 visited 的node，注意有cycle 的case，另外需要maintain 一个map，key 是 child node， value 是它的parent。
binary tree的话两个edge随便选一个即可， BST 的话必须选的那个删除后还能保证 BST 的属性。

24 
class removeNode{
    TreeNode removeNode(TreeNode root){
        helper(null, root, new HashSet<>(), false);
        return root;
    }
    boolean helper(TreeNode parent, TreeNode root, Set<TreeNode> check, boolean left) {
        if (root == null)
            return false;
        if (check.contains(root)) {
            if (left) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            return true;
        }
        check.add(root);
        return helper(root, root.left, check, true) || helper(root, root.right, check,false);
    }
}
25

Mr. X, where can I find this video?

26

3月份上海onsite时候也面到了这道题，刚看到很懵逼，思考方向是对的但始终没有总结出方案。面试官给出hint才理清思路。这轮只解出1题，发挥很差。在紧张时没能冷静下来理清思路是很大问题。
楼上提到这题有两种解法，不过用数组全量保存的解法很不高效，不算一种可行解法吧。
贴一下map优化的方法，这个符合面试官期望：

class Snapshot {
public:
    Snapshot(int capacity, vector<int> vec) {
        _sid = 0;
        _size = capacity;
        _vec = vector<int>(capacity);
        _records = vector<map<int, int>> (capacity, map<int, int>());
        for (int i = 0; i < vec.size(); ++i) {
            set(i, vec[i]);
        }
    }

    int get(int key) {
        return get(key, _sid);
    }

    void set(int key, int value) {
        _records[key][_sid] = value;
        _vec[key] = value;
    }

    int snapshot() {
        return _sid++;
    }

    int get(int key, int snapshotid) {
        if (snapshotid > _sid)
            return -1;
        auto records = _records[key];
        return records.lower_bound(snapshotid)->second;
    }

private:
    int _sid;
    int _size;
    vector<int> _vec;
    vector<map<int, int>> _records;
};

int main() {
    int capacity = 4;
    vector<int> vec = vector<int> (capacity, 0);
    Snapshot snapshot = Snapshot(capacity, vec);

    snapshot.set(1, 1);
    snapshot.set(1, 2);
    int sid1 = snapshot.snapshot();
    snapshot.set(1, 5);
    cout << snapshot.get(1, sid1) << endl;
    cout << snapshot.get(1) << endl;
    return 0;
}
27

binary search的解法才是最优解

28

老师您好，不太明白为什么要binary search。既然可以用Map<“key”, List<“latest values of every version”>>, 为什么不能直接用list.get(versionID)拿到某一个snapshot的value呢？

29

这题的详细解答在 Google Interview Question Collection 已经收录了
你说的是 brutal force的解法，在space usage上不够优化。 binary search 的解法其实是正解

30

收录在那一課，我都找不到？

31

你微信上私信我吧，我告诉你