一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
shou3301 发表于 2015-6-7 13:44:07 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 猎头 - Onsite |Other在职跳槽

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

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

x
共5轮. visit 1point3acres.com for more.
第一轮
给一个matrix,一开始都是0。写一个method addRock(int i, int j),实现在i,j位置加入一个rock使其可以变成一个island或者island的一部分,然后这个method要返回这个matrix里有多少个island

第二轮
假设把人类的族谱形成一张图,每个人都是一个node,每个人会有父亲和母亲(也是node),写一个method isBloodRelated(Node n1, Node n2),实现假设n1和n2有共同的祖先,那么就意味着n1和n2是related的。限制是可能有很多代人,然后可以在node加额外的信息。
. more info on 1point3acres.com
第三轮
问题1:
给两个实现的method, Collection<String> getActors(String movie) 和 Collection<String> getMovies(String actor)
写一个method int distance(String actor1, String actor2),实现计算actor1到actor2的最短距离。距离的定义是假设两个演员在同一部电影里出演,那么他们之间的distance就是1。follow up是假设数据集很大,有什么方法可以优化。
问题2:
给一个expression只有+, *, 和数字。然后给一个实现好的method Iterator<Token> tokenize(String exp),1问是如何model这个Token,方向是OOD。2问是写一个method int calculate(Iterator<Token> iter),实现计算表达式的值。

第四轮
问题1:
写一个method int longestStringWithAtMostTwoUniqueChars(String s),实现返回最长的substring最多有两个unique的char
问题2:
设计google map的back end的api

第五轮
感觉问得有点偏。他先问如何实现shuffle elements in an array,但是关键不是在实现,而是证明为什么概率是正确的。我没答上来,他引导我用数有多少种可能的permutation来证明。然后follow up是他给了一种错误的shuffle的方法,然后问怎么证明这个算法是错误的。我也没答上来,他就继续引导,我没能很快理解,不过最后在他耐心的解释下,我还是理解了。
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 由于没剩下很多时间,第2个问题就是问了下在网页上填了个什么东西,然后点击submit后会发生什么,越详细越好。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

wugoat 发表于 2015-6-8 00:23:07 | 显示全部楼层
感谢分享面经! 第三轮的follow up是是什么思路 感觉就是bfs 用mapreduce吗
回复 支持 反对

使用道具 举报

tyr034 发表于 2015-6-8 04:46:02 | 显示全部楼层
wugoat 发表于 2015-6-8 00:23
感谢分享面经! 第三轮的follow up是是什么思路 感觉就是bfs 用mapreduce吗

maybe bi-direction bfs?
回复 支持 反对

使用道具 举报

yinloveslele 发表于 2015-6-8 07:19:45 | 显示全部楼层
请问第二题怎么解啊。。我假设每个node都有指针指向父母。那么从两个节点分别bfs mark祖先,然后通过hashset看有没有intersection? 好像memory 要求挺多的啊。
回复 支持 反对

使用道具 举报

2006reload 发表于 2015-6-8 11:07:56 | 显示全部楼层
第三题follow up 怎么解
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-6-8 12:01:39 | 显示全部楼层
wugoat 发表于 2015-6-8 00:23
感谢分享面经! 第三轮的follow up是是什么思路 感觉就是bfs 用mapreduce吗

给的提示是说假如有的演员很popular,有没有帮助。最后的意思是,每个actor的节点可以存个参数类似于popular的程度,然后在bfs的时候先去add那些popular的,基本就把普通的queue换成priority queue。
回复 支持 反对

使用道具 举报

 楼主| shou3301 发表于 2015-6-8 12:04:27 | 显示全部楼层
yinloveslele 发表于 2015-6-8 07:19
请问第二题怎么解啊。。我假设每个node都有指针指向父母。那么从两个节点分别bfs mark祖先,然后通过hashse ...

可以在每个node存额外信息,所以在网上遍历的时候可以记下这个是n1或者n2的祖先,然后假设另外个遍历的时候发现了这个信息就说明是relaed。还有注意的一点是两个要交替遍历,这样可以少许优化时间。
回复 支持 反对

使用道具 举报

yinloveslele 发表于 2015-6-8 12:06:02 | 显示全部楼层
shou3301 发表于 2015-6-8 12:04. visit 1point3acres.com for more.
可以在每个node存额外信息,所以在网上遍历的时候可以记下这个是n1或者n2的祖先,然后假设另外个遍历的时 ...

懂了, 交替遍历确实是一种优化。多谢!
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-6-8 12:48:08 | 显示全部楼层
shou3301 发表于 2015-6-8 12:01
给的提示是说假如有的演员很popular,有没有帮助。最后的意思是,每个actor的节点可以存个参数类似于popu ...

感觉很tricky 啊 popular 的actor参与的movie多 和其他actor有short distance的path几率也较大
回复 支持 反对

使用道具 举报

wugoat 发表于 2015-6-8 12:48:25 | 显示全部楼层
shou3301 发表于 2015-6-8 12:01
给的提示是说假如有的演员很popular,有没有帮助。最后的意思是,每个actor的节点可以存个参数类似于popu ...

感觉很tricky 啊 popular 的actor参与的movie多 和其他actor有short distance的path几率也较大
回复 支持 反对

使用道具 举报

buaawj 发表于 2015-6-10 07:48:12 | 显示全部楼层
"给一个expression只有+, *, 和数字。然后给一个实现好的method Iterator<Token> tokenize(String exp),1问是如何model这个Token,方向是OOD。"

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷请问搂住,这个怎么model的? 谢谢!
回复 支持 反对

使用道具 举报

XCQ 发表于 2015-6-23 16:04:15 | 显示全部楼层
楼主能讲讲google map api怎么design 要实现哪些operation吗?
另外第一题是不是union find比较好?
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-2-3 15:48:39 | 显示全部楼层
shou3301 发表于 2015-6-8 12:04
可以在每个node存额外信息,所以在网上遍历的时候可以记下这个是n1或者n2的祖先,然后假设另外个遍历的时 ...

如果乱伦了也是有血缘关系的  所有不能交替遍历吧?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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