一亩三分地论坛

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

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

Google面经

[复制链接] |试试Instant~ |关注本帖
adamru 发表于 2015-8-26 00:26:22 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 Onsite |Passfresh grad应届毕业生

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

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

x
电面
输入是一个二维数组。要求实现 (1)set(x, y, n) 更改(x, y)值为n (2)query(x1, y1, x2, y2) 计算输出(x1, y1)为左顶点,(x2, y2)为右底点的子二维数组内所有数的和
例子:
1 2 3
4 5 6
7 8 9
query(1, 1, 2, 2) = 5 + 6 + 8 +9 = 28;
考虑(1) set很多, query很少(2)set很少,query很多

onsite.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. 给一个字典,找出两个单词满足条件(1)没有相同的字母(2)长度的乘积最大
2. Serialize an N-ary Tree 将树存到文件里,要求可以还原。. from: 1point3acres.com/bbs
3. Stock + House robber 结合题 可以无限买卖,但卖了之后要至少隔一天才能买
4. Word Abbreviation 单词中连续的字符串可以用它的长度代替, 例如 abbreviation 可以为 a1breviation a2reviation 1bbreviation abbrevia4 ab3via4 abbreviation 11n 12等,问(1)一共有多少种缩写(2)输出所有这些缩写



补充内容 (2015-8-26 03:35):
关于电面 是分两种情况 进行适当预处理 然后实现set query
还有一种set,query都很多的情况就比较麻烦,好像论坛面经里有,当时我是准备onsite看到的。
不好意思啊 等级不够一小时只能发3帖 无法一一回复

补充内容 (2015-8-27 00:21):
多谢赏米!. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

关于电面 感谢19垅 大神@Linzertorte的说明, 二维树状数组可以实现两个都是O(logN)。特别感谢大神@Linzertorte写的面经,对我帮助很大!

补充内容 (2015-8-27 00:27):. more info on 1point3acres.com
关于onsite 1  感谢23垅@huanghe0828提供判断两个单词有没有重复字母的方法, 我面试也用的同样的方法,也是之前在地里面经看到的,不记得出处了,感谢原作者! 面试的时候还被问到如何优化,尽早退出循环。. more info on 1point3acres.com

补充内容 (2015-8-27 00:33):
接上面 我当时是所有单词按长度排序,从最长的单词开始循环,到剩下单词长度乘积都比已知结果小的时候退出循环。当然最理想是开始就按pair的长度乘积排序,但比较难实现,和面试官讨论后放弃。内循环也能提前退出。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
补充内容 (2015-8-27 00:40):.鏈枃鍘熷垱鑷1point3acres璁哄潧
关于 onsite 4 感谢9垅@hj867955629 和 23垅@huanghe0828,(1)每个单词可以选缩或不缩,所以一共有2^N种结果,楼主比价水加之最后一轮有点脑抽 想的比较复杂。
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-8-27 00:43):
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴接上面 (2)我当时的方法是DFS,先把选中的字母变成特殊字符(我当时是1), 然后选完后把所有1合并成符合要求的数字。

补充内容 (2015-9-1 10:04):. visit 1point3acres.com for more.
关于onsite3 每天都有两种情况(1)手上有share,记为hold(2)手上没share,记为unhold. 那么第 i 天 hold[ i ] 可能(1)第 i - 1天有share,保持 (2)第 i - 2 天没share,可以买。取两者大的
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2015-9-1 10:07):
接上面 即 hold = max(hold[i-1], unhold[i-2] - price)。 同样, unhold = max(uphold[i-1], hold[i-1] + price). 最后返回unhold[n-1]。当然可以优化空间啦

补充内容 (2015-9-1 10:13):
更正 上面是hold = max(hold[i-1], unhold[i-2] - price) 和 unhold = max(uphold[i-1], hold[i-1] + price)

补充内容 (2015-9-1 10:21):
吞字。。。不明觉厉。。。hold[ i ] = max(hold[i-1], unhold[i-2] - price[ i ]) 和 unhold[ i ] = max(uphold[i-1], hold[i-1] + price[ i ])

评分

5

查看全部评分

本帖被以下淘专辑推荐:

 楼主| adamru 发表于 2015-9-1 10:19:02 | 显示全部楼层
吞字。。。不明觉厉。。。hold[ i ] = max(hold[i-1], unhold[i-2] - price[ i ]) 和 unhold[ i ] = max(uphold[i-1], hold[i-1] + price[ i ])
回复 支持 反对

使用道具 举报

zzwzhong698800 发表于 2015-9-10 23:11:33 | 显示全部楼层
alucardzhou 发表于 2015-8-26 03:14
请问楼主能贴出网上那个答案的链接么?十分感谢
. Waral 鍗氬鏈夋洿澶氭枃绔,
你可以搜一下树状数组,这题就是用树状数组可以达到,更新和取和都是log(n)的复杂度
回复 支持 1 反对 0

使用道具 举报

Linzertorte 发表于 2015-8-30 05:58:03 | 显示全部楼层
哇 。 你怎么不给我加分啊
回复 支持 1 反对 0

使用道具 举报

