Google onsite面经

Job Hunting Interview
, , , , ,
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

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