一亩三分地论坛

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

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

刚刚结束的谷歌电面

[复制链接] |试试Instant~ |关注本帖
muancy 发表于 2015-11-4 07:01:19 | 显示全部楼层 |阅读模式

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

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

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

x
刚刚结束的电面,一个小哥打来的,迟到了整整30分钟,上来没有解释,没有say sorry。

直接上题:一道很常见的面试题, 求二维矩阵里面 两个坐标范围内的submatrix的总和。心中窃喜,昨晚刚准备过的。
. 1point3acres.com/bbs
然后就直接写代码,用2维树状数组来做,然后20分钟不到做完了。 .鏈枃鍘熷垱鑷1point3acres璁哄潧

然后就下来的就是各种悲剧:. more info on 1point3acres.com

首先那个小哥说从来没听过树状数组,叫我解释下,然后我就从1维的开始解释,然后解释到2维,可能我表达能力不行,然后小哥也是似懂非懂,
然后就开始用数据来验证我的代码,然后就各种set update,然后还有我一点一点的show 树状数组里面的内容。  到最后还没验证完对错,时间到了,随便问了个问题就挂了。. from: 1point3acres.com/bbs

感觉跪了,因为面试官根本没办法知道我做的是对的还是错的。。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
只是建议后面面的同学,不用一上来就给树状数组的解法,慢慢来,如果硬是要求lgn的时间复杂度再用吧。
. 1point3acres.com/bbs
哎,这样悲剧的比较郁闷,move on吧

本帖被以下淘专辑推荐:

Ziyan 发表于 2015-11-4 07:07:21 | 显示全部楼层
patpat  可能过两天就收到onsite邀请了  感觉电面还是比较容易过的 应该不至于说他还没弄懂就否决你的做法   我也觉得二维树状数组很有可能面试官都不知道 所以确实是还有follow up的时候再提一下比较好
回复 支持 反对

使用道具 举报

curry97 发表于 2015-11-4 07:15:57 | 显示全部楼层
没有修改的话不用树状数组吧 直接n^2预处理然后O(1)回答询问吧
回复 支持 反对

使用道具 举报

 楼主| muancy 发表于 2015-11-4 07:20:53 | 显示全部楼层
curry97 发表于 2015-11-3 15:15
没有修改的话不用树状数组吧 直接n^2预处理然后O(1)回答询问吧

前几天一个帖子里面有人贴出来了几个答案,还不错,应该稍微翻翻就能翻到
回复 支持 反对

使用道具 举报

 楼主| muancy 发表于 2015-11-4 07:21:36 | 显示全部楼层
Ziyan 发表于 2015-11-3 15:07
patpat  可能过两天就收到onsite邀请了  感觉电面还是比较容易过的 应该不至于说他还没弄懂就否决你的做法  ...

对啊,他说从没听说过,所以只有从一维的慢慢解释
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-4 07:26:40 | 显示全部楼层
楼主应该和面试官讨论下你的approach。。先讨论解法。。讨论完了。。然后再implement。。这时候解释会容易的多
回复 支持 反对

使用道具 举报

 楼主| muancy 发表于 2015-11-4 07:39:41 | 显示全部楼层
leixiang5 发表于 2015-11-3 15:26
楼主应该和面试官讨论下你的approach。。先讨论解法。。讨论完了。。然后再implement。。这时候解释会容易 ...

我最开始说运用树状数组怎样,然后讲思路。  感觉他没怎么明白,就说:你先写吧。  一边写我还一边问: make sense?他就一直说: go on....  然后 = =
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-11-4 07:41:20 | 显示全部楼层
muancy 发表于 2015-11-4 07:39. Waral 鍗氬鏈夋洿澶氭枃绔,
我最开始说运用树状数组怎样,然后讲思路。  感觉他没怎么明白,就说:你先写吧。  一边写我还一边问: m ...

淡定。。也许就过了。。
回复 支持 反对

使用道具 举报

curry97 发表于 2015-11-4 07:51:13 | 显示全部楼层
muancy 发表于 2015-11-4 07:20
前几天一个帖子里面有人贴出来了几个答案,还不错,应该稍微翻翻就能翻到

我说一下我的想法 如果我没有理解错的话 :). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

设给的矩阵为a[][],首先求一个f[j] = sigma a[1][1]..a[j],具体求法可以利用递推:f[j] = a[j] + f[i-1][j] + f[j-1] - f[i-1][j-1]
.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后对于一个询问 sigma a[x1][y1]..a[x2][y2](x1<=x2,y1<=y2),首先--x1,--y1,然后答案就等于f[x2][y2] - f[x1][y2] - f[x2][y1] + f[x1][y1]

补充内容 (2015-11-4 08:01):
公式没显示全 f[j] = a[1][1]..a[j]的和,递推:f[j] = a[j] + f[i-1][j] + f[j-1] - f[i-1][j-1]
.1point3acres缃
补充内容 (2015-11-4 08:07):
f(i,j) = a(1,1) .. a(i,j)的和 递推:f(i,j) = a(i,j) + f(i-1,j) + f(i,j-1) - f(i-1,j-1)
回复 支持 反对

使用道具 举报

 楼主| muancy 发表于 2015-11-4 08:11:10 | 显示全部楼层
curry97 发表于 2015-11-3 15:51
我说一下我的想法 如果我没有理解错的话 :)

设给的矩阵为a[][],首先求一个f[j] = sigma a[1][1]..a[j ...

最后的补充是对的,这题感觉最后的递推公式都一样,不一样的只是怎么就不同点的和
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2015-11-4 08:34:28 | 显示全部楼层
LZ第一题是这道http://www.lintcode.com/en/problem/submatrix-sum/

补充内容 (2015-11-4 08:34):
吗?
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-11-18 03:55:18 | 显示全部楼层
jmnjmnjmn 发表于 2015-11-4 08:34
LZ第一题是这道http://www.lintcode.com/en/problem/submatrix-sum/. 鍥磋鎴戜滑@1point 3 acres

补充内容 (2015-11-4 08:34):

看描述貌似不是,应该是给任意两个点,作为子矩阵的左上和右下角,然后求这个子矩阵的所有元素的和吧。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 01:11:16 | 显示全部楼层
这个问题感觉可以做到O(m) query,  O(n) update就够了吧
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-12-7 03:04:36 | 显示全部楼层
应该没什么问题, 你做出来了就不会跪。 你可以给Recruiter 写邮件详细说明一下情况。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 16:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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