一亩三分地论坛

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

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

google 电面 29/11

[复制链接] |试试Instant~ |关注本帖
Hmoon 发表于 2016-11-30 04:15:24 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
因为住的地方邻居经常弄出很突然的响动,很担心面试的时候也出现这种响动,实际上也出现了,全程很紧张,没法静下心。。题目倒不难,可是离做出来很近了。。。
一开始说说她的经历,她在google search engine组,在google 工作了九年。然后问我我做过的project中最interesting的是什么。我说了我是做科学计算的,说了一大推,感觉她似乎也没听懂,沉默几秒钟后,她说她开始问题目了。首先问我知不知道binary search tree, 我说我知道。然后让我说定义,然后问我怎么找到 kth level 的最大值,我说最大值应该是rightmot的那个,可以用BFS,然后她问我还有什么办法,我想了想说可以用heap tree, 然后互相说了几句,发现不对,然后我又想了会儿,然后说可以用inoder tree traversal, 不过得先从右边,然后左边,她说可以,然后让我写代码,我问她写前面的,还是后面,她说了后面的。一开始用iterative 写了标准的inorder tree traversal 只不过从右边到左边,发现不行,然后问她可以用recursive 么。她说可以,然后写recursive,其实不难,写了一会儿,发现不对,然后交流,又该,还是不对,最后还是没弄出来,她说很close了。最后问了用什么tes case,我说两大类,一类depth 小于k ,另类不小于k, 不小于k的,一类最右边的是一个node right child, 另外一类不是。 题目不难,太紧张了。。


补充内容 (2016-11-30 04:18):-google 1point3acres
欢迎大家评价。。。。这个面试的在NY

评分

1

查看全部评分

catinclay 发表于 2016-11-30 04:22:44 | 显示全部楼层
是不是LC199?
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-11-30 04:25:04 | 显示全部楼层
感觉楼主inorder先右后左的思路是对的,就相当于从大到小排序,但是不是要同时记录下当前的层数?返回第一个层数为K的节点就好?
回复 支持 反对

使用道具 举报

 楼主| Hmoon 发表于 2016-11-30 04:25:38 | 显示全部楼层

还真是。。。不过DFS感觉比BFS难些。。。。后悔没多看leetcode上面题目
回复 支持 反对

使用道具 举报

 楼主| Hmoon 发表于 2016-11-30 04:27:43 | 显示全部楼层
WTYJack 发表于 2016-11-30 04:25
感觉楼主inorder先右后左的思路是对的,就相当于从大到小排序,但是不是要同时记录下当前的层数?返回第一 ...

我卡在如何识别k th level 上面,但愿她看在我的思路上面给我机会。。。。
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-11-30 04:29:25 | 显示全部楼层
Hmoon 发表于 2016-11-30 04:27. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我卡在如何识别k th level 上面,但愿她看在我的思路上面给我机会。。。。

BFS可以自己写个数据结构存Queue里,DFS直接把level当参数传下去就好吧,写起来应该还是DFS方便点儿
回复 支持 反对

使用道具 举报

 楼主| Hmoon 发表于 2016-11-30 04:31:37 | 显示全部楼层
WTYJack 发表于 2016-11-30 04:29
BFS可以自己写个数据结构存Queue里,DFS直接把level当参数传下去就好吧,写起来应该还是DFS方便点儿

我感觉BFS容易多了,要不然她也不会挑这个让我写。。。
回复 支持 反对

使用道具 举报

WTYJack 发表于 2016-11-30 04:56:54 | 显示全部楼层
Hmoon 发表于 2016-11-30 04:31
我感觉BFS容易多了,要不然她也不会挑这个让我写。。。

抱歉想错了。。应该是preorder的先右后左吧~祝好运啦!!
回复 支持 反对

使用道具 举报

 楼主| Hmoon 发表于 2016-11-30 05:00:56 | 显示全部楼层
WTYJack 发表于 2016-11-30 04:56
抱歉想错了。。应该是preorder的先右后左吧~祝好运啦!!
.鐣欏璁哄潧-涓浜-涓夊垎鍦
I think both are OK,  the key point is how to identify which level you are in...
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 00:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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