要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
系统
14秒前
系统
17秒前
系统
42秒前
系统
1分钟前
全站
Warald 说: MemorialDay大礼包之二:【新功能】论坛开启用户全局威望值,每楼右上方均可投票。
27分钟前
全站
Warald 说: MemorialDay大礼包之一:【新功能】发帖后,可以邀请朋友参与讨论(自动功能)
34分钟前
查看: 2803|回复: 20
收起左侧

Google电面面经 9/2

[复制链接] |试试Instant~ |关注本帖
我的人缘0
complete_46 发表于 2015-9-3 06:43:56 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

x
刚面完不久,应该是跪了
1 两大数相加,用数组表示的,不难

2 给一个树,看有没有相同的子树,如果有,找出位置.本文原创自1point3acres论坛
我不会,也没听太明白面试官到底想要干吗,应该是跪了
讨论了一阵最后结果是:preorder inorder遍历两次,然后对某个node搞一个fingerprint出来,比较这些fingerprint,我还是没明白. visit 1point3acres for more.

评分

3

查看全部评分


上一篇:uber 7月,8月 高频考题
下一篇:Bloomberg Onsite 两轮游。。。。

本帖被以下淘专辑推荐:

我的人缘0
 楼主| complete_46 发表于 2015-9-3 06:44:12 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
对了,求点米呀
回复 支持 反对

使用道具 举报

我的人缘0
hbsophia 发表于 2015-9-3 07:01:13 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
啥意思呀第二个题,哪个大牛给解释下
回复 支持 反对

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-9-3 07:44:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
同问第二题,求思路!!!
回复 支持 反对

使用道具 举报

我的人缘0
hulahu 发表于 2015-9-3 07:51:32 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
-google 1point3acres
楼主, 您的米都这么多了。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
sosisarah 发表于 2015-9-8 12:40:41 | 显示全部楼层
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段 <node, preorder + inorder> , 每一个node 有唯一一个 fingerprint. 然后扔到hash表里判重就行了, 可以找出有多少个节点是重的, 最大的子树是多大.
. 1point3acres. Waral 博客有更多文章,
复杂度O(n), n为 树中node的数目.

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

使用道具 举报

我的人缘0
hbsophia 发表于 2015-9-8 13:19:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
sosisarah 发表于 2015-9-8 12:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...

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

使用道具 举报

我的人缘0
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顺序的.
回复 支持 反对

使用道具 举报

我的人缘0
rb131108 发表于 2015-9-9 11:30:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
sosisarah 发表于 2015-9-8 12:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...

请问你说的inorder+preorder是把树inorder和preorder打印的结果吗?
然后以inorder+preorder做key?
回复 支持 反对

使用道具 举报

我的人缘0
zq13667243992 发表于 2015-9-9 12:13:11 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
http://stackoverflow.com/questions/9507564/removing-duplicate-subtrees-from-binary-tree  可以用hash 达到O(n) 复杂度
回复 支持 反对

使用道具 举报

我的人缘0
luzhuzeng 发表于 2015-9-9 13:50:09 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
sosisarah 发表于 2015-9-7 22:40
我觉得第二题的做法是  对树做一次 preorder 和inorder 的遍历,然后对每一个节点记录下面一个字段  , 每一 ...

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

使用道具 举报

我的人缘0
坐看云起 发表于 2015-9-9 15:06:08 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
luzhuzeng 发表于 2015-9-9 13:50
有能运行的code能share一下吗?

public class Solution {
        private boolean contains;
        private TreeNode node1, node2;
        . 一亩-三分-地,独家发布
        public boolean SameSubTree(TreeNode root){
                if(root == null){
                        return true;
                }. 1point3acres
               
                contains = false;.留学论坛-一亩-三分地
                node1 = null;
                node2 = null;
               
                HashMap<List<Integer>, TreeNode> record = new HashMap<List<Integer>, TreeNode>();
                search(root, node1, node2, record);
               
                return contains;. 留学申请论坛-一亩三分地
        }. Waral 博客有更多文章,
        
        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;. visit 1point3acres for more.
                }
               
                List<List<Integer>> left = search(root.left, n1, n2, record);
. 1point 3acres 论坛                List<List<Integer>> right = search(root.right, n1, n2, record);
                . Waral 博客有更多文章,
                List<Integer> inorder = new ArrayList<Integer>();
                List<Integer> preorder = new ArrayList<Integer>();
                List<Integer> key = new ArrayList<Integer>();
               
                inorder.addAll(left.get(0));. 一亩-三分-地,独家发布
                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;
                        node1 = record.get(key);
                        node2 = root;
                }
               
                record.put(key, root);
               
                res.add(inorder);
                res.add(preorder);-google 1point3acres
                return res;. From 1point 3acres bbs
        }
        
}. 留学申请论坛-一亩三分地
. From 1point 3acres bbs
补充内容 (2015-9-9 15:06):
偷懒,用的list;如果真要达到O(n),改成String就可以了
回复 支持 反对

使用道具 举报

我的人缘0
坐看云起 发表于 2015-9-9 15:06:36 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
坐看云起 发表于 2015-9-9 15:06
public class Solution {
        private boolean contains;
        private TreeNode node1, node2; ...

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

使用道具 举报

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

使用道具 举报

我的人缘0
zzwzhong698800 发表于 2015-9-10 11:52:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
zq13667243992 发表于 2015-9-3 07:56. Waral 博客有更多文章,
第二题感觉可以对树做一次遍历,然后对应遍历的每一个node cur,做一次isSubtree(TreeNode root,TreeNode c ...

这种复杂度太高了吧,应该是n的三次方了
回复 支持 反对

使用道具 举报

我的人缘0
luzhuzeng 发表于 2015-9-10 13:05:42 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
坐看云起 发表于 2015-9-9 01:06. From 1point 3acres bbs
偷懒,用的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都是什么。有很多疑问不明白,望指教,谢谢!
回复 支持 反对

使用道具 举报

我的人缘0
rb131108 发表于 2015-9-10 20:06:23 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
luzhuzeng 发表于 2015-9-10 13:05
lz有个疑问,你相当于给每个node都存了属于它自己的preorder和inorder,这样算下来光空间就O(n^2)了,那么 ...

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

. 围观我们@1point 3 acres
我觉得楼主的finger print 是说 inorder打印的string+postorder打印的string 吧
回复 支持 反对

使用道具 举报

我的人缘0
坐看云起 发表于 2015-9-11 01:57:27 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
luzhuzeng 发表于 2015-9-10 13:05
lz有个疑问,你相当于给每个node都存了属于它自己的preorder和inorder,这样算下来光空间就O(n^2)了,那么 ...
. 牛人云集,一亩三分地
确实有这方面的问题,之前说O(n),没有充分考虑拷贝的复杂度,换成String,应该也会有这个问题;
这种做法只能说是1 pass,不一定是O(n)了。。。。
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 13:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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