行人自行车匹配

linyu203 发表于 2019/03/30 09:41:13
有没有要求所有人的总距离最小？

follow up有

为了这题特地去学了KM和匈牙利
心很累...

不过面试的时候大概就只出张嘴了
被问了follow-up 1的话我会说

> 这题我可以提供3种方法来解, 分别是Linear programming, Minimum cost maximum s-t flow, KM

然后开始讲怎么reduce成这些问题, 像是

1. Linear programming
> 考虑一矩阵, column index代表人, row index代表车, 可写出
> $Maximize: -\sum^N_i c_{ij} x_{ij}$
> $Persons: \sum^{bikes}_j x_{ij} = 1 \forall i$
> $Bikes: \sum^{persons}_i x_{ij} \leq 1 \forall j$
> $All: x_{ij} \geq 0 \forall i, j$
> 然后用simplex algorithm应该就可解出

2. Minimum cost maximum s-t flow
> 给一对source和target节点
> source都有capacity为1的edge连到persons
> target都有capacity为1的edge连到bikes
> persons都有capacity为1的edge连到bikes, 且cost为其两者距离
> 讲完就赶快换话题讲KM了, 其实我只学过maximum s-t flow没学过这个...

3. KM
> 这就不用解释了, 随便鬼扯说这是专门解这个问题的方法所以时间复杂度会比较优就好了

前面原题做完, 这3个讲慢一点, 然后时间就差不多了就不用写代码了...

不过避免遇到原题就直接问了follow-up的情况我还是把代码全都写过了
test cases的graphs就直接从google doc里的范例取了
基本是看着这篇文章的Java刻出来的Python版本
求更compact更Pythonic的写法和其他test cases

Follow-up 2面试时可以写写看不算太难

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

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

补充内容 (2019-4-1 23:45):
这边的KM是最简单的DFS:O(N^4)的形式
N是人数
BFS似乎可O(N^3)
但太复杂果断放弃

linear programming的时间复杂度我就没概念了
minimum cost flow似乎有很多版本
有人有概念的吗
另外也好奇这两种算法的Python实现

补充内容 (2019-4-1 23:57):
另外貌似KM似乎有很简单的实现方式的样子
https://blog.csdn.net/u014754127/article/details/78086014
有空再来看看

分享一个新的面对follow-up时的出路
写一个pythonic的暴力解
至少可以展现对一个语言的熟悉度
让你从no-hire变成leaning-no-hire...

只要把sum与max互换, 一秒完成另一个follow-up

test cases同上篇回文, 只是input座标从list改用tuple

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

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

终于因情势所逼让我试着把匈牙利看懂了皮毛，不过二分法+匈牙利找最短距离是时间复杂度怎么算？O(PB^2 Log(K)) where K=max(dist)-min(dist)?

这题我去年准备谷歌的时候就是高频 现在还是高频 看来谷歌的题也没有传说中新题出得那么快啊

kaipeng21 发表于 2019-4-8 03:53
终于因情势所逼让我试着把匈牙利看懂了皮毛，不过二分法+匈牙利找最短距离是时间复杂度怎么算？O(PB^2 Log( ...

感觉是O(P^3 log K)的样子?

外层loop呼叫DFS共O(P)
DFS里面虽然循环B
但只要找到没match的bike就停止
已match的bikes最多P台, 所以循环O(P)
DFS深度是match的数量, 所以也是O(P)

补充内容 (2019-4-9 03:21):
忘了考虑没有perfect match的状况了
所以DFS中的主循环B还是可能的
那应该是O(P^2 B log K)?