新鲜电面面经
Find longest poolChain
input: List<Log>
output: 最长的poolchain
log结构:
Long timestamp
int driver_id
int passenger_id
String pickup / dropoff
poolchain的定义：
直接或者间接的有overalp的行程（乘客）数目
先报这么多吧。。勉强写完跑完testcase，面试官感觉全程冷漠，希望能收到昂赛，如果拿到了 再来写更详细的吧。
写了一个版本如下，不知道理解的对不对: longest pool chain 就是最长能够串起来的旅程数量？
class Log:
def __init__(self, ts, di, pi, pd):
self.timestamp = ts
self.driverId = di
self.passengerId = pi
self.pickupOrDropoff = pd
class Trip:
def __init__(self, sl, el):
self.startLog = sl
self.endLog = el
class Solution:
def isOverlap(self, t1, t2):
if t1.startLog.timestamp > t2.endLog.timestamp or \
t2.startLog.timestamp > t1.endLog.timestamp:
return False
else:
return True
def findLongestPoolchain(self, logs):
from collections import defaultdict
trips = []
startTab = defaultdict(Log)
for log in logs:
if log.pickupOrDropoff == "P":
startTab[log.driverId] = log
elif log.pickupOrDropoff == "D":
trip = Trip(startTab[log.driverId], log)
trips.append(trip)
del startTab[log.driverId]
trips.sort(key = lambda x: x.startLog.timestamp)
longestChain = 0
i = 0
j = 1
n = len(trips)
while i < n and j < n:
overlap = trips[i]
while j < n and self.isOverlap(overlap, trips[j]):
overlap.endLog.timestamp = max(overlap.endLog.timestamp, trips[j].endLog.timestamp)
j += 1
if j - i > longestChain:
longestChain = j - i
i = j
j += 1
return longestChain
### Test:
logs = [Log(101, 1, 1, "P"), Log(102, 1, 1, "D"), Log(105, 3, 3, "P"),
Log(107, 2, 2, "P"), Log(109, 2, 2, "D"), Log(111, 3, 3, "D"),
Log(115, 1, 1, "P"), Log(120, 1, 1, "D")]
print(Solution().findLongestPoolchain(logs))
2
给你俩test case哈
dr1 -> p1 p2 d2 d1 p3 d3 –> chain: 2, 1
dr2 -> p1 p2 d2 p3 d1 d3 p4 d4 –> chain: 3, 1
output: 3
他家电面就这么难吗？还是楼主面的level比较高？
Anyway，以下是我的理解，说得不对还望指正！
我可以理解成每个driver有自己的timeline，我们可以分开处理。
1.对于每个driver而言，有一系列的trip，我们可以看作interval
2.然后我们对其按照starttime排序。求出overlap最多的trip个数。
3.最后对所以driver的max chain再得出一个全局的longest pool chain
感觉比较适合用map-reduce来实现，map负责按照driver id进行分配， reducer负责对同一个driver参与的trip进行interval 处理
以上也只是思路，电面的时间要理解题意，阐述思路，实现代码感觉真的好难。。。 >_<
你的理解是对的，唯一就是 p1 p2 d2 p3 d1 d3 这种虽然passenger 2 和3没有同时在车上，但是因为passenger 1 会有间接的overlap 所以这种情况下chain length =3. 不是我的level的问题，我是转专业的phd，投的一般的职位。 只是遇到的人，电面不能面对面，确实弄懂题意花了好一会儿。
这个题可以先把log 按照 driver_id + timestamp sort 一下
然后有个hashmap《driverId, Set》
有个hashmap<driverId, UserNumber>
然后按照顺序把 passenger 加到 set 里面，游客，本帖隐藏的内容需要积分高于 10 才可浏览，您当前积分为 0。 查看如何攒积分 Click here for more info.gt; [2] -> [3] -> [3] ->[0]
这样就可以记录最大的数量
更新： 收到游客，本帖隐藏的内容需要积分高于 10 才可浏览，您当前积分为 0。 查看如何攒积分 Click here for more info.邀请啦
ok的 我面试的时候也是按照driver id 存hashmap 再排序，然后不用set，直接用个counter就行了，来一个乘客，counter++,下一个，counter-- ; 这期间记录一下总共上了几个乘客，当counter =0的时候，update一下最大的乘客数
对 counter 是可以的哎 但是会不会有这种情况 p1 p2 d1 d3,这种情况3还没上车，但是drop了它
这属于非法输入了。。。只要跟面试官确认 输入都合法就行了