亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1724|回复: 10
收起左侧

Google 6/14 二轮店面

[复制链接] |试试Instant~ |关注本帖
llsshh1128 发表于 2016-6-29 15:28:56 | 显示全部楼层 |阅读模式

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

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

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

x
只有一道题,题目跟leetcode算一定range的matrix很像。
给一个matrix存了一堆数。
给两个function,一个 set(int x, int y, int value),一个sum(int x, int y)。. 1point3acres.com/bbs
set那个function用来改某个位置的value,sum是算从(0,0)到(x,y)的所有数的和。
问能不能写一种方法让sum的速度比set快,一路update就可以。

-google 1point3acres二轮店面其实不难,LZ一开始理解错意思了,后来解出来了,但怕因为面试官觉得前面交流不好就不开心= =等了两周HR打电话来说准备约Onsite,大写的感人QAQ
为了Onsite顺利攒人品!!!顺路说一下,LZ面的是Seattle/Kirkland的职位~

评分

2

查看全部评分

YongHaoHu 发表于 2016-6-29 18:06:03 | 显示全部楼层
请问sum有什么办法比set快呢?
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-29 22:28:47 | 显示全部楼层
native 的方法:.鐣欏璁哄潧-涓浜-涓夊垎鍦
add O(1): 二维数组 random access
sum O(n^2) 遍历二维数组

fenwick tree.鏈枃鍘熷垱鑷1point3acres璁哄潧
add O(lgm) m is the max length of digits in binary of max value in array
sum 同上..
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 楼主运气不错啊..这题应该是电面最简单的了
回复 支持 反对

使用道具 举报

wsliubw 发表于 2016-6-29 22:39:52 | 显示全部楼层
请问楼主男生还是女生啊? 谢谢啊
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-6-30 04:06:23 | 显示全部楼层
我也想知道 怎么才能使 sum 比 Update 更快
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-30 04:49:55 | 显示全部楼层
hyj143 发表于 2016-6-30 04:06
我也想知道 怎么才能使 sum 比 Update 更快
.鐣欏璁哄潧-涓浜-涓夊垎鍦
简单啊...你看看lc那个range sum query,
二维的话, set就是O(n2), query是O(1)
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-6-30 05:07:20 | 显示全部楼层
readman 发表于 2016-6-30 04:49
简单啊...你看看lc那个range sum query,
二维的话, set就是O(n2), query是O(1)

这个我觉得不能叫做 sum  比 update 快吧?
因为 在 update的时候, 复杂度太高了, 以至于 比sum还高了
回复 支持 反对

使用道具 举报

 楼主| llsshh1128 发表于 2016-6-30 05:24:44 | 显示全部楼层
wsliubw 发表于 2016-6-29 22:39
请问楼主男生还是女生啊? 谢谢啊

男生女生有啥影响吗
回复 支持 反对

使用道具 举报

 楼主| llsshh1128 发表于 2016-6-30 05:25:11 | 显示全部楼层
ofdk88 发表于 2016-6-29 23:43
请问楼主第一次电面完,多长时间来的Onsite?

额,我这是第二轮电面了,等了两周收到Onsite
回复 支持 反对

使用道具 举报

 楼主| llsshh1128 发表于 2016-6-30 05:26:29 | 显示全部楼层
hyj143 发表于 2016-6-30 05:07. 1point 3acres 璁哄潧
这个我觉得不能叫做 sum  比 update 快吧? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
因为 在 update的时候, 复杂度太高了, 以至于 比sum还高了

我不理解也在这里,搞半天= =,但后来发现他就是想让你用set来算然后sum直接query。。。
回复 支持 反对

使用道具 举报

robinali 发表于 2016-6-30 14:14:55 | 显示全部楼层
谢谢分享&恭喜楼主!
面试好运!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-17 23:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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