一亩三分地论坛

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

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

Google刚出炉的面经

[复制链接] |试试Instant~ |关注本帖
jerry_lin324 发表于 2016-4-21 05:41:36 | 显示全部楼层 |阅读模式

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

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

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

x
刚面完一波google,速度来发帖赞人品。
面试官是老美,Android组的,声音好沙哑,刚开始一直听不清他说啥。讲道理应该先聊聊简历寒暄寒暄,问候完他直接上题。题并不难,只不过我刚开始有点懵逼,有点犯傻,没进入状态。


1. Binary tree lowest common ancester. lowest common ancester他是定义为longest path from a leaf to the root,貌似和leetcode那个题不太一样。
我一上来用的方法写到一半觉得写不下去。果断说我换个更直白的方法,把所有path都记录下来,然后返回最长path的最后一个node。写的过程中,他说我的第一个方法对着呢为啥不写完呢,我说先把这个写完再写那个。第一个方法就是不断更新path的长度,然后更新相对应的那个node。最后两种方法都写了,他说perfect,我们来下一个。

2. 你有 10^12个short integer,然后找出largest top100。最直白的方法就是用heap,分分钟完成。然后我想当然的说可以用hashmap,因为short integer 大概范围是-32000~32000,差不多64000个数,然后怎么弄key-value我不太清楚。他说heap is perfect enough,hashmap这个key-value pair不太好搞 - -。第二题就这么结束了。. 1point 3acres 璁哄潧

感觉老美面试还是稳,题比三哥简单。但是自己刚开始有点懵逼,表现的不太好,希望不要受到影响,求Onsite

评分

1

查看全部评分

本帖被以下淘专辑推荐:

adiggo 发表于 2016-4-21 06:02:49 | 显示全部楼层
楼主 第一题 和 leetcode lca 有什么区别么。。
回复 支持 反对

使用道具 举报

 楼主| jerry_lin324 发表于 2016-4-21 06:05:08 | 显示全部楼层
adiggo 发表于 2016-4-21 06:02. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主 第一题 和 leetcode lca 有什么区别么。。

我没太看leetcode那个题,不太清楚噢
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-21 06:20:05 | 显示全部楼层
(所以这个第一题,是让干什么。。。。。。。)
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-4-21 08:09:04 | 显示全部楼层
讲道理楼主是ob粉丝吧。。。
回复 支持 反对

使用道具 举报

 楼主| jerry_lin324 发表于 2016-4-21 08:15:11 | 显示全部楼层
ykwwind 发表于 2016-4-21 06:20
(所以这个第一题,是让干什么。。。。。。。)

说白了,就是找最长路径上的那个叶子节点,感觉跟LCA没啥关系。
回复 支持 反对

使用道具 举报

 楼主| jerry_lin324 发表于 2016-4-21 08:16:03 | 显示全部楼层
caiqi8877 发表于 2016-4-21 08:09
-google 1point3acres讲道理楼主是ob粉丝吧。。。

兄弟这都能看出来
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-21 08:30:05 | 显示全部楼层
jerry_lin324 发表于 2016-4-21 08:15
说白了,就是找最长路径上的那个叶子节点,感觉跟LCA没啥关系。

囧..............
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-4-21 08:59:53 | 显示全部楼层
jerry_lin324 发表于 2016-4-21 08:15. visit 1point3acres.com for more.
说白了,就是找最长路径上的那个叶子节点,感觉跟LCA没啥关系。

意思就是BFS, 最后一层的点?
回复 支持 反对

使用道具 举报

kiviljc 发表于 2016-4-21 10:13:37 | 显示全部楼层
第一题是找最长path吧?
回复 支持 反对

使用道具 举报

Mark6 发表于 2016-4-21 10:34:07 | 显示全部楼层
第二题有没有类似快排的方法,把最大的一百个放到最后,然后前面的不管。这样好像趋近与O(n)?不是很清楚,求大神指导。。
回复 支持 反对

使用道具 举报

waikai 发表于 2016-4-21 13:32:01 | 显示全部楼层
Mark6 发表于 2016-4-21 10:34
第二题有没有类似快排的方法,把最大的一百个放到最后,然后前面的不管。这样好像趋近与O(n)?不是很清楚 ...

感觉,既然告诉了数值范围,而且10^12次方远大于这个范围。考虑BucketSort会好一点。heap的话需要的空间太大,桶排序开2个byte就行。由于数很多,可能最大值很快就充满了top100。这种情况桶排序也可以提前结束。复杂度大概率小于n
回复 支持 反对

使用道具 举报

 楼主| jerry_lin324 发表于 2016-4-21 21:00:41 | 显示全部楼层
ykwwind 发表于 2016-4-21 08:59
意思就是BFS, 最后一层的点?

对,但是要最长path上面那个leaf
回复 支持 反对

使用道具 举报

 楼主| jerry_lin324 发表于 2016-4-21 21:01:27 | 显示全部楼层
kiviljc 发表于 2016-4-21 10:13
第一题是找最长path吧?

嗯啊,就是找到最长path然后返回这条path上面那个leaf节点
回复 支持 反对

使用道具 举报

oh_yee 发表于 2016-4-21 23:15:04 | 显示全部楼层
waikai 发表于 2016-4-21 13:32
感觉,既然告诉了数值范围,而且10^12次方远大于这个范围。考虑BucketSort会好一点。heap的话需要的空间 ...

请问, 能详细讲一下如何用BucketSort做这题吗? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

谢谢啦!
回复 支持 反对

使用道具 举报

Crystal_yy 发表于 2016-4-23 02:50:31 | 显示全部楼层
请问第一题题目是肯定只有一个点么?还有有可能有多个叶子节点,只要返回一个就可以了
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-20 02:20:31 | 显示全部楼层
如果 用int来存这10^12个数的话 每个数是4 bytes 这么多数得4000G内存才能放得下…………
回复 支持 反对

使用道具 举报

jjustc 发表于 2016-6-20 02:29:28 | 显示全部楼层
即使不用int 32000这个数也差不多得用16位才能存下 那也是2个bytes 那也是 2^12 / 10^3 / 10^3 / 10^3 = 2000GB内存……如果 用Heap 得把所有数都放到heap里,这样内存吃不消 所以还是得用bucket sort,有比较大的概率 提前终止。
回复 支持 反对

使用道具 举报

pengpengche 发表于 2016-6-26 03:06:09 | 显示全部楼层
我感觉第二题,做个priorityQueue,每次size()过一百了,poll()个数出来不就行了?这个为什么不行啊,求大神指教
回复 支持 反对

使用道具 举报

pengpengche 发表于 2016-6-26 03:31:54 | 显示全部楼层
pengpengche 发表于 2016-6-26 03:06
我感觉第二题,做个priorityQueue,每次size()过一百了,poll()个数出来不就行了?这个为什么不行啊,求大 ...

好啊,还是桶排序好。。。。。。我是sb
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 20:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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