一亩三分地论坛

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

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

Google新鲜面经

[复制链接] |试试Instant~ |关注本帖
donghao 发表于 2015-8-29 03:16:12 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
谷歌面经,话不多说,直接上题目吧,  就是 2D matrix
Given a 2D space of maximum size NxN which supports two operations :
[1] void UPDATE(x,y,v) - sets the value of cell [x,y] to v
[2] int SUM(x1,y1,x2,y2) - returns sub-rectangle sum (x1,y1) to (x2,y2)
inclusive, and there is an infinite stream of such 2 types of operations which have to supported. How would you store the values for efficient updates and retrievals ?
原题直接来吧
1 2 3
4 5 6
7 8 9



A. optimize for the case where updates are frequent - make update as fast as possible

Store the values in a 2D array - x and y are indexes into the array
To update O(1): array[x][y] = v
To sum O(n^2):
sum = 0
for (int x = x1; x <= x2; x++) {
  for (int y = y1; y <= y2; y++ {
    sum += array[x][y];
}
return sum;

.1point3acres缃
B. Optimize for the case where sums are frequent, updates are rare - make sum as fast as possible
[size=13.3333333333333px]

[size=13.3333333333333px]还有 个 c  就是如何 实现  O(1) sum  
[size=13.3333333333333px]

[size=13.3333333333333px]

[size=13.3333333333333px]我给小哥的刚开始的方法是 segment tree  小哥说可以,就是空间复杂度高了, 在小哥的提点下, 我说弄个 prefix  sum  for  each row,  然后小哥问 我时间复杂度,我说o(n)
[size=13.3333333333333px]我给的数组是这样的
arr[0][0]  = 1  arr[0][1] = 3 arr[0][2] = 6
arr[1][0] = 4   arr[1][1] = 9  arr[1][2] = 15
arr[2][0] = 7   arr[2][1] = 15 arr[2][2] = 24
[size=13.3333333333333px]小哥给我说了下 求sum 时间,我说o(N) 小哥说对,
[size=13.3333333333333px]然后对到了 第三问, 那能能快吗 , 我就 给了 个数组示例, 每个 cell 都是求前 i,j  的 sum. From 1point 3acres bbs

arr[0][0]  = 1  arr[0][1] = 3 arr[0][2] = 6
arr[1][0]  = 10  arr[1][1] =19  arr[1][2] =34
[size=13.3333333333333px]

[size=13.3333333333333px]然后给小哥了个公式, S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]
小哥说,可能是对的, 不确定,最后一个 S[x1][y1]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后小哥说,我是这样存的

arr[0][0]  = 1  arr[0][1] = 3 arr[0][2] = 6
arr[1][0]  = 5  arr[1][1] =12 arr[1][2] = 21
请注意列,. From 1point 3acres bbs
然后给了他的 解法方程 arr[x2][x2] - arr[x1-1][y2] - arr[x2][y1-1] + arr[x1-1][y1-1]


然后就结束了,  和地里的 这个帖子一样的 http://www.1point3acres.com/bbs/thread-140228-1-1.html
. 1point 3acres 璁哄潧只有这一题目,三个问题
附件是自己准备的google 看的面经, 我自己的想法,和一些问题的code , 不一定对,希望对大家有用 不. more info on 1point3acres.com
愉快的结束了
希望对以后的朋友面试有用 ,  大家加油,  面试信号不好, 求进onsite






7.pdf

254.95 KB, 下载次数: 147, 下载积分: 大米 -1 升

本帖被以下淘专辑推荐:

laurie洁 发表于 2015-8-29 03:33:37 | 显示全部楼层
答的很好诶~~学习了!!
回复 支持 反对

使用道具 举报

 楼主| donghao 发表于 2015-8-29 04:01:44 | 显示全部楼层
laurie洁 发表于 2015-8-29 03:33
答的很好诶~~学习了!!

还行吧,在小哥的提示下做的,半推半就,弄出来了,准备的过程挺长知识的
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-29 04:03:01 | 显示全部楼层
two sum 改进 貌似lintcode 有。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-29 04:03:25 | 显示全部楼层
blessed 楼主。
回复 支持 反对

使用道具 举报

 楼主| donghao 发表于 2015-8-29 04:17:27 | 显示全部楼层
hulahu 发表于 2015-8-29 04:03-google 1point3acres
blessed 楼主。

谢谢,等消息吧
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-29 06:32:47 | 显示全部楼层
多谢LZ分享,受教了
回复 支持 反对

使用道具 举报

xujun 发表于 2015-8-29 08:07:26 | 显示全部楼层
答的很好诶~~学习了!!
回复 支持 反对

使用道具 举报

zchang3 发表于 2015-8-29 08:15:37 | 显示全部楼层
二维树状数组...
回复 支持 反对

使用道具 举报

zxj1015 发表于 2015-8-30 17:29:52 | 显示全部楼层
能不能发我邮箱一份,我是新手,还没有米,下不了。1031665920@qq.com
回复 支持 反对

使用道具 举报

 楼主| donghao 发表于 2015-8-31 07:16:39 | 显示全部楼层
zxj1015 发表于 2015-8-30 17:29
能不能发我邮箱一份,我是新手,还没有米,下不了。

已经发送了
回复 支持 反对

使用道具 举报

wenzhu 发表于 2015-8-31 23:29:49 | 显示全部楼层
lz我也没有大米呀...求pdf~
hou103880@163.com
谢谢啦
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-8-31 23:33:53 | 显示全部楼层
赞一下 如此详细的面经。  满分面经。 希望楼主过了的话,告诉下大家。
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-2 02:48:03 | 显示全部楼层
楼主答的不错啊,应该过了吧?
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-3 13:22:29 | 显示全部楼层
啥是二维树状数组啊 ,祝lz好运
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-3 13:22:47 | 显示全部楼层
传说中的log (n) 的解法是啥
回复 支持 反对

使用道具 举报

wendyistutu 发表于 2015-9-8 06:11:00 | 显示全部楼层
楼主好人,我也没米,求帮助。wendyistutu@gmail.com
谢谢
回复 支持 反对

使用道具 举报

douch 发表于 2015-9-8 06:53:13 | 显示全部楼层
楼主好人啊
回复 支持 反对

使用道具 举报

qizy09 发表于 2015-11-25 20:43:41 | 显示全部楼层
太棒了,谢谢楼主
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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