一亩三分地论坛

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

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

Google 面经

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

2015(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
9.28 onsite

去年面实习的时候过了电面所以就直接onsite了,去年的面经不记得了orz,onsite四轮早上两轮下午两轮. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

round 1:
roman to integer, leetcode 原题,

给定一串shuffle过的source->destination的string像SFO->LAX, 还原顺序成source->dest1,dest1->dest2,dest2->dest3。。保证输入合法没有环,一条线。 hashmap 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
.鐣欏璁哄潧-涓浜-涓夊垎鍦
parallel 求解数组max元素,如果compare操作dominant时间,比如一分钟一次compare,给定长度N的数组,K个processors,求最少时间. 最后面试官同意的结果是ceil(N/K)-1+ceil(log(K))-1
N =32, K = 8, time = 5, 虽然我觉得最后一项应该是一个跟log(sqrt(k))有关的但是最后没时间了。假设剩下p个元素比较,如果p*(p-1)/2 < K那么就可以在一分钟出结果所以应该类似ceil(N/K)+ceil(log(K/p)+1

round 2:
给一堆字符串,给定每个char对应的morse code(假设有API), 求是否有字符串对应相同的morse code,输出。 hashmap
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给定stream of student record <name,gpa> 求max。min heap, bst
followup:100million record, machine with 64GB,analyze map reduce: map, reduce function, memory need, how to split
followup2: 如果split之后还是放不下怎么办. 如果可以牺牲精度? 如果只有8GB,every 8GB data output top K/split records assume random shuffle
followup3: 牺牲精度还有没有其他方法? fit a normal distribution, and calculate the threshold to cut if need more precision just fit more data. from: 1point3acres.com/bbs
这个system design感觉真是天马行空

round3:
给定matrix of island heights, 假设下雨可以从高处流到低处,如果左+上是太平洋,右+下是大西洋,问下雨到某个地方是否能同时流到两个洋。 BFS
鏉ユ簮涓浜.涓夊垎鍦拌鍧. . From 1point 3acres bbs
round4:
image rotate 180' in place leetcode原题 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
system design LRC不用写code, leetcode原题

总得来说还是很简单bar感觉相对小公司还是低不少,good luck to everyone

评分

1

查看全部评分

本帖被以下淘专辑推荐:

小柯西 发表于 2015-10-18 14:12:03 | 显示全部楼层
楼主还是很牛逼,膜拜下!
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-18 21:04:04 | 显示全部楼层
round 2 的话,如果只要最大值。。。。我内存O(1)维护一个最大值不就好了。。。=。=
回复 支持 反对

使用道具 举报

aoisky 发表于 2015-10-19 00:32:57 | 显示全部楼层
楼主什么时候得到的消息?
回复 支持 反对

使用道具 举报

 楼主| weakbirds 发表于 2015-10-19 02:19:47 | 显示全部楼层
Wizmann 发表于 2015-10-18 21:04
round 2 的话,如果只要最大值。。。。我内存O(1)维护一个最大值不就好了。。。=。=

哦打错了,求top k,100million求top 20million这样
回复 支持 反对

使用道具 举报

 楼主| weakbirds 发表于 2015-10-19 02:20:24 | 显示全部楼层
aoisky 发表于 2015-10-19 00:32
楼主什么时候得到的消息?

上周吧,听说一般两到三周
回复 支持 反对

使用道具 举报

 楼主| weakbirds 发表于 2015-10-19 02:20:50 | 显示全部楼层
round2: 是求top K 不是max...
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-19 11:59:01 | 显示全部楼层
weakbirds 发表于 2015-10-19 02:20. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
round2: 是求top K 不是max...

TopK也可以用桶排。因为成绩这种东西,值域比较小吧。
回复 支持 反对

使用道具 举报

 楼主| weakbirds 发表于 2015-10-19 13:06:26 | 显示全部楼层
Wizmann 发表于 2015-10-19 11:59
TopK也可以用桶排。因为成绩这种东西,值域比较小吧。
. 鍥磋鎴戜滑@1point 3 acres
内存fit不下top 10millions record
回复 支持 反对

使用道具 举报

wtcupup 发表于 2015-10-19 14:07:48 | 显示全部楼层
求round3 matrix那题的code
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-10-19 20:23:25 | 显示全部楼层
weakbirds 发表于 2015-10-19 13:06
内存fit不下top 10millions record

如果分数只能到1~100的话

我桶排一下就好了啊,只记数非常省内存。

当然你要一个total solution的话,上分布式也没什么可说的。
回复 支持 反对

使用道具 举报

molt 发表于 2015-10-22 10:00:56 | 显示全部楼层
image rotate 180' in place leetcode原题

弱问一下,这个转180度吗?leetcode上是90度。180的话也太简单了啊?
1 2  => 5 4. Waral 鍗氬鏈夋洿澶氭枃绔,
4 5        1 2
上下reverse, 左右reverse就可以?还是我想简单了?谢谢。
回复 支持 反对

使用道具 举报

 楼主| weakbirds 发表于 2015-10-23 16:19:39 | 显示全部楼层
molt 发表于 2015-10-22 10:00
image rotate 180' in place leetcode原题
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
弱问一下,这个转180度吗?leetcode上是90度。180的话也太简 ...

就是180°,直接对角swap上半matrix就好了不用两次reverse
回复 支持 反对

使用道具 举报

mingmingya 发表于 2015-10-23 20:47:20 来自手机 | 显示全部楼层
给定一串shuffle过的source->destination的string像SFO->LAX, 还原顺序成source->dest1,dest1->dest2,dest2->dest3。。保证输入合法没有环,一条线。 这题可以举个例子吗?没看懂,谢谢啦
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-10-23 22:57:50 | 显示全部楼层
请问下楼主,去年过了实习电面后为什么没去google实习?
回复 支持 反对

使用道具 举报

 楼主| weakbirds 发表于 2015-10-31 09:18:05 | 显示全部楼层
小柯西 发表于 2015-10-23 22:57
请问下楼主,去年过了实习电面后为什么没去google实习?

host match不上时间太晚了就去FB了
回复 支持 反对

使用道具 举报

leochen4891 发表于 2015-11-4 13:38:50 | 显示全部楼层
Wizmann 发表于 2015-10-19 20:23
如果分数只能到1~100的话

我桶排一下就好了啊,只记数非常省内存。

恩,如果是int型的分数,应该桶排,貌似题目里是GPA,可以带小数的,就看小数是多少位。如果是两位的话,还是可以桶排。
回复 支持 反对

使用道具 举报

chalice 发表于 2015-11-9 07:01:27 | 显示全部楼层
thanks for sharing
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 02:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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