一亩三分地论坛

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

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

新鲜出炉的Google On Campus面经

[复制链接] |试试Instant~ |关注本帖
herz 发表于 2014-11-5 05:17:16 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Google - 内推 - 校园招聘会 |Other

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

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

x
昨天去面的,两轮back-to-back总共1.5小时,面我的是两个美国小哥,

第一轮:小哥说他是LA分部的,瞎聊了几句扯了点Project开始做题。
第一题是Moving Average, 每次输入一个数,调用double next_val(int val),和现有的windows_size,输出当前平均数。
例如,win_size = 3,
next_val(1) = 1/3;
next_val(10) = (1 + 10) / 2;
next_val(3) = (1 + 10 + 3) / 3;
next_val(5) = (10 + 3 + 5) / 3 (因为已经数的总数已经到达win_size).鏈枃鍘熷垱鑷1point3acres璁哄潧
……
这题还算直接,一个queue不断记录当前的win_size个数,一个sum不断记录当前和就行。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

第二题是Friend Suggestion,知道一个人在network里的Friends,求Friends的Friends里和这个人最多common friends的人。
Person{
    vector<Person*> Friends;
}类似这样,假设读进来是Person *a,
一开始想了三重循环的直接方法,b = loop a的Friends, c = loop b的Friends,d = loop c的Friends再看这里面有多少和b in common统计输出,O(n3),并且注意判断重复(不要找到a,也不要找到已存在的friends)
然后要我改进,我说那可以用hash来保存a的friends有哪些friends,就少一个loop了,小哥看来也算满意,时间也差不多结束了。


第二轮:一个光头小哥,看起来有点冷冰冰,也是show了一下project开始做题。. From 1point 3acres bbs
第一题是look and say,leetcode原题,我假装没做过先听他叙述完我也仔细想好怎么一次写出来了,比较顺利,还跟他讨论了下in place的做法。


第二题是不用写code直接说思路的,说现在有很多数据,知道某种狗的parent是什么狗,问用什么数据结构来记录并能较方便地查询任意两种狗是不是blood related的(share一个共同的祖先)。
想了想就说先用一个dummy root node把森林变成一棵树,然后求这两个结点的lowest common ancester,求的方法可以用链表记录路径也可以直接判断blah blah blah。
小哥说嗯这个work,能不能更快点。我说更快的话就要求更多信息,最好就是可以child node指向parent node,这样可以很多种方法来做,直接搜吖,hash吖,甚至建成无向图找最短路等等,讲完时间也刚刚好到,我就跑回去上课了。

累死,明天面F家求人品!! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

评分

1

查看全部评分

byrlhb 发表于 2014-11-5 08:17:33 | 显示全部楼层
如何排除已经存在的friends?用hashmap?
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-11-7 12:04:33 | 显示全部楼层
我也是光头小哥。。题目跟你的完全一样....
回复 支持 反对

使用道具 举报

 楼主| herz 发表于 2014-11-7 13:17:58 | 显示全部楼层
kelvinzhong 发表于 2014-11-7 12:04
我也是光头小哥。。题目跟你的完全一样....

那就好!!碰到面经是好运气!
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-11-7 15:39:18 | 显示全部楼层
楼主是哪个学校的?
回复 支持 反对

使用道具 举报

yannan 发表于 2014-11-9 01:40:44 来自手机 | 显示全部楼层
请问lz申请的是全职嘛
回复 支持 反对

使用道具 举报

yannan 发表于 2014-11-9 01:42:28 来自手机 | 显示全部楼层
sorry我手机上看不到,打开电脑发现是的
回复 支持 反对

使用道具 举报

lin126 发表于 2014-11-9 04:46:41 | 显示全部楼层
楼主是在哪里面的啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 02:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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