一亩三分地论坛

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

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

Google 6/14 二轮店面

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

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

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

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

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

二轮店面其实不难,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. visit 1point3acres.com for more.
add O(lgm) m is the max length of digits in binary of max value in array
sum 同上... Waral 鍗氬鏈夋洿澶氭枃绔,
. from: 1point3acres.com/bbs

楼主运气不错啊..这题应该是电面最简单的了
回复 支持 反对

使用道具 举报

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. 1point3acres.com/bbs
我也想知道 怎么才能使 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.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个我觉得不能叫做 sum  比 update 快吧?
因为 在 update的时候, 复杂度太高了, 以至于 比sum还高了
. more info on 1point3acres.com
我不理解也在这里,搞半天= =,但后来发现他就是想让你用set来算然后sum直接query。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 00:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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