谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 9106|回复: 58
收起左侧

Google面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
adamru 发表于 2015-8-26 00:26:22 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

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

onsite. visit 1point3acres for more.
1. 给一个字典,找出两个单词满足条件(1)没有相同的字母(2)长度的乘积最大
2. Serialize an N-ary Tree 将树存到文件里,要求可以还原。
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 . From 1point 3acres bbs
还有一种set,query都很多的情况就比较麻烦,好像论坛面经里有,当时我是准备onsite看到的。
不好意思啊 等级不够一小时只能发3帖 无法一一回复

补充内容 (2015-8-27 00:21):
多谢赏米!

关于电面 感谢19垅 大神@Linzertorte的说明, 二维树状数组可以实现两个都是O(logN)。特别感谢大神@Linzertorte写的面经,对我帮助很大!
来源一亩.三分地论坛.
补充内容 (2015-8-27 00:27):
关于onsite 1  感谢23垅@huanghe0828提供判断两个单词有没有重复字母的方法, 我面试也用的同样的方法,也是之前在地里面经看到的,不记得出处了,感谢原作者! 面试的时候还被问到如何优化,尽早退出循环。

.本文原创自1point3acres论坛补充内容 (2015-8-27 00:33):
接上面 我当时是所有单词按长度排序,从最长的单词开始循环,到剩下单词长度乘积都比已知结果小的时候退出循环。当然最理想是开始就按pair的长度乘积排序,但比较难实现,和面试官讨论后放弃。内循环也能提前退出。
. Waral 博客有更多文章,
补充内容 (2015-8-27 00:40):
关于 onsite 4 感谢9垅@hj867955629 和 23垅@huanghe0828,(1)每个单词可以选缩或不缩,所以一共有2^N种结果,楼主比价水加之最后一轮有点脑抽 想的比较复杂。

补充内容 (2015-8-27 00:43):
接上面 (2)我当时的方法是DFS,先把选中的字母变成特殊字符(我当时是1), 然后选完后把所有1合并成符合要求的数字。

补充内容 (2015-9-1 10:04):
关于onsite3 每天都有两种情况(1)手上有share,记为hold(2)手上没share,记为unhold. 那么第 i 天 hold[ i ] 可能(1)第 i - 1天有share,保持 (2)第 i - 2 天没share,可以买。取两者大的. from: 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]。当然可以优化空间啦
. 围观我们@1point 3 acres
补充内容 (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大米 +58 收起 理由
虾米酱 + 15
hulahu + 3 感谢分享!
whdawn + 30
jy_121 + 5 感谢分享!
MCwong + 5 欢迎来介绍你知道的情况

查看全部评分


上一篇:Amazon New York职位发的OA有人做过吗?
下一篇:LiveRamp电面面经

本帖被以下淘专辑推荐:

我的人缘0
 楼主| adamru 发表于 2015-9-1 10:19:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
吞字。。。不明觉厉。。。hold[ i ] = max(hold[i-1], unhold[i-2] - price[ i ]) 和 unhold[ i ] = max(uphold[i-1], hold[i-1] + price[ i ])
回复 支持 反对

使用道具 举报

我的人缘0
zzwzhong698800 发表于 2015-9-10 23:11:33 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
alucardzhou 发表于 2015-8-26 03:14
请问楼主能贴出网上那个答案的链接么?十分感谢
来源一亩.三分地论坛.
你可以搜一下树状数组,这题就是用树状数组可以达到,更新和取和都是log(n)的复杂度
回复 支持 1 反对 0

使用道具 举报

我的人缘0
Linzertorte 发表于 2015-8-30 05:58:03 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
哇 。 你怎么不给我加分啊
回复 支持 1 反对 0

使用道具 举报

我的人缘0
maxnima 发表于 2015-8-26 01:24:53 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
恭喜楼主,word abbreviation 这题怎么破啊。
回复 支持 反对

使用道具 举报

我的人缘0
hanchen999 发表于 2015-8-26 01:38:43 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
感觉怎么排列好像都有重复
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| adamru 发表于 2015-8-26 01:56:56 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maxnima 发表于 2015-8-26 01:24
恭喜楼主,word abbreviation 这题怎么破啊。

我是这么做的:
如果单词长度为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上类似的思路。
回复 支持 反对

使用道具 举报

我的人缘0
maxnima 发表于 2015-8-26 02:04:29 | 显示全部楼层
  此人我要顶:
 
0% (0) 【我投】
  此人我要踩:
 
100% (1) 【我投】
adamru 发表于 2015-8-26 01:56.1point3acres网
我是这么做的:
如果单词长度为N, 可以分别选0,1,2 。。。N个字母进行缩写。对于选K个字母,就是N个中 ...

膜拜,大牛,我回去好好想想。
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
jiebour 发表于 2015-8-26 02:14:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主,第一题不考虑set多query少或者set少query多的话,很好做。要是考虑的话怎么破。。。。。求
回复 支持 反对

使用道具 举报

我的人缘0
Walcottking 发表于 2015-8-26 02:16:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
adamru 发表于 2015-8-26 01:56
我是这么做的:. more info on 1point3acres
如果单词长度为N, 可以分别选0,1,2 。。。N个字母进行缩写。对于选K个字母,就是N个中 ...

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

使用道具 举报

我的人缘0
 楼主| adamru 发表于 2015-8-26 02:37:53 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maxnima 发表于 2015-8-26 02:04. 围观我们@1point 3 acres
膜拜,大牛,我回去好好想想。

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

使用道具 举报

我的人缘0
hj867955629 发表于 2015-8-26 02:45:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
maxnima 发表于 2015-8-26 02:04
膜拜,大牛,我回去好好想想。

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

使用道具 举报

我的人缘0
 楼主| adamru 发表于 2015-8-26 02:45:57 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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). 但楼主太水,没看懂。。。有兴趣可以看下哈
