一亩三分地论坛

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

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

Google家电面

[复制链接] |试试Instant~ |关注本帖
isophia0729 发表于 2015-4-21 03:00:59 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Googleg家电面面经 - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
印度口音很重的女生。
1. java基础知识,不难。interface是什么,为什么用interface不用abstract class, interface有什么缺点。.鐣欏璁哄潧-涓浜-涓夊垎鍦
2. 给一个矩阵,返回一个新的矩阵,新矩阵里面的元素是原矩阵的元素左上角矩阵所有元素之和。给[[1 2 3] [2 3 1] [2 1 3]],返回[[1 3 6] [3 8 12] [5 11 18]]。写出代码以后问复杂度,O(mn),然后问能不能优化,实在没想出来,就问能不能给点提示。她说that's ok,然后就下一道题了。
3. 01矩阵,给一个位置,比如这个位置上的元素是0,返回与他上下左右相邻的所有0的个数,不包括对角上的元素,要求只写出伪代码即可。和leetcode原题有点像,但不完全一样,所以想了一下就写出来了。问了问复杂度,O(mn)。
-google 1point3acres
然后就是问问题,问了几个常规的。然后就挂了,面试了55分钟。

希望能有后续面试~~

评分

3

查看全部评分

yellowrabbit 发表于 2015-5-1 02:26:51 | 显示全部楼层
isophia0729 发表于 2015-4-30 23:10
我就是这样做的,我一直以为这样就是暴力的做法非cs专业转码农基础不扎实啊~~

哦哦,,恩,那这样就对了,,说暴力也不能说完全错,DP实际上本质就是TRY OUT EVERYTHING

补充内容 (2015-5-1 02:27):
那这样了,还能怎么优化,填答案不用花时间?搞笑的面试官
回复 支持 1 反对 0

使用道具 举报

woshiee123 发表于 2015-4-25 02:38:36 | 显示全部楼层
最后一题那个是只和当前元素连接 还是可以和当前元素连接的元素连接
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-4-25 02:42:43 | 显示全部楼层
woshiee123 发表于 2015-4-25 02:38
最后一题那个是只和当前元素连接 还是可以和当前元素连接的元素连接

所有的连接,就是说一片不间断的0或者1有几个。
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-4-25 02:56:34 | 显示全部楼层
isophia0729 发表于 2015-4-25 02:42
所有的连接,就是说一片不间断的0或者1有几个。

这个貌似很像leetcode的新题 the number of islands, 还有弱问楼主 第一题就是暴力解决么。。。
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-4-25 03:00:32 | 显示全部楼层
woshiee123 发表于 2015-4-25 02:56. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个貌似很像leetcode的新题 the number of islands, 还有弱问楼主 第一题就是暴力解决么。。。

最近出了好多新题,都突破200道了,好多还没来得及做。第一题就是暴力做的,面试官让我优化,我没优化出来,求提示,她说that's OK, 就直接下一道题了。
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-4-25 03:12:35 | 显示全部楼层
isophia0729 发表于 2015-4-25 03:00
最近出了好多新题,都突破200道了,好多还没来得及做。第一题就是暴力做的,面试官让我优化,我没优化出 ...

谢谢楼主 good luck!!!!
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-4-25 03:27:12 | 显示全部楼层
woshiee123 发表于 2015-4-25 03:12
谢谢楼主 good luck!!!!

嗯嗯,一起加油,祝我们都能拿到offer!!
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-27 13:08:43 | 显示全部楼层
第一题可以DP啊。。。不过DP的复杂度也是O(mn) m是row个数,n是col个数
回复 支持 反对

使用道具 举报

yellowrabbit 发表于 2015-4-30 17:27:34 | 显示全部楼层
wangxinlei 发表于 2015-4-27 13:08-google 1point3acres
第一题可以DP啊。。。不过DP的复杂度也是O(mn) m是row个数,n是col个数
. 鍥磋鎴戜滑@1point 3 acres
我觉得他应该连复杂度也说错了,因为前面回复,他说用暴力做,暴力绝对不是mn的时间复杂度。。这题应该就是考dp, board[j] = board[i-1][j] + board[j-1] - board[i-1][j-1]
回复 支持 反对

使用道具 举报

offerget 发表于 2015-4-30 17:30:52 | 显示全部楼层
“然后就挂了”
。。。。。。
回复 支持 反对

使用道具 举报

hahahengheng 发表于 2015-4-30 22:57:31 | 显示全部楼层
暴力复杂度应该是O((mn)^2), DP 就是经典的submatrix sum问题,cc150上一道矩阵题的preprocess
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-4-30 23:10:53 | 显示全部楼层
yellowrabbit 发表于 2015-4-30 17:27
我觉得他应该连复杂度也说错了,因为前面回复,他说用暴力做,暴力绝对不是mn的时间复杂度。。这题应该就 ...

我就是这样做的,我一直以为这样就是暴力的做法非cs专业转码农基础不扎实啊~~
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-4-30 23:11:31 | 显示全部楼层
hahahengheng 发表于 2015-4-30 22:57
暴力复杂度应该是O((mn)^2), DP 就是经典的submatrix sum问题,cc150上一道矩阵题的preprocess

我就是这样做的,我一直以为这样就是暴力的做法非cs专业转码农基础不扎实啊~~
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-4-30 23:12:28 | 显示全部楼层
offerget 发表于 2015-4-30 17:30.鏈枃鍘熷垱鑷1point3acres璁哄潧
“然后就挂了”
。。。。。。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
哈哈,这样说好像不太吉利,我意思是说挂电话啦
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-5-1 02:29:46 | 显示全部楼层
yellowrabbit 发表于 2015-5-1 02:26
哦哦,,恩,那这样就对了,,说暴力也不能说完全错,DP实际上本质就是TRY OUT EVERYTHING

补充内容 (20 ...

嗯,我也是不知道怎么优化,冷场了快一分钟,就问她给点提示,她就说OK直接下一题了。
回复 支持 反对

使用道具 举报

hahahengheng 发表于 2015-5-1 07:36:28 | 显示全部楼层
isophia0729 发表于 2015-5-1 02:29
嗯,我也是不知道怎么优化,冷场了快一分钟,就问她给点提示,她就说OK直接下一题了。

她是让你在O(mn) 基础上再优化?
回复 支持 反对

使用道具 举报

 楼主| isophia0729 发表于 2015-5-4 03:48:08 | 显示全部楼层
hahahengheng 发表于 2015-5-1 07:36. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
她是让你在O(mn) 基础上再优化?
. 鍥磋鎴戜滑@1point 3 acres
是的。字数字数字数字数字数字数~~
回复 支持 反对

使用道具 举报

magicalcan 发表于 2015-5-4 16:37:53 | 显示全部楼层
yellowrabbit 发表于 2015-4-30 17:27
我觉得他应该连复杂度也说错了,因为前面回复,他说用暴力做,暴力绝对不是mn的时间复杂度。。这题应该就 ...

这个算式最后还要加上原矩阵的【 i 】【j】才行吧,不然差个数
回复 支持 反对

使用道具 举报

yellowrabbit 发表于 2015-5-4 17:22:02 | 显示全部楼层
magicalcan 发表于 2015-5-4 16:37
这个算式最后还要加上原矩阵的【 i 】【j】才行吧,不然差个数

恩是,就那个意思,少写了一个。。太晚睡了。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 22:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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