行人自行车匹配

狗家最近超高频题

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

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

为了这题特地去学了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

本文作者已经获得管理员和版主的200分奖励！

关于双倍积分奖励算法题和系统设计题讨论的决定：

我们：
1. 希望能看到干货讨论；
2. 希望能看到好的代码（web端高级发帖模式下，@ 朋友右边的<> 可以选择多种代码）

版主 @14417335 负责审核加分，也请大家给好的回复加分 + 顶。
大家给30，我会跟进奖励30，double之；
大家给100，我也会跟进奖励100，double之。

很理解大家写代码、调试、写思路分析，很花时间。对于特别好的回复，还会有额外加分。

欢迎大家拿出好的题目讨论，选中了我会全站置顶。哪位同学起了好的题目/帖子，激发了干货讨论，也会获得一定的积分奖励。

欢迎大家踊跃参与。看到好的回复，也请大家顶一下，作为对别人积极参与讨论、热心分享的认可和鼓励。

其他可以获得双倍积分的题目：

在刷题版里选择高频题标签，链接:
https://www.1point3acres.com/bbs/forum.php?mod=forumdisplay&fid=84&filter=typeid&typeid=1019

大家看到LC没有的高频题，也请贴到刷题版里，又有大米又有赞。对于学弟学妹们也是功劳一件。举手之劳。谢谢大家的参与。

这是哪家的高频啊？

perking999 发表于 2019-3-29 07:26
这是哪家的高频啊？

楼顶第一行小字：狗家
高频应该已经一年了
而且是超高频。

去年面过这个题，用了一个非常下下策的方法。把人车用一维id进行编号，这样有两个结构体数组，然后把所有的车和人进行pairing，能得到一个每个pair的距离，将这些pair按照距离进行排序，只mark车和人同时未出现过的pair，直到找到target。这样做可以用priority_queue进行优化，不需要对整体进行排序，可以提高一些时间复杂度。当时感觉这题答的很不好，但是也过hc了。供大家参考。

manyfun711 发表于 2019-3-29 11:17
去年面过这个题，用了一个非常下下策的方法。把人车用一维id进行编号，这样有两个结构体数组，然后把所有的 ...

你这个方法是原题的最优解吧。但是没法用在follow up上，当时面试官问的是什么follow up 啊？

需要如此熟练掌握这么些算法的组和职位，每天工作可能只是算法，一定枯燥得不行吧。

感谢分享感谢分享

感谢分享 找个java版本

有没有要求所有人的总距离最小？