一亩三分地论坛

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

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

Google电面面经 9/2

[复制链接] |试试Instant~ |关注本帖
complete_46 发表于 2015-9-3 06:43:56 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚面完不久,应该是跪了. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
1 两大数相加,用数组表示的,不难 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

2 给一个树,看有没有相同的子树,如果有,找出位置.鏈枃鍘熷垱鑷1point3acres璁哄潧
我不会,也没听太明白面试官到底想要干吗,应该是跪了
讨论了一阵最后结果是:preorder inorder遍历两次,然后对某个node搞一个fingerprint出来,比较这些fingerprint,我还是没明白

评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| complete_46 发表于 2015-9-3 06:44:12 | 显示全部楼层
对了,求点米呀
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-3 07:01:13 | 显示全部楼层
啥意思呀第二个题,哪个大牛给解释下
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-9-3 07:44:09 | 显示全部楼层
同问第二题,求思路!!!
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-3 07:51:32 | 显示全部楼层
complete_46 发表于 2015-9-3 06:44 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
对了,求点米呀

楼主, 您的米都这么多了。。
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2015-9-3 07:56:50 | 显示全部楼层
第二题感觉可以对树做一次遍历,然后对应遍历的每一个node cur,做一次isSubtree(TreeNode root,TreeNode cur) 调用,找到另外一个包含在root 下并且与当前以cur为根节点的相同的子树,注意一下不要与cur重复。复杂度应该是n方吧。
回复 支持 反对

使用道具 举报

sosisarah 发表于 2015-9-8 12:40:41 | 显示全部楼层
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段 <node, preorder + inorder> , 每一个node 有唯一一个 fingerprint. 然后扔到hash表里判重就行了, 可以找出有多少个节点是重的, 最大的子树是多大.

复杂度O(n), n为 树中node的数目. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

fingerprint 之所以选择为 preorder+inorder, 因为这个可以唯一确定一棵树.
.1point3acres缃
补充内容 (2015-9-8 14:28):
可以对root的一次 preorder 和 inorder, 求出所有 node的 preorder和inorder, 记录一个time stamp, 详见<算法导论, DFS章节>
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-8 13:19:51 | 显示全部楼层
sosisarah 发表于 2015-9-8 12:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...

楼上的,感谢你的讨论哦,那对于每一个node做一次preorder + inorder, 感觉是o(n^2) 呀。感觉空间复杂度是o(n), 时间复杂度为o(n^2)
回复 支持 反对

使用道具 举报

sosisarah 发表于 2015-9-8 14:26:40 | 显示全部楼层
hbsophia 发表于 2015-9-8 13:19 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼上的,感谢你的讨论哦,那对于每一个node做一次preorder + inorder, 感觉是o(n^2) 呀。感觉空间复杂度 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个可以在对 root节点的一次 preorder 和 inorder中求出所有node的 preorder和inorder顺序的.
回复 支持 反对

使用道具 举报

rb131108 发表于 2015-9-9 11:30:28 | 显示全部楼层
sosisarah 发表于 2015-9-8 12:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
请问你说的inorder+preorder是把树inorder和preorder打印的结果吗?
然后以inorder+preorder做key?
回复 支持 反对

使用道具 举报

zq13667243992 发表于 2015-9-9 12:13:11 | 显示全部楼层
http://stackoverflow.com/questions/9507564/removing-duplicate-subtrees-from-binary-tree  可以用hash 达到O(n) 复杂度
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2015-9-9 13:50:09 | 显示全部楼层
sosisarah 发表于 2015-9-7 22:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...

有能运行的code能share一下吗?
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-9 15:06:08 | 显示全部楼层
luzhuzeng 发表于 2015-9-9 13:50
有能运行的code能share一下吗?

public class Solution {. visit 1point3acres.com for more.
        private boolean contains;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        private TreeNode node1, node2;
        
        public boolean SameSubTree(TreeNode root){
                if(root == null){
                        return true;
                }
               
                contains = false;. 1point 3acres 璁哄潧
                node1 = null;
                node2 = null;.1point3acres缃
               
                HashMap<List<Integer>, TreeNode> record = new HashMap<List<Integer>, TreeNode>();
                search(root, node1, node2, record);
               
                return contains;
        }
        
