uber电面 新鲜面经

新鲜电面面经

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了它

这属于非法输入了。。。只要跟面试官确认 输入都合法就行了