maxnima 发表于 2015-8-26 01:24:53 | 显示全部楼层
恭喜楼主,word abbreviation 这题怎么破啊。
回复 支持 反对

使用道具 举报

hanchen999 发表于 2015-8-26 01:38:43 | 显示全部楼层
感觉怎么排列好像都有重复
回复 支持 反对

使用道具 举报

 楼主| adamru 发表于 2015-8-26 01:56:56 | 显示全部楼层
maxnima 发表于 2015-8-26 01:24
恭喜楼主,word abbreviation 这题怎么破啊。
-google 1point3acres
我是这么做的:
如果单词长度为N, 可以分别选0,1,2 。。。N个字母进行缩写。对于选K个字母,就是N个中选K个, 就是 n! / k!(n-k)! 记为Ck。
总和就是 C0 + C1 + C2 +....+ Ck-1 + Ck =pow(2, k).
然后(2)问用DFS实现,leetcode上类似的思路。
回复 支持 反对

使用道具 举报

maxnima 发表于 2015-8-26 02:04:29 | 显示全部楼层
adamru 发表于 2015-8-26 01:56
我是这么做的:
如果单词长度为N, 可以分别选0,1,2 。。。N个字母进行缩写。对于选K个字母,就是N个中 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
膜拜,大牛,我回去好好想想。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 02:14:00 | 显示全部楼层
楼主,第一题不考虑set多query少或者set少query多的话,很好做。要是考虑的话怎么破。。。。。求
回复 支持 反对

使用道具 举报

Walcottking 发表于 2015-8-26 02:16:49 | 显示全部楼层
adamru 发表于 2015-8-26 01:56
我是这么做的:
如果单词长度为N, 可以分别选0,1,2 。。。N个字母进行缩写。对于选K个字母,就是N个中 ...

大神,如果直接从N中取K个的话,怎么保证取出来的是连续的呢?
回复 支持 反对

使用道具 举报

 楼主| adamru 发表于 2015-8-26 02:37:53 | 显示全部楼层
maxnima 发表于 2015-8-26 02:04
膜拜,大牛,我回去好好想想。

楼主很水的。。。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-26 02:45:45 | 显示全部楼层
maxnima 发表于 2015-8-26 02:04
膜拜,大牛,我回去好好想想。

也可以这么想,每个字母可能被缩写了,也可能没被缩写,所以最后是2^n个。
回复 支持 反对

使用道具 举报

 楼主| adamru 发表于 2015-8-26 02:45:57 | 显示全部楼层
jiebour 发表于 2015-8-26 02:14. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主,第一题不考虑set多query少或者set少query多的话,很好做。要是考虑的话怎么破。。。。。求

我是这么做的:
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0)和(x, y)组成的子数组中所有数的和
这样query(x1, y1, x2, y2) = S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1] 就能O(1)了, set O(N)了
其实应该还有第三问,如果一样多怎么办? 面完后网上搜题看到的。 答案可以实现都是O(logN). 但楼主太水,没看懂。。。有兴趣可以看下哈
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 02:50:09 | 显示全部楼层
adamru 发表于 2015-8-26 02:45
我是这么做的: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个我知道,比较经典的一个预处理问题。
可能我理解错了吧,你说的set很多指的是你预处理了之后,又会有set操作?然后需要再次预处理?-google 1point3acres
谢谢楼主耐心!
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-26 03:14:02 | 显示全部楼层
adamru 发表于 2015-8-25 13:45
我是这么做的:. 1point3acres.com/bbs
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0 ...

请问楼主能贴出网上那个答案的链接么?十分感谢
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-26 03:14:38 | 显示全部楼层
adamru 发表于 2015-8-26 02:45
我是这么做的:
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0 ...

是不是query(x1, y1, x2, y2) = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]啊?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 03:21:22 | 显示全部楼层
hj867955629 发表于 2015-8-26 03:14
是不是query(x1, y1, x2, y2) = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]啊?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果set操作很多,query很少,你怎么办?
回复 支持 反对

使用道具 举报

 楼主| adamru 发表于 2015-8-26 03:23:19 | 显示全部楼层
hj867955629 发表于 2015-8-26 03:14
是不是query(x1, y1, x2, y2) = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]啊?

哈哈 是是 当时写的时候也是这么错得 多谢指正
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-8-26 03:27:58 | 显示全部楼层
我想问个蠢问题。。。google onsite管不管从家里去机场来回的出租车费。。。
回复 支持 反对

使用道具 举报

huanghe0828 发表于 2015-8-26 05:55:00 | 显示全部楼层
能不能请问下面的是什么职位?
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-8-26 08:36:29 | 显示全部楼层
楼主。。。Onsite 第一题是用Trie做么?
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-8-26 08:46:32 | 显示全部楼层
adamru 发表于 2015-8-26 02:45 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我是这么做的:
(1)直接存下输入二维数组就行 set就是O(1), query O(N). Waral 鍗氬鏈夋洿澶氭枃绔,
(2)二维数组S存的是(0, 0 ...

二维树状数组嘛 。
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-8-26 08:50:35 | 显示全部楼层
当我没问。。。这题是个明显的bit计算。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 05:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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