Google 6/14 二轮店面

只有一道题，题目跟leetcode算一定range的matrix很像。
给一个matrix存了一堆数。
给两个function，一个 set(int x, int y, int value

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

为了Onsite顺利攒人品！！！顺路说一下，LZ面的是Seattle/Kirkland的职位~

hyj143 发表于 2016-6-30 05:07
这个我觉得不能叫做 sum  比 update 快吧？
因为 在 update的时候， 复杂度太高了， 以至于 比sum还高了

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

readman 发表于 2016-6-30 04:49
简单啊...你看看lc那个range sum query,
二维的话, set就是O(n2), query是O(1)

这个我觉得不能叫做 sum  比 update 快吧？
因为 在 update的时候， 复杂度太高了， 以至于 比sum还高了

native 的方法:
add O(1): 二维数组 random access
sum O(n^2) 遍历二维数组

fenwick tree
add O(lgm) m is the max length of digits in binary of max value in array
sum 同上..


楼主运气不错啊..这题应该是电面最简单的了

请问sum有什么办法比set快呢？

请问楼主男生还是女生啊？ 谢谢啊

我也想知道 怎么才能使 sum 比 Update 更快

hyj143 发表于 2016-6-30 04:06
我也想知道 怎么才能使 sum 比 Update 更快

简单啊...你看看lc那个range sum query,
二维的话, set就是O(n2), query是O(1)

wsliubw 发表于 2016-6-29 22:39
请问楼主男生还是女生啊？ 谢谢啊

男生女生有啥影响吗

ofdk88 发表于 2016-6-29 23:43
请问楼主第一次电面完，多长时间来的Onsite?

额，我这是第二轮电面了，等了两周收到Onsite