一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1592|回复: 23
收起左侧

[算法题] Google 面經求問

[复制链接] |试试Instant~ |关注本帖
frank11118 发表于 2016-7-17 13:25:34 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x




1. Given a binary tree, find if there are two subtrees that are the same. (i.e. the tree structures are the same; the values on all corresponding nodes are the same). You should find the largest subtree and don’t use brute force.




我只想到 brute-force,或是用 Map 存整個第一棵樹再掃第二顆做比較,想請問有沒有更好的想法?




2. Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array                                         




目前我是用 merge k sorted lists 來解,也是想討論有沒有更好的解法


感謝!


评分

1

查看全部评分

本帖被以下淘专辑推荐:

hxtang 发表于 2016-7-18 02:19:44 | 显示全部楼层
第一题讲个思路吧。

假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照group在后序遍历中第一次出现的时间顺序决定。
这样我们可以一边后序遍历子树,一边建两个hashmap:
(root value, group id of left, group id of right) -> group id of root
group id -> subtrees of this group
这样我们做一遍后序遍历同时维护层数最高、subtree数量>=2的group id就行了。

这个其实跟用整棵子树的serialization作为key做法差不多,只是对key作了压缩。

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

pushazhiniao 发表于 2016-8-13 04:19:36 | 显示全部楼层
本帖最后由 pushazhiniao 于 2016-8-13 04:22 编辑

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

musteryu 发表于 2016-7-17 16:23:14 | 显示全部楼层
本帖最后由 musteryu 于 2016-7-17 18:20 编辑

第二题可不可以用小根堆来做?最右下角为小根堆的根节点,每个结点的左侧和上侧结点为该结点的左右子结点。然后不断输出并删除根节点,维护小根堆应该就可以了。
对于M*N的矩阵,树的深度为Depth ≤ M+N,每次维护的复杂度为≤O(log(Depth)),总的复杂度 <O((M*N) * log(Depth))。

merge k sorted lists的最大复杂度有可能为O(M*M*N)
回复 支持 反对

使用道具 举报

 楼主| frank11118 发表于 2016-7-18 02:51:42 | 显示全部楼层
hxtang 发表于 2016-7-18 02:19
第一题讲个思路吧。

假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照 ...

感謝分享! 但有點深奧啊 ><...
請問您的 group id 是一個 len = 3 的 array 嗎?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-18 03:23:25 | 显示全部楼层
frank11118 发表于 2016-7-18 02:51
感謝分享! 但有點深奧啊 >

不是。group id就是一个数字,对应一棵unique的子树。
比如一棵3个结点的树,根结点是10, 两个node是20, 20.
那么group id->node的hash table存的是
0: NULL
1: leftnode, right node
2: root node

(root val, left id, right id)->root id的hashtable存的是
(20, 0, 0) : 1
(10, 1, 1) : 2

所以返回group id 1下面的两个node.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-18 03:58:35 | 显示全部楼层
musteryu 发表于 2016-7-17 16:23
第二题可不可以用小根堆来做?最右下角为小根堆的根节点,每个结点的左侧和上侧结点为该结点的左右子结点。 ...

用heap做merge k sorted list的复杂度好像是O(log(M) MN)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| frank11118 发表于 2016-7-21 13:31:39 | 显示全部楼层
hxtang 发表于 2016-7-18 03:23
不是。group id就是一个数字,对应一棵unique的子树。
比如一棵3个结点的树,根结点是10, 两个node是20 ...

了解了!
好方法,感謝分享
回复 支持 反对

使用道具 举报

zhihaosun 发表于 2016-7-21 14:21:36 | 显示全部楼层
第一题想到一个有趣的解法,把Tree用DFS做serialization , 就变成了找substring的问题了,可以用kmp或者直接用内置方法做吧
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-21 15:57:55 | 显示全部楼层
第一题可不可以求每个节点的后续遍历然后用1个hashmap比较
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-21 19:38:20 | 显示全部楼层
jy_121 发表于 2016-7-21 15:57
第一题可不可以求每个节点的后续遍历然后用1个hashmap比较

树规模大了以后hashmap的key会越来越长。虽然hit到对应的hashkey可能还是O(1)的,但是应该还是得比较两个key是不是确实一样,这个比较是O(n)的。
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-7-22 14:18:36 | 显示全部楼层
hxtang 发表于 2016-7-21 19:38
树规模大了以后hashmap的key会越来越长。虽然hit到对应的hashkey可能还是O(1)的,但是应该还是得比较两个 ...

有道理,多谢
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-7-24 12:02:19 | 显示全部楼层
本帖最后由 greentrail 于 2016-7-24 19:37 编辑

第一题,返回相同最大相同子树的节点数。简单测了一下。
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了。
回复 支持 反对

使用道具 举报

burself 发表于 2016-8-11 23:22:15 | 显示全部楼层
zhihaosun 发表于 2016-7-21 14:21
第一题想到一个有趣的解法,把Tree用DFS做serialization , 就变成了找substring的问题了,可以用kmp或者直 ...

握手。我也是这么想的。参考pre-order遍历序列化一棵二叉树。然后build这个字符串的失败函数。假设某字符的失败函数值为最大,且这个子串不以空开头,即为最大重复子树。
不知道是不是正解?能不能举出反例?
回复 支持 反对

使用道具 举报

jefferyy 发表于 2016-8-13 02:22:54 | 显示全部楼层
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 很相似
回复 支持 反对

使用道具 举报

mnmunknown 发表于 2016-8-13 02:37:27 | 显示全部楼层
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,但是树的结构不同。
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-13 04:25:42 | 显示全部楼层
本帖最后由 pushazhiniao 于 2016-8-13 04:39 编辑

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就够了
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-13 04:34:37 | 显示全部楼层
mnmunknown 发表于 2016-8-13 02:37
应该不行,只靠 pre-order 不能定义一个独立的 tree,至少需要加上 in-order.

比如,          1      ...

可以,参考https://leetcode.com/problems/se ... ialize-binary-tree/
回复 支持 反对

使用道具 举报

 楼主| frank11118 发表于 2016-8-13 04:46:39 | 显示全部楼层
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 應該是一樣的吧?
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-13 08:52:30 | 显示全部楼层
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里的元素个数变化
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 16:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表