📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 5640| 回复: 15
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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



评分

参与人数 14大米 +218 收起 理由
flyMontain + 2 给你点个赞!
mhbkb + 2 给你点个赞!
zjccpmh + 2 给你点个赞!
magmag + 1 很有用的信息!
kaipeng21 + 2 很有用的信息!

查看全部评分


上一篇:只用C++,java刷题可以吗
下一篇:[讨论讨论,加米加米] Leetcode 621 Task Scheduler 任务行程表
推荐
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
回复

使用道具 举报

推荐
Warald 2019-3-28 03:22:30 | 只看该作者
全局:
本文作者已经获得管理员和版主的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:32 | 只看该作者
全局:
这是哪家的高频啊?
回复

使用道具 举报

🔗
14417335 2019-3-29 07:58:05 | 只看该作者
全局:
perking999 发表于 2019-3-29 07:26
这是哪家的高频啊?

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

使用道具 举报

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

评分

参与人数 2大米 +6 收起 理由
14417335 + 3 很有用的信息!
umialpha + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
 楼主| umialpha 2019-3-29 11:57:07 | 只看该作者
全局:
manyfun711 发表于 2019-3-29 11:17
去年面过这个题,用了一个非常下下策的方法。把人车用一维id进行编号,这样有两个结构体数组,然后把所有的 ...

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

使用道具 举报

🔗
garyyang 2019-3-29 22:43:38 | 只看该作者
全局:
需要如此熟练掌握这么些算法的组和职位,每天工作可能只是算法,一定枯燥得不行吧。
回复

使用道具 举报

🔗
_song 2019-3-29 23:59:33 | 只看该作者
全局:
感谢分享感谢分享
回复

使用道具 举报

🔗
bazingaa 2019-3-30 00:34:53 | 只看该作者
全局:
感谢分享 找个java版本
回复

使用道具 举报

全局:
有没有要求所有人的总距离最小?
回复

使用道具 举报

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

本版积分规则

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