一亩三分地论坛

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

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

谷歌11.12 11.13两次电面面经

[复制链接] |试试Instant~ |关注本帖
hackerpainter 发表于 2015-11-14 04:36:28 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
热乎乎的面经,刚刚结束十分钟不到这两天的面试可以说是有运气好,也有不好的成分,表现的话,差强人意吧……在地理看了这么久的面经,特地过来分享一下,顺便攒攒人品.鐣欏璁哄潧-涓浜-涓夊垎鍦
一面
国人大哥,很nice啊
1.find duplicate number
-google 1point3acresfollow up:有没有其他办法?我第一反应是O(nlogn)的做法,但是那个做法需要排序,所以我就说如果排序的,我有办法。面试官后来听我讲了半天,说其实只要看adjacent number就可以了……我真的想一头撞墙上
follow up:如果是一个stream的输入,怎么做?提示是不用100%正确率。答曰:bloom filter。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
bloom filter是我前面做项目的时候用到的方法,当时还看了很多参考资料,印象非常之深刻,所以回答的很清晰。
应该是我把这个经历写到了resume里面,这位国人大哥才会这么问。由此可见,大家在resume上面也不能都是乱吹的……如果真的不小心遇到了人家会的,问倒了就尴尬了
2.find duplicate number,但是这里要求是在某一个范围k内的
最naive的想法,每次遇到一个点,在k区间内找一下
follow up: 有没有更好的办法?提示时间复杂度是O(nk),但是可以变成O(n)的
然后我才想到 sliding window, two pointers
3.find close number,还是要求范围k内,close的定义就是,两个数字的差的绝对值小于等于某个数d
继续naive想法,每次加一个数字的时候,我把[arr[i]-k, arr[i]+k]内所有的数字都给测一遍,每次删除一个数字的时候也一样
follow up: 有没有更好的办法,提示之后我说可以用平衡树做,但是没想到java里的TreeMap是红黑树,也是被提示的。提示之后我才想到了有ceiling()和flooring()

一面面完之后感觉,谷歌的面试很灵活
eetcode切完了不代表一切啊,binary search,brute force,bfs/dfs,dp,two pointers,divide and conquer,这些算法的想法更应该掌握,而不能仅仅是题目
下面等二面……但是说好的背靠背,面试官不见了,打了个电话,预约到了第二天上午……其实是中午……我一会儿还有个FB的面试……


二面
是一个很有趣中国妹子,开始那个妹子在等meeting room,等的时候和我在google doc上面聊了一会儿。而且声音还很甜,非常提神(我这里是下午一点,最困的时候)。可惜的是通话噪声很大,导致很多时候没法听清。
1. plus one
2. 10进制转16进制
lz这里开始卡住了……真的是……以前搞ACM最怕的就是这种边界情况特别难整的,加一减一之类的。所以binary search一直是我的痛……

在妹子的提示下完成了debug……时间已经不多了……:(. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个时候妹子很善解人意的说,你可以问问题了……是我傻……非要和人家说,再来一道……
3. 最后一道我感觉地理见到过,是导弹系统。把模型抽象出来就是,给你一个int[]数组,让你找最少的increasing sequence number.
从正面找 #increasing sequences的问题,可以转化为 反面找LIS的问题,具体证明可以看Dilworth定理
其实我一直很好奇如果不知道Dilworth定理的小伙伴遇到这种题目怎么办……
最后看了通话时间是46min,没来得及问问题就结束了。因为昨晚的诡异遭遇,所以今天还临时安排面试、耽误人家休息时间面试真的很不好意思。lz在此只能说好人一生平安!
同时非常感谢recruiter的reschedul,继续好人一生平安!

最后求大米~求大米~求大米~求offer~求offer~求offer~

评分

3

查看全部评分

stormy1991 发表于 2015-11-14 04:58:29 | 显示全部楼层
lz加油,马上就有offer了!话说G家实习面试都是背靠背的么?
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-14 05:42:37 | 显示全部楼层
lz能不能说一下找最少的increasing sequence number的详细解法?谢谢!
回复 支持 反对

使用道具 举报

fillchar 发表于 2015-11-14 06:00:40 | 显示全部楼层
一面第三题可以用线段树做我觉得,leetcode上应该有这题…
回复 支持 反对

使用道具 举报

lcl3356897 发表于 2015-11-14 06:02:32 | 显示全部楼层
两轮国人,太棒了

楼主好运~~
回复 支持 反对

使用道具 举报

tommy1122337 发表于 2015-11-14 06:48:42 | 显示全部楼层
請問第一題 看adjacent number的思路是什麼
回复 支持 反对

使用道具 举报

adiggo 发表于 2015-11-14 08:10:27 | 显示全部楼层
楼主 求具体描述一下 二面第三题
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 10:33:55 | 显示全部楼层
stormy1991 发表于 2015-11-14 04:58
lz加油,马上就有offer了!话说G家实习面试都是背靠背的么?

地里看到的,和我周围的小伙伴大都是
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 10:37:24 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-14 05:42
lz能不能说一下找最少的increasing sequence number的详细解法?谢谢!

比如说给个序列,1,3,2,4
可以这样分:{1,3},{2,4}
也可以这样子分:{1,2}{3,4}
想要知道最少序列的数目,根据Dilworth定理,就是求4,2,3,1这个序列的LIS长度
. From 1point 3acres bbs
当然根据不同的题目还会有点小trick
如果题目求的是increasing subsequence的个数,那么逆序求的就是最长不下降子序列
如果题目求的是non-decreasing subsequence的个数,那么逆序求的就是LIS长度
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 10:37:44 | 显示全部楼层
fillchar 发表于 2015-11-14 06:00. From 1point 3acres bbs
一面第三题可以用线段树做我觉得,leetcode上应该有这题…
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
对的,segment tree也是balanced tree的一种
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 10:37:55 | 显示全部楼层
lcl3356897 发表于 2015-11-14 06:02
两轮国人,太棒了

楼主好运~~

谢谢啦~~~
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 10:38:33 | 显示全部楼层
tommy1122337 发表于 2015-11-14 06:48
請問第一題 看adjacent number的思路是什麼
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
已经排序的数组,如果有duplicate,那就是这样的
1,2,3,4,4,5,6
所以只要看任意adjacent数字是否相等就好
回复 支持 反对

使用道具 举报

 楼主| hackerpainter 发表于 2015-11-14 10:39:17 | 显示全部楼层
adiggo 发表于 2015-11-14 08:10
楼主 求具体描述一下 二面第三题

刚刚已经回复过另外一个小伙伴了. 1point 3acres 璁哄潧
如果想来了解的话,百多或者谷歌Dilworth应该就可以
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-8 23:32:29 | 显示全部楼层
楼主第一面,第三题是[arr[i]-k, arr[i]+k],还是[i - k, i + k]?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-8 23:37:00 | 显示全部楼层
hackerpainter 发表于 2015-11-14 10:37
比如说给个序列,1,3,2,4.鏈枃鍘熷垱鑷1point3acres璁哄潧
可以这样分:{1,3},{2,4}
也可以这样子分:{1,2}{3,4}

反序LIS是3,为什么序列是2呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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