一亩三分地论坛

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

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

谷沟新鲜面经

[复制链接] |试试Instant~ |关注本帖
Gates_ice 发表于 2015-2-26 03:07:37 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Other

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

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

x
新鲜的

两道题

1. 数组做差,从第一个数组中去掉第二个数组中出现过得元素,多次出现的,那就去掉和第二个数组中出现次数一样的数量

2. 矩阵中求某些房间和某些特定房间的距离的问题,果断是DP啦
. visit 1point3acres.com for more.
时间卡的很准,第二道题没有写完代码,不过面试官说基本明白我的思路了,强行打断问我复杂度是多少

面试官,三哥哥,略虚。家里信号不太好,对面说话太模糊,各种parden,然后就在gdoc上写……

总体来说略虚,求赞人品来onsite


补充内容 (2015-2-26 05:01):
2个小时后收到邮件,已得到onsite机会

补充内容 (2015-2-27 01:24):
完全看不懂楼层名字……第二题的详细内容在地基那层

评分

3

查看全部评分

 楼主| Gates_ice 发表于 2015-2-27 01:23:23 | 显示全部楼层
fangl086 发表于 2015-2-26 09:25
2. 矩阵中求某些房间和某些特定房间的距离的问题,果断是DP啦
没想明白这题怎么dp,公式什么样的?

题目的意思是,一个博物馆,有N乘以N个房间,每个房间有OPEN,CLOSED两种状态

如果CLOSED,说明房间不能进人也不能出人

如果OPEN,则可能有守卫在里面,也可能没有守卫
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给定N的大小,还有哪些房间CLOSED,哪些房间有守卫

输出:一个N乘以N的矩阵,每个元素的值是这个房间距离最近的守卫的距离

补充内容 (2015-2-27 01:25):
所以DP的方法就是每个房间从它周围四个(可能三个可能两个)房间中OPEN的房间的值+1 即可

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

唯一 发表于 2015-2-26 05:58:57 | 显示全部楼层
明天电面。。希望一切顺利~~祝楼主onsite好运!
回复 支持 反对

使用道具 举报

houqingniao 发表于 2015-2-26 06:19:07 | 显示全部楼层
第二题啥意思?DP?
回复 支持 反对

使用道具 举报

silverwind 发表于 2015-2-26 08:01:02 | 显示全部楼层
恭喜啊,我也发现从那边打电话来信号不太好,对面说话会断断续续
回复 支持 反对

使用道具 举报

 楼主| Gates_ice 发表于 2015-2-26 09:15:44 | 显示全部楼层
houqingniao 发表于 2015-2-26 06:19
第二题啥意思?DP?

第二道题就是在求一个矩阵中每一个元素距离矩阵中有特定属性的元素的最近距离,典型的Dynamic Programming
. Waral 鍗氬鏈夋洿澶氭枃绔,
不过也可以BFS
回复 支持 反对

使用道具 举报

fangl086 发表于 2015-2-26 09:25:08 | 显示全部楼层
2. 矩阵中求某些房间和某些特定房间的距离的问题,果断是DP啦
没想明白这题怎么dp,公式什么样的?
回复 支持 反对

使用道具 举报

fangl086 发表于 2015-2-27 01:49:48 | 显示全部楼层
Gates_ice 发表于 2015-2-27 01:23
题目的意思是,一个博物馆,有N乘以N个房间,每个房间有OPEN,CLOSED两种状态

如果CLOSED,说明房间不 ...

对啊,你扫描NxN数组的时候,要么从上到小,要么从下到上,如果从上到下,好像就没有更新到下面的距离只更新了到上面的距离。
回复 支持 反对

使用道具 举报

yolkfive 发表于 2015-2-27 03:12:08 | 显示全部楼层
同不明白lz说的dp是什么意思,是从守卫出发哪,还是(0,0)到(n,n)
回复 支持 反对

使用道具 举报

 楼主| Gates_ice 发表于 2015-2-27 08:41:42 | 显示全部楼层
