Zenefits最新电面，含详细解法

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

面试时先介绍一下自己，问几个行为问题，然后讲题目思路，这样就差不多过了半小时，后面写程序时间有点紧，
所以介绍时尽量简短一点。
说思路的时候

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

/div>

3 + 1 + 3 = 7

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

刚面完了，也是这个题。这个题最优解法就是以每个robot为源点都做一遍bfs，然后把和加起来找个最小的……别再想别的了。

liyanjia92 发表于 2015-11-1 03:50
MST怎么做呢？能不能讲解一下。

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

aiuou 发表于 2015-11-1 11:46
这个点是一定保证存在的么，如果有个机器人被路障围起来了呢？

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

请问dis数组是什么结构，我能想到的是用hashtable, key的坐标,value是总距离

MCwong 发表于 2015-10-22 23:59
请问dis数组是什么结构，我能想到的是用hashtable, key的坐标,value是总距离

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

darkwowgamer 发表于 2015-10-23 01:24
dis应该就是二维数组, 直接在对应坐标存距离, 没必要hashtable吧?

理解了, thanks!

MCwong 发表于 2015-10-23 01:33
理解了, thanks!

其实最好是直接用原来的数组

kennethinsnow 发表于 2015-10-23 09:52
其实最好是直接用原来的数组

原数组是可以改变的,对吧？

楼主原数组是char数组吗？X是存成‘X’的？

这道题不能用minimum spanning tree的算法么？感觉很像哎？ 这样算法复杂度就可以到O(mlogn)了？

jyang_2015 发表于 2015-11-1 03:41
这道题不能用minimum spanning tree的算法么？感觉很像哎？ 这样算法复杂度就可以到O(mlogn)了？

MST怎么做呢？能不能讲解一下。