一亩三分地论坛

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

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

Zenefits最新电面,含详细解法

[复制链接] |试试Instant~ |关注本帖
kennethinsnow 发表于 2015-10-22 10:34:39 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Zenefits - 内推 - 技术电面 |Other在职跳槽

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

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

x
老题目,到所有机器人距离和最小的点,
一个matrix, 1代表机器人,0代表通路,x代表路障,求到所有机器人距离和最小的一点. 1point 3acres 璁哄潧
需要注意的是机器人本身也是通路的一部分,可以通过他到达其他机器人,甚至最小点
也可以和机器人在同一个点上。
另外如果被路障围起来的点不能被算进来. from: 1point3acres.com/bbs

面试时先介绍一下自己,问几个行为问题,然后讲题目思路,这样就差不多过了半小时,后面写程序时间有点紧,. 鍥磋鎴戜滑@1point 3 acres
所以介绍时尽量简短一点。
说思路的时候,说了bfs, dfs,面试官说bfs好,又问内存用多少,答O(m*n), 要求节省内存,但我没有想出来不用queue做bfs,
现在想内存最多是O(m + n)应该已经很好了。不过后来又用了一个存距离和判断访问过的二维数组,所以应该还是需要O(m*n),
不知道有什么办法节省。后来面试官没有深究。
基本思路就是找到一个机器人位置,从这点开始bfs, 把所有点到这个机器人的距离加到dis数组,最后扫一遍看看谁距离最短就返回
这点。-google 1point3acres

/*//problem: robot merge point
//input:
//robot: 1
//obstacle: X
[
0   0   0   M   1
0   1   X   0   0
0   X   0   0   0
0   0   0   1   0
0   0   0   0   0
//output:
//best merge point: M
3 + 1 + 3 = 7

Definition: Best merge point: minimal sum of path num between robots and merge point*/

. visit 1point3acres.com for more.

评分

2

查看全部评分

本帖被以下淘专辑推荐:

wegnahz 发表于 2015-11-10 08:14:47 | 显示全部楼层
刚面完了,也是这个题。这个题最优解法就是以每个robot为源点都做一遍bfs,然后把和加起来找个最小的……别再想别的了。
回复 支持 1 反对 0

使用道具 举报

MCwong 发表于 2015-10-22 23:59:56 | 显示全部楼层
请问dis数组是什么结构,我能想到的是用hashtable, key的坐标,value是总距离
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-10-23 01:24:53 | 显示全部楼层
MCwong 发表于 2015-10-22 23:59
请问dis数组是什么结构,我能想到的是用hashtable, key的坐标,value是总距离

dis应该就是二维数组, 直接在对应坐标存距离, 没必要hashtable吧?
回复 支持 反对

使用道具 举报

MCwong 发表于 2015-10-23 01:33:55 | 显示全部楼层
darkwowgamer 发表于 2015-10-23 01:24. visit 1point3acres.com for more.
dis应该就是二维数组, 直接在对应坐标存距离, 没必要hashtable吧?

理解了, thanks!
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-10-23 09:52:40 | 显示全部楼层

其实最好是直接用原来的数组
回复 支持 反对

使用道具 举报

MCwong 发表于 2015-10-23 10:30:44 | 显示全部楼层
kennethinsnow 发表于 2015-10-23 09:52
其实最好是直接用原来的数组

原数组是可以改变的,对吧?
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-10-26 23:51:17 | 显示全部楼层
楼主原数组是char数组吗?X是存成‘X’的?
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-1 03:41:52 | 显示全部楼层
这道题不能用minimum spanning tree的算法么?感觉很像哎? 这样算法复杂度就可以到O(mlogn)了?
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-11-1 03:50:06 | 显示全部楼层
jyang_2015 发表于 2015-11-1 03:41
这道题不能用minimum spanning tree的算法么?感觉很像哎? 这样算法复杂度就可以到O(mlogn)了?
. From 1point 3acres bbs
MST怎么做呢?能不能讲解一下。
回复 支持 反对

使用道具 举报

jyang_2015 发表于 2015-11-1 11:28:35 | 显示全部楼层
liyanjia92 发表于 2015-11-1 03:50
MST怎么做呢?能不能讲解一下。

嗯 又想了一下 MST应该不好做,我之前看到算最小距离之和直觉就感觉是不是MST。暂时能想到的也只是brute-force 的每个点进行BFS。但这样感觉效率很低哎,而且会重复计算之前遍历过的robot pair。大家还有更好的方法么?
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-11-1 11:46:47 | 显示全部楼层
这个点是一定保证存在的么,如果有个机器人被路障围起来了呢?
回复 支持 反对

使用道具 举报

 楼主| kennethinsnow 发表于 2015-11-1 11:55:58 | 显示全部楼层
aiuou 发表于 2015-11-1 11:46
这个点是一定保证存在的么,如果有个机器人被路障围起来了呢?

问得好,我也没有来得及问面试官。
不过如果不保证所有机器人都在一个联通域,那任何点到都不可能到达所有机器人,所以也就不存在最近的点了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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