        private List<List<Integer>> search(TreeNode root, TreeNode n1, TreeNode n2, HashMap<List<Integer>, TreeNode> record){
                ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
               
                if(root == null){
                        res.add(new ArrayList<Integer>());
                        res.add(new ArrayList<Integer>());
                        return res;
                }
                . From 1point 3acres bbs
                List<List<Integer>> left = search(root.left, n1, n2, record);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                List<List<Integer>> right = search(root.right, n1, n2, record);
               
                List<Integer> inorder = new ArrayList<Integer>();-google 1point3acres
                List<Integer> preorder = new ArrayList<Integer>();
                List<Integer> key = new ArrayList<Integer>();
               
                inorder.addAll(left.get(0));. 1point 3acres 璁哄潧
                inorder.add(root.val);
                inorder.addAll(right.get(0));
               
                preorder.add(root.val);
                preorder.addAll(left.get(1));
                preorder.addAll(right.get(1));
               
                key.addAll(inorder);
                key.addAll(preorder);
               
                if(record.containsKey(key)){
                        contains = true;. Waral 鍗氬鏈夋洿澶氭枃绔,
                        node1 = record.get(key);
                        node2 = root;
                }
               
                record.put(key, root);
               
                res.add(inorder);
                res.add(preorder);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                return res;
        }
        
}

补充内容 (2015-9-9 15:06):
偷懒,用的list;如果真要达到O(n),改成String就可以了
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-9 15:06:36 | 显示全部楼层
坐看云起 发表于 2015-9-9 15:06
public class Solution {
        private boolean contains;
        private TreeNode node1, node2; ...

偷懒,用的list;如果真要达到O(n),改成String就可以了
回复 支持 反对

使用道具 举报

hzshuai 发表于 2015-9-9 16:06:57 | 显示全部楼层
这个相同子树的定义,除了结构相同,还要对应节点的值相同?
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-10 11:52:28 | 显示全部楼层
zq13667243992 发表于 2015-9-3 07:56
第二题感觉可以对树做一次遍历,然后对应遍历的每一个node cur,做一次isSubtree(TreeNode root,TreeNode c ...
. more info on 1point3acres.com
这种复杂度太高了吧,应该是n的三次方了
回复 支持 反对

使用道具 举报

luzhuzeng 发表于 2015-9-10 13:05:42 | 显示全部楼层
坐看云起 发表于 2015-9-9 01:06
偷懒,用的list;如果真要达到O(n),改成String就可以了

lz有个疑问,你相当于给每个node都存了属于它自己的preorder和inorder,这样算下来光空间就O(n^2)了,那么时间自然也至少是O(n^2); 比如你每次addall,不管是list也好还是string也好,不都要append上去吗?不都是O(n)吗每次?同时你用一整个list做key去hash,难道计算这个list的hash的时候是O(1)吗?我不清楚list的hash怎么做的,但是如果list很大很大(比如1mission),我们还能认为计算hash的时候是O(1)吗?我觉得计算hash也得是O(n)吧,因为你需要知道你的list都是什么。有很多疑问不明白,望指教,谢谢!
回复 支持 反对

使用道具 举报

rb131108 发表于 2015-9-10 20:06:23 | 显示全部楼层
luzhuzeng 发表于 2015-9-10 13:05
lz有个疑问,你相当于给每个node都存了属于它自己的preorder和inorder,这样算下来光空间就O(n^2)了,那么 ...

我也有个问题,不过我的问题是,这段代码每次都new一个key,那这个key和map里面的对应key应该不是一个object,hashfunction不work吧。


我觉得楼主的finger print 是说 inorder打印的string+postorder打印的string 吧
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-11 01:57:27 | 显示全部楼层
luzhuzeng 发表于 2015-9-10 13:05
lz有个疑问,你相当于给每个node都存了属于它自己的preorder和inorder,这样算下来光空间就O(n^2)了,那么 ...

确实有这方面的问题,之前说O(n),没有充分考虑拷贝的复杂度,换成String,应该也会有这个问题;
这种做法只能说是1 pass,不一定是O(n)了。。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 04:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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