Uber电面

ysq0807 · 2017-10-23 13:09:22

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

x

拼车系统，日志里记录司机的id和每个trip

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

量最多）和所属的司机

cake923

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

ysq0807

cake923 发表于 2017-11-3 13:20
楼主可以再解释下这道题吗？明天uber面试好捉急。它说的这个chain是指的是某个司机接人， drop off乘客时间 ...

是的你的理解是正确的

LUOLUOLNSH · 2017-10-23 20:16:45

多谢lz分享请问这个日志里每条记录是按start时间排序的吗？

ysq0807 · 2017-10-24 13:10:17

good question, interview的回答是不是的

cicean · 2017-10-24 14:52:57

啥叫组成一个chain 是直接存有重合的所有司机 id 么？

ysq0807 · 2017-10-25 02:12:03

一个司机可能会pick up乘客A，pick up乘客B，drop off乘客A，pick up C， drop C， drop B，这是一个长度为3的chain

学霸也刷题 · 2017-10-25 02:15:16

感谢分享！
所以这题是类似于meeting room吗？

547690781 · 2017-10-25 02:30:46

这题greedy就好了。

ysq0807 · 2017-10-25 02:36:22

我的做法是类似merge intervals，不知道有没有更好的做法

yikehongxin · 2017-10-25 02:41:06

请问楼主，日志只包含一个司机的ID么？

ysq0807 · 2017-10-25 02:54:02

包含很多司机id，需要找出最长chain的司机和chain的长度，我的做法是每一个司机做merge interval