📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: umialpha
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 行人自行车匹配

🔗
 楼主| umialpha 2019-3-30 11:02:58 来自APP | 只看该作者
全局:
linyu203 发表于 2019/03/30 09:41:13
有没有要求所有人的总距离最小?

follow up有
回复

使用道具 举报

🔗
Lunluen 2019-4-1 21:09:26 | 只看该作者
全局:
为了这题特地去学了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即刻解锁阅读权限 或 查看其他获取积分的方式
Popular 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
有空再来看看

评分

参与人数 3大米 +16 收起 理由
hyklxf + 3 感谢分享!
14417335 + 10 给你点个赞!
umialpha + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
Lunluen 2019-4-6 07:49:32 | 只看该作者
全局:
分享一个新的面对follow-up时的出路
写一个pythonic的暴力解
至少可以展现对一个语言的熟悉度
让你从no-hire变成leaning-no-hire...

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

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

您好!
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 130 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies
回复

使用道具 举报

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

使用道具 举报

🔗
cs2009 2019-4-8 05:40:28 | 只看该作者
全局:
这题我去年准备谷歌的时候就是高频 现在还是高频 看来谷歌的题也没有传说中新题出得那么快啊
回复

使用道具 举报

🔗
Lunluen 2019-4-9 02:45:17 | 只看该作者
全局:
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)?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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