一亩三分地论坛

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

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

[找工就业] Google电面新题

[复制链接] |试试Instant~ |关注本帖
悲伤网管 发表于 2015-4-30 01:30:42 | 显示全部楼层 |阅读模式

2015(4-6月)-[]CS硕士+fresh grad 无实习/全职 - 内推| 码农类全职@Googlefresh grad应届毕业生

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

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

x
最近面了Google电面,第一轮,一道设计题。

一个二维数组,有两个方法可以调用,一个是替换二维数组某个位置的值,一个是计算给定矩阵内部所有数字的和,如果替换操作很多,计算和的操作相对较少,如何优化这两个方法。-google 1point3acres

面试结束时的解法是预先计算一些小方块内部数字的和,然后由小方块拼凑成给定矩阵,最后根据替换的值算差值,得出最终的结果。
. 1point3acres.com/bbs
期间面试官一直在提醒,没有写代码,只写了几行注释。

不知还有没有更好的做法?
wangxinlei 发表于 2015-4-30 02:42:54 | 显示全部楼层
没懂题目的要求啊?最后要求是输出什么啊?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-4-30 02:44:58 | 显示全部楼层
wangxinlei 发表于 2015-4-30 02:42
没懂题目的要求啊?最后要求是输出什么啊?

输出的是这个二维数组中给定矩阵范围内数字的和,方法的参数可以是矩阵的两个顶点和二维数组
回复 支持 反对

使用道具 举报

wangxinlei 发表于 2015-4-30 02:48:23 | 显示全部楼层
哦。。。所以替换操作的意义就是把不在范围内的数字替换成在范围内的数字,然后总的和减去差值?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-4-30 02:51:54 | 显示全部楼层
wangxinlei 发表于 2015-4-30 02:48
哦。。。所以替换操作的意义就是把不在范围内的数字替换成在范围内的数字,然后总的和减去差值?

替换是更新某个位置的值,参数可以是坐标和新值,怎么计算矩阵的和是自己设计的
回复 支持 反对

使用道具 举报

flyskyfly 发表于 2015-5-9 08:25:51 | 显示全部楼层
对啊 ,感觉只要是计算总和,然后每次更新和的差值就行吧?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-5-9 08:52:09 | 显示全部楼层
flyskyfly 发表于 2015-5-9 08:25
对啊 ,感觉只要是计算总和,然后每次更新和的差值就行吧?

差不多,聊了一些优化的具体细节
回复 支持 反对

使用道具 举报

joybing 发表于 2015-5-15 02:52:54 | 显示全部楼层
第二个方法的输入参数是用什么表示给定的矩阵的?
回复 支持 反对

使用道具 举报

joybing 发表于 2015-5-15 03:13:07 | 显示全部楼层
joybing 发表于 2015-5-15 02:52
第二个方法的输入参数是用什么表示给定的矩阵的?

看了回复,大概知道了,可以用对角线上的两个点 和 原二维数组作为输入参数
回复 支持 反对

使用道具 举报

头像被屏蔽
shqyking 发表于 2015-5-23 12:11:41 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

icey_hs 发表于 2015-5-24 01:48:42 | 显示全部楼层
请问楼主是 technical phone interview 么?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-5-24 03:58:32 | 显示全部楼层
icey_hs 发表于 2015-5-24 01:48
请问楼主是 technical phone interview 么?

全职的电面
回复 支持 反对

使用道具 举报

八月槎 发表于 2015-5-27 06:41:45 | 显示全部楼层
“小方块”需要满足什么要求吗?怎么能保证给定的矩阵就一定能由你设定的小方块组成?
回复 支持 反对

使用道具 举报

sunnycat 发表于 2015-5-27 09:06:49 | 显示全部楼层
是面试哪个team?
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-5-27 13:40:38 | 显示全部楼层
八月槎 发表于 2015-5-27 06:41
“小方块”需要满足什么要求吗?怎么能保证给定的矩阵就一定能由你设定的小方块组成?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不能保证,后面还得分割,就是说说想法
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-5-27 13:40:47 | 显示全部楼层
sunnycat 发表于 2015-5-27 09:06.1point3acres缃
是面试哪个team?

new grad的
回复 支持 反对

使用道具 举报

dangertrip 发表于 2015-5-27 17:39:50 来自手机 | 显示全部楼层
二维线段树可以么,修改O(lgn),查询O(1)
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-5-28 02:28:50 | 显示全部楼层
dangertrip 发表于 2015-5-27 17:39
二维线段树可以么,修改O(lgn),查询O(1)

我不懂二维线段树,应该更好吧
回复 支持 反对

使用道具 举报

dangertrip 发表于 2015-5-28 08:16:32 | 显示全部楼层
悲伤网管 发表于 2015-5-28 02:28
我不懂二维线段树,应该更好吧

其实你的想法就差不多的
回复 支持 反对

使用道具 举报

 楼主| 悲伤网管 发表于 2015-5-28 08:25:43 | 显示全部楼层
dangertrip 发表于 2015-5-28 08:16
其实你的想法就差不多的

后来在论坛上看了一下,这题好几个人都面过,差不多都是这个方向
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 17:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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