一亩三分地论坛

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

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

Google - 2016暑期实习面经 (三轮,共5题)

[复制链接] |试试Instant~ |关注本帖
wangding0421 发表于 2015-11-3 11:13:09 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 校园招聘会 |Passfresh grad应届毕业生

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

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

x
楼主现在第一年Master in CS, UCSD。地里找的内推。第一次发帖,总共面了三轮 (C++):
前两轮是On Campus,时间:10/13/2015。中午12:30 - 14:00。
第一轮:
面试官:白人小哥,做database的。
插曲:被HR带错了房间,开始的时候45分钟已经过了15分钟。
题目:3 Sum Smaller (Leetcode带锁的题,楼主没subscribe,凭着3 Sum的感觉写的)
解法:用仨pointer吧。
Follow-ups:
  • Time Complexity? (O(n^2))
  • 注意到我用了三个指针,如果三个点之和超过了INT_MAX怎么办?(换一下data type。把int32换成long。)
  • 有没有别的方法。(楼主一开始没想到啥别的,他说提醒你可以用hashmap先存两个两个的和。然后楼主就想到了好像可以先把两个两个的和都存了,然后在loop一轮,遇到符合条件的就把counter加一。)
有啥要问面试官的么:
没时间了,面试官就没让我问。

背靠背第二轮:
(真的是背靠背,因为就是对门儿)
面试官:亚洲成熟大叔,做map的。

题目:
  • 说一下你本科最喜欢的课。(好心帮我热身感觉)
  • 你喜欢体育么,我说喜欢篮球,他说好。那给你一堆数据,每一个数据是一个NBA的比赛结果,比如:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
            第一个数据是:Lakers 98 : Kings 96.             第二个数据是:xxx 100:xx101
            以此类推。
            前提是淘汰制度,然后让你处理一下这个数据输出一个最后的冠军。
  解法:楼主loop一下数据,然后建了一个map来存还没输过的队伍。最后输出就行了。
Follow-ups:
  • 如果是总共有128只队伍,那么冠军应该赢了几场。(一开始脑抽了说六场,赶紧改正说是7场。)
  • 如果是127只队伍呢?(6或7场?面试官接着问为啥,我说如果那个冠军恰好是种子选手,就6场吧。)
  • 有没有可能,冠军其实只赢了一场?(我一开始说不可能吧,除非这队伍特别特别牛逼就在final那儿等着别人。然后竟然把他逗笑了,他说你说的对,就好比冠军守擂一样)
做到这儿的时候感觉这不就是脑筋急转弯吗!
有啥要问面试官的么:
问了个问题,闲聊一会结束了。

一周后(10/20/2015)收到邮件说要加面一轮电面。(估计是表现不行啊。。。)
时间:10/26/2015。中午11:00 - 12:00 (超时了)。
第三轮:
面试官:印度小哥,做knowledge graph(其实没听懂,毕竟phone + English捉急)的。
插曲:上来问我天气,我确认了三次才发现他是在问我天气。。。然后说了半天什么graph我还以为第一题我就没听懂,后来发现人家在自我介绍。
题目:
  • Remove duplicate from string vector.
解法:用hashmap做记录,但这里楼主脑抽犯了错误用的erase,后来才意识到应该用俩指针不停覆盖,时间复杂度可以减少。
  2. Search for a range (Leetcode)
稍有改动,原题是一堆sorted int,这题改成排好序的string。然后给你的target是一个prefix。
举例:
const vector<string> input = {a, an, app, apple, bad, badminton, badness, bat };
prefix “bad”
should return Range (4, 6);
解法:用二分法写了一个找lower_bound的function,一个找upper_bound的function。还写了一个比较当前string和prefix关系的function。
后来发现那个string和prefix关系的function有错。但是当场小哥和我都没发现。。。
这时候已经40分钟了,小哥说你要不要检查一下,还是直接第三题。我说那我检查一下吧,他说好那你去检查,我去给你出第三题。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
   3. 给你一Student的struct。包含 string name 和 float height
然后给你个typedef vector<Student> SchoolData. 里面的学生都按身高(由高到低!)排好了。
好了,题目是这样的:
给你一个vector<SchoolData>, 让你输出前k高的学生。
举例:
input <{{tom, 44}, {peter, 43}, {hary, 42}} , {{john, 45}, {kary, 42}, {simon, 40}}, {{randy 47}, {rob, 46}, {matt, 45.5}}>
output : <{randy, 47} {rob, 46} {matt, 45.5}>
解法:已经没啥时间了就直接说了一个比较优的解法,用max heap。本来寻思没时间了说个思路估计就完事了,结果说完思路面试官说,好,写吧。
就写了。
后来发现操作heap的时候漏了一行,竟然是漏掉了要pop。。。。简直觉得肯定要崩了。
这个题主要注意的就是heap 的compare的struct要自己写!
有啥要问面试官的么:
问了一问题,结果印度小哥说啥我是真没听懂哎。。。以上就结束了。

本来以为第二天没收到hr通知进入下一轮就是崩了,结果没想到今天 (11/2/2015) 竟然被告知进入pool。
感动成马,发帖攒个人品。跪求地里的Googler捡了我。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

5

查看全部评分

dong882205 发表于 2015-11-4 12:30:53 | 显示全部楼层
前k高的学生这题,逻辑上得用一个min heap吧,然后改写priority_queue里的compare?
回复 支持 1 反对 0

使用道具 举报

deepreader 发表于 2015-11-3 11:26:53 | 显示全部楼层
顶google 鼎,专程来膜拜。
回复 支持 反对

使用道具 举报

chopinzwz 发表于 2015-11-4 11:19:07 | 显示全部楼层
恭喜楼主!  我也进pool了,然后HR就说让等11月初project才放出,好焦虑
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-11 05:19:36 | 显示全部楼层
前K大的 应该是小顶堆。。
回复 支持 反对

使用道具 举报

sonicgu 发表于 2016-1-11 07:58:04 | 显示全部楼层
lz如果球队的个数有2^k + 1个的话,有可能总冠军只赢了一场吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 11:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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