fangl086 发表于 2015-2-27 01:49.鏈枃鍘熷垱鑷1point3acres璁哄潧
对啊,你扫描NxN数组的时候,要么从上到小,要么从下到上,如果从上到下,好像就没有更新到下面的距离只 ...

所以我当时是写了一个函数做递归调用,然后函数外扫一遍grid,已经求出来的就不需要了,没有求出来的就调用这个函数

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

refurbish 发表于 2015-3-3 02:07:47 | 显示全部楼层
Gates_ice 发表于 2015-2-27 08:41
所以我当时是写了一个函数做递归调用,然后函数外扫一遍grid,已经求出来的就不需要了,没有求出来的就调 ...

那你这个时间复杂度是多少呢?

还可以直接从四个角分别扫一次,然后每次DP[j]取当前以及周围四个方向+1的最小值,这样复杂度能保证是O(n^2)

补充内容 (2015-3-3 02:08):
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷DP【i】【j】
回复 支持 反对

使用道具 举报

 楼主| Gates_ice 发表于 2015-3-3 02:09:56 | 显示全部楼层
refurbish 发表于 2015-3-3 02:07. 鍥磋鎴戜滑@1point 3 acres
那你这个时间复杂度是多少呢?

还可以直接从四个角分别扫一次,然后每次DP[j]取当前以及周围四个方向+ ...
. visit 1point3acres.com for more.
对啊, 每个cell都会扫描一遍
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-9 03:37:58 | 显示全部楼层
refurbish 发表于 2015-3-3 02:07
那你这个时间复杂度是多少呢?

还可以直接从四个角分别扫一次,然后每次DP[j]取当前以及周围四个方向+ ...

是不是可以只从两个对角顶点开始扫描,而不是四个角,因为从左上,就可以确定当前值是左上两个方向的最小值,再从右下,就可以确定当前值是右下的最小值,然后和左上的结果比较。而且不用递归。时间复杂度是n^2,空间是n^2
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-9 03:38:58 | 显示全部楼层
数组做差,从第一个数组中去掉第二个数组中出现过得元素,多次出现的,那就去掉和第二个数组中出现次数一样的数量.
这个将两数组排序,然后比较?还是使用hash保存第二个数组的值?
回复 支持 反对

使用道具 举报

 楼主| Gates_ice 发表于 2015-3-9 03:44:32 | 显示全部楼层
mm豆 发表于 2015-3-9 03:38
数组做差,从第一个数组中去掉第二个数组中出现过得元素,多次出现的,那就去掉和第二个数组中出现次数一样 ...

hash第二个数组,key是元素,value是它的次数
然后开始处理第一个数组
回复 支持 反对

使用道具 举报

mm豆 发表于 2015-3-9 03:59:30 | 显示全部楼层
Gates_ice 发表于 2015-3-9 03:44. from: 1point3acres.com/bbs
hash第二个数组,key是元素,value是它的次数
然后开始处理第一个数组

明白了 十分感谢。 dp那道题的解法对不对?
是不是可以只从两个对角顶点开始扫描,而不是四个角,因为从左上,就可以确定当前值是左上两个方向的最小值,再从右下,就可以确定当前值是右下的最小值,然后和左上的结果比较。而且不用递归。时间复杂度是n^2,空间是n^2
回复 支持 反对

使用道具 举报

 楼主| Gates_ice 发表于 2015-3-9 05:22:10 来自手机 | 显示全部楼层
差不多 理论上从哪扫描都无所谓
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-3-9 07:08:45 | 显示全部楼层
第二题是从所有的守卫那里做一次BFS吧
回复 支持 反对

使用道具 举报

averillzheng 发表于 2015-3-9 09:34:52 | 显示全部楼层
第二题的dp不知道怎么搞?我第一直觉是bfs。
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-3-9 12:36:22 | 显示全部楼层
mm豆 发表于 2015-3-9 03:37
是不是可以只从两个对角顶点开始扫描,而不是四个角,因为从左上,就可以确定当前值是左上两个方向的最小 ...

对的,两个对角应该就可以了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 22:42

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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