狗家自行车题超级无敌加强版

今天面了狗家，出了个自行车题，一开始听到题目我是窃喜的。

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

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

总之整个面试过程就像我上面写的一样乱，中间没有给任何hint。想问下地里各位大佬这个题到底要怎么做。如果非要用匈牙利算法那我认栽。但是就这么把我挂了我实在不甘心。另外遇到这种情况（面试官完全不配合不给hint）能不能向recuiter要求再面一轮？要是这个feedback送到hc估计已经凉了。


补充内容 (2018-10-10 06:32):
最小匹配brute force应该是O(k!)
另外lz还提到了stable match, 老哥说这个和你全局最优没啥区别……

很简单的DFS题啊，

n个人和n辆车的坐标都有了，存到array或list里都可以，

距离就用 |x1 - x2| + |y1 - y2| 来得到，

第一个人有n种选择，第二个人有n-1中选择 ，第三个人有n-2中选择，... ，直接dfs求出最小的res

复杂度O(n!)，

放在leetcode里撑死了medium难度。

感觉面试官希望你用queue + bfs方法做。

queue用来存储所有人的位置，如果找到一辆车说明找到这个人匹配的车，如果找到多辆车就放回queue，后面再处理，这样解可以使得最大距离最小，面试官好像在往这个方向引导你。

specialzsp 发表于 2018-10-9 17:41
不可以，因为有距离相同的，你这样会有抢车的情况。原帖已经说了存在距离相同的情况。

race condition我当时就大概讨论了一下。因为是两个人抢一辆车嘛，所以你就找离这两个人第二.三.四之类近的车，谁更远谁就赢。

lz面的是onsite？我觉得是不是不同面试官对candidate要求不同？我这个写出来以后还剩15-20分钟然后就直接口述followup讨论，大概述了一分钟吧，然后就尬聊了。

O(k!), 原贴写错了

这题我的做法是把所有人车距离的pair放在heap里。pop出一个就把相关的车和人mark成visited。这样应该是最优的。

bfs时间复杂度比pq大很多

kwang75 发表于 2018-10-10 06:39
这题我的做法是把所有人车距离的pair放在heap里。pop出一个就把相关的车和人mark成visited。这样应该是最优 ...

不可以，因为有距离相同的，你这样会有抢车的情况。原帖已经说了存在距离相同的情况。

其实看了一圈地里似乎这题也没有什么明确解法，用什么方法纯看面试官心情，我觉得这题就是单纯考察面试者思路的，而不是单纯做出题。比如你的面试官就在最后明确说要用匈牙利算法，但也有人面试时说用匈牙利算法被面试官叫停，面试官说没那么复杂，暴力即可。另外那个最大距离最小的最优方法似乎是你的面试官想要的方案，好像也没有什么效率比较高的方法，怎么看都是一np问题，似乎有人提到dp可以做，但是状态转移方程还是不明。

不好意思看错了lz。我面的那题没有obstacle。。。sorry

但是我觉得idea应该类似？

kwang75 发表于 2018-10-10 06:47
race condition我当时就大概讨论了一下。因为是两个人抢一辆车嘛，所以你就找离这两个人第二.三.四之类近 ...

有道理。不过我感觉后来的讨论面试官一直想让我给出新的criteria，我提了几个可能的优化全局的解法他都说不好，问能不能focus 在每一个人的optimal上……

我的想法是从每辆车出发，做BFS，每层BFS都把所有车做了。当任何一辆车找到一个人的时候，把车和人都拿掉，之后的BFS不再考虑他们。这样直到所有车和所有人都匹配到。不过我也说不好这个是什么最优，应该是一种local optimal。楼上那个把pair放进pq里的方法我觉得也不一定不行，和我说的应该给出一样的结果，两个人到车最近那一定是会出现抢车，可能就看index了？这个肯定不是全局最优了。不过这个规则的obstacle有存在的意义吗？感觉最开始的问题都可以直接算出距离来比较而不用BFS了

specialzsp 发表于 2018-10-9 17:51
有道理。不过我感觉后来的讨论面试官一直想让我给出新的criteria，我提了几个可能的优化全局的解法他都说 ...

这个我觉得你得先跟面试官clarify清楚吧？我当时上来就问，你是想让我optimize某一个人还是所有人。他说所有人。那我觉得可能还是heap+loop 2nd 3rd option这样比较make sense。但是这个followup我没写过，所以have no idea。

感觉你可能是碰到了either一个特别大神的面试官，或者一个像坑你的。