一亩三分地论坛

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

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

08/29 谷歌电面 心路历程求米!

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

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
8月29号的第一轮电面,一位俄罗斯phd, 来迟了几分钟,发现开始给我的google doc不好使,于是面试官要了我邮箱发来了链接。

就面了一题,给一个树,要输出所有重复的子树,包括叶子。 其实这题在15年的面经有,面试完了才知道,当时的想法是:又遇到没做过的题了。当时虽然想到leetcode其他相关的题比如same tree, symmetric tree等,发现都不一样,就硬着头皮说first thinking就是把每个节点都hash到hashmap里边,要找到这样一个hash要保证,1-1对应。然后就想到leetcode有道看见过但是没做过的serialize tree, deserialize tree(leetcode刷了300多题,这题还没刷到),就说我写个serialize tree 吧,把每个节点都serialize了,遍历一遍,然后两相比较。我就先写了一个pre-order traversal serialize tree, 中间有小bug也被面试官指出来了,比如点之间我没加分隔符比如" "(还是当时紧张了,要吸取教训。)。面试官说你这样貌似很expensive啊,我心里想是啊,那怎么整,就自己想一个recursive的做法,因为是树的题嘛,写了五分钟,就卡住了,面试官人好,提示我,你之前写的那个serialize tree有可能得到一个比较好的答案的,你再去看看。 我就回去一看是啊,开始建立一个hashmap(dictionary), 在递归建立serialization的时候其实就可以同时查现在的结果是不是已经在hashmap里了。很快就写完了,毕竟代码没多少。面试官问,你这是哪种traversal,我说这是preorder, 然后他问别的traversal行不行,我就说inorder 和post 应该都行,as long as you can deserialize to the original tree. 现在想想这个说法没毛病,但是如果做了Leetcode那道题,其实就知道pre 和post容易deserialize, in order 不太好搞,就可以点出来这个了。anyway, 面试官说好,然后又问那你给出一些test cases吧,我就把什么complete tree, imbalance tree(left or right heavy), symmetric tree 等等念叨了一遍。又问,如果left heavy, 你分析一下不同traversal的区别,我就分析了一下dfs, bfs区别,然后说但是那是search, 如果这道题其实不管怎么都要看全部的,速度没差别。 面试官说那单位时间找到的多呢,我说那就用先搜left child的traversal。 看就剩下十分钟了,面试官就让我问问题,然后问了我简历里边的一个project,感觉面试官还挺用心的。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

因为只做了一道题比较忐忑,第二天HR发email说约时间打电话quick update on your interview process 要share feedback, 我心里就开始琢磨怎么现在拒人还要预约电话了?这是到下一步了还是谢谢再见了呢?

. 1point 3acres 璁哄潧然后今天下午接电话先问了下我对面试官的feedback,我就把面试官表扬了一番,然后她说i'm glad that the feedbacks are good --- on both ends. 才知道可以约onsite了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
写下这些造福一下论坛,也算是还原一下这个过程,希望看到的同学少犯低级失误,大家有加油!

评分

1

查看全部评分

mooc 发表于 2016-9-1 07:27:50 | 显示全部楼层
同学,怎么定义重复的子树啊?
         1
      2      3
   4    5 4    5 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这棵树有重复子树吗?
回复 支持 反对

使用道具 举报

 楼主| Ridingstar01 发表于 2016-9-1 07:30:07 | 显示全部楼层
mooc 发表于 2016-9-1 07:27
同学,怎么定义重复的子树啊?
         1
      2      3
. 1point3acres.com/bbs
4 和4重复,5和5重复,定义就是两个树一样就是重复的。
回复 支持 反对

使用道具 举报

mooc 发表于 2016-9-1 07:35:58 | 显示全部楼层
那如果是
      1
   2      2
  3 4   5 6
呢?
2有重复,但其子树并不重复,能算吗?
回复 支持 反对

使用道具 举报

 楼主| Ridingstar01 发表于 2016-9-1 08:05:17 | 显示全部楼层
mooc 发表于 2016-9-1 07:35
那如果是
      1. more info on 1point3acres.com
   2      2

必须整个sub tree都一样才算重复的
回复 支持 反对

使用道具 举报

Tsien 发表于 2016-9-4 05:24:15 | 显示全部楼层
LZ是用一个hashmap保存pre-order的结果吗?
我觉得光pre-order结果相同不一定能保证两个subtree完全相同,e.g.,
      1             1
     /                \
    3                  3
这两个的pre-order结果都是13,但他们并不相同。对于in-order 和 poster-order也一样有反例。
回复 支持 反对

使用道具 举报

burning_k 发表于 2016-9-4 05:44:15 | 显示全部楼层
Tsien 发表于 2016-9-4 05:24
LZ是用一个hashmap保存pre-order的结果吗?
我觉得光pre-order结果相同不一定能保证两个subtree完全相同, ...

要存null
回复 支持 反对

使用道具 举报

Tsien 发表于 2016-9-4 06:10:32 | 显示全部楼层
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
ok, got it!
Thx~
回复 支持 反对

使用道具 举报

 楼主| Ridingstar01 发表于 2016-9-4 06:12:32 | 显示全部楼层
Tsien 发表于 2016-9-4 06:10
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴ok, got it!
Thx~
. from: 1point3acres.com/bbs
恩 None 存成特殊字符 详情可以看下leetcode serialize deserialize那道题。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 22:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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