一亩三分地论坛

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

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

Google 12月11日 onsite

[复制链接] |试试Instant~ |关注本帖
majiaofdaye 发表于 2016-2-9 12:12:36 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 网上海投 - Onsite |Failfresh grad应届毕业生

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

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

x
除了第一个是国人,其他三人都是老印,不过也没感觉坑。
建议大家动手写面经里的题目。 写过的题目会变成你在面试中的自信。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

1。decode way。leetcode问的是number of decode way。要求返回所有可能的decoding, as a list of string。.1point3acres缃

2。 string compress. aaa -> 3Xa。不能用escape character。decoder不能改。 老题目。

第二问是算法思路题。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
集群各机器上有无序int stream,要找这些其median。 用quick selection的思想(pivot与其rank)。本来是在一个int[]中找median,现在是要在[int[], int[], int[]....]中找出median。从第一台机器找出local median后让其report pivot和rank,再把这信息发给所有其他机器让他们算出给定pivot 和小于pivot的value count,即为[pivot, count of values smaller than pivot]。这样一来回就知道下一步该怎么做,具体有三种情况。


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

3。general树(子节点数量不定)中找出最长的连续整数链条长度,每个节点都是int值。问:怎么表示树节点(要写class定义)?写代码找maxConsecutivePathLength()
递归遍历即可。

follow up: 如果不是树而是DAG图怎么做?怎么表示图的节点?考虑哪些问题?怎么优化?
就当做一般的有向无环图遍历即可,节点中可加visited标记。注意图不连通的情况,这点面试官故意没说清楚。. 1point 3acres 璁哄潧

4。判断字符串s是否是按照顺序规则字符串t排好序的。t规定哪个字符该出现在哪个前面。t是有效的顺序字符串。即每个字符不会出现多次,但也不确保26个字母都有。s中某些字符可能不在t中,那么这些字符必须得跟自己相同的字符成群出现(不能有脱离群体单独出现的)。

e.g.:
s= "ccbbfffffaaaa"  t="cba" => true 因为t规定c在b前,b在a前出现,s确实如此。f不在t中出现,但f是成群出现的。因此符合。
s= "ccbbfffffaaaaffff"  t="cba" => false, f没有成群出现。. from: 1point3acres.com/bbs

一种做法:判断s中两种类型的字符是否按规矩来的。 一种是出现在t中的,按t给定的顺序出现。另一种是不在t中的,要成群出现。两种条件都得满足。



评分

4

查看全部评分

本帖被以下淘专辑推荐:

hakusama1024 发表于 2016-2-9 13:24:58 | 显示全部楼层
感谢楼主的分享。请问结果如何。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-7 11:34:12 | 显示全部楼层
请问第四题是用hashmap吗?
回复 支持 反对

使用道具 举报

siren01 发表于 2016-3-7 11:52:06 | 显示全部楼层
bobzhang2004 发表于 2016-3-7 11:34
请问第四题是用hashmap吗?

想qing jia
. 1point3acres.com/bbs
补充内容 (2016-3-7 11:52):
想请教一个题目,就是LeetCode 253,求重叠最多的一个区间. 不知道binary index tree的解法。。
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-7 16:13:46 | 显示全部楼层
bobzhang2004 发表于 2016-3-7 11:34
请问第四题是用hashmap吗?

这个第四题怎么做啊?谢谢!
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-3-7 16:13:57 | 显示全部楼层
楼主最后一题怎么做?谢谢
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-30 03:55:38 | 显示全部楼层
第四题我觉得先是扫一遍记录不在t中的字符出现的区间数,保存其他字符在list中,然后去重生成新的字符串和t比较是否equal。
回复 支持 反对

使用道具 举报

m1h1r0 发表于 2016-5-7 03:08:25 | 显示全部楼层
请教第2问中pivot和rank是什么?
回复 支持 反对

使用道具 举报

 楼主| majiaofdaye 发表于 2016-6-16 14:07:54 | 显示全部楼层
m1h1r0 发表于 2016-5-7 03:08. 1point3acres.com/bbs
请教第2问中pivot和rank是什么?

Pivot 是分界线的value。 小于pivot的放在一边,大于pivot的放在另一边。Rank就是pivot的值排序后排第几,这就能知道小于/大于pivot的有几个。
回复 支持 反对

使用道具 举报

 楼主| majiaofdaye 发表于 2016-6-16 14:08:16 | 显示全部楼层
Pivot 是分界线的value。 小于pivot的放在一边,大于pivot的放在另一边。Rank就是pivot的值排序后排第几,这就能知道小于/大于pivot的有几个。
回复 支持 反对

使用道具 举报

Thunder_up 发表于 2016-6-27 13:00:59 | 显示全部楼层
majiaofdaye 发表于 2016-6-16 14:08
Pivot 是分界线的value。 小于pivot的放在一边,大于pivot的放在另一边。Rank就是pivot的值排序后排第几, ...

请问楼主第三题树那道是从上往下么?还是能从左往右那种?从左往右貌似很复杂啊- -!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 04:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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