Google 面經求問

hxtang 发表于 2016-7-21 19:38
树规模大了以后hashmap的key会越来越长。虽然hit到对应的hashkey可能还是O(1)的，但是应该还是得比较两个 ...

有道理，多谢

第一题，返回相同最大相同子树的节点数。简单测了一下。
int identicalSubtree(TreeNode * root) {
        unordered_map<int, int> map;
        string out;
        int num = 0, n = 0;
        
        search(root, out, map, n, num);
        return num;
}

void search(TreeNode * root, string & out, unordered_map<int, int> & map, int & n, int & maxnodes) {
        if (!root) {            out.append("# ");
            return;
        }
        string seq;
        int leftn = 0, rightn = 0;
        search(root->left, seq, map, leftn, maxnodes);
        search(root->right, seq, map, rightn, maxnodes);

        n = leftn + rightn + 1;
        seq.append(to_string(root->val) + " ");
        out.append(seq);

        int h = hash<string>()(seq);
        if (map.count(h) == 0) {
                map[h] = n;
        }
        else maxnodes = max(maxnodes, map[h]);
}

Update:
有个小bug，fix了。

Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array   
这个题和leetcode的Kth Smallest Element in a Sorted Matrix 很相似

burself 发表于 2016-8-11 23:22
握手。我也是这么想的。参考pre-order遍历序列化一棵二叉树。然后build这个字符串的失败函数。假设某字 ...

应该不行，只靠 pre-order 不能定义一个独立的 tree，至少需要加上 in-order.

比如，          1         和             1
                  /                         /   \
                2                         2     3
              /
            3

的 pre-order 都是 1-2-3，但是树的结构不同。

第二题参考这题做法建heap
https://leetcode.com/problems/kt ... in-a-sorted-matrix/

dfs或者bfs都可以定义一棵树，参考这题
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/只需要none节点用#或者什么特别字符表示即可，如果不表示none节点才不能只用preorder（也就是dfs）

如
1,2,3,#,#,#,#和
1,2,#,#,3,#,#是不一样的

感觉第一题就是set加树serialization
后序遍历的过程中，对于每个根节点做serialization（利用其左右已经序列好的来省时间），以serialized string为id，如果遇到相同的就返回True，不需要hashmap，set就够了

mnmunknown 发表于 2016-8-13 02:37
应该不行，只靠 pre-order 不能定义一个独立的 tree，至少需要加上 in-order.

比如，          1      ...

可以，参考https://leetcode.com/problems/se ... ialize-binary-tree/

pushazhiniao 发表于 2016-8-13 04:19
第二题参考这题做法建heap
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

感謝！
但建 heap 的複雜度也是 O(nlgn)
複雜度跟 merge k sorted list 應該是一樣的吧？

frank11118 发表于 2016-8-13 04:46
感謝！
但建 heap 的複雜度也是 O(nlgn)
複雜度跟 merge k sorted list 應該是一樣的吧？

worst case是一样的 但是average case 总左上角跑到右下角还是不一样

merge k sorted list：n一直都是matrix的边长
而从matrix左上角跑到右下角每次pop并放入下一个，heap只在正中间的时候是matrix的边长，其他时候都小于

你可以想象从matrix的左边横着跑到右边heap里放的元素个数，再想从matrix的左上跑到右下heap里的元素个数变化