回复 支持 反对

使用道具 举报

我的人缘0
jiebour 发表于 2015-8-26 02:50:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
adamru 发表于 2015-8-26 02:45
我是这么做的:
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0 ...

这个我知道,比较经典的一个预处理问题。
可能我理解错了吧,你说的set很多指的是你预处理了之后,又会有set操作?然后需要再次预处理?
谢谢楼主耐心!
回复 支持 反对

使用道具 举报

我的人缘0
alucardzhou 发表于 2015-8-26 03:14:02 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
adamru 发表于 2015-8-25 13:45
我是这么做的:
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0 ...

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

使用道具 举报

我的人缘0
hj867955629 发表于 2015-8-26 03:14:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
adamru 发表于 2015-8-26 02:45. 1point 3acres 论坛
我是这么做的:
(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]啊?
回复 支持 反对

使用道具 举报

我的人缘0
jiebour 发表于 2015-8-26 03:21:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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很少,你怎么办?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| adamru 发表于 2015-8-26 03:23:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
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]啊?

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

使用道具 举报

我的人缘0
zhouyoung1124 发表于 2015-8-26 03:27:58 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我想问个蠢问题。。。google onsite管不管从家里去机场来回的出租车费。。。
回复 支持 反对

使用道具 举报

我的人缘0
huanghe0828 发表于 2015-8-26 05:55:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
能不能请问下面的是什么职位?
回复 支持 反对

使用道具 举报

我的人缘0
zhouyoung1124 发表于 2015-8-26 08:36:29 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主。。。Onsite 第一题是用Trie做么?
回复 支持 反对

使用道具 举报

我的人缘0
Linzertorte 发表于 2015-8-26 08:46:32 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
adamru 发表于 2015-8-26 02:45
我是这么做的:
(1)直接存下输入二维数组就行 set就是O(1), query O(N)
(2)二维数组S存的是(0, 0 ...

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

使用道具 举报

我的人缘0
zhouyoung1124 发表于 2015-8-26 08:50:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
当我没问。。。这题是个明显的bit计算。。。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-23 16:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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