Airbnb onsite 跪经

本人粗鄙的想法。

1. 
   
2. def optimize_requests(requests: list):
   
3.         if not requests:
   
4.                 return 0, []
   
5. 
   
6.         requests = sorted(requests, key=lambda x: (x[0], -x[1]))
   
7.         print(requests)
   
8. 
   
9.         # end time for current plan, -total_profit current plan, path
   
10.         pq = [(requests[0][1], requests[0][0] - requests[0][1], [requests[0]])]
    
11. 
    
12.         for idx, item in enumerate(requests[1:], 1):
    
13.                 if requests[idx][0] == requests[idx - 1][0] and requests[idx][1] <= requests[idx - 1][1]:
    
14.                         continue
    
15. 
    
16.                 start, end = item
    
17.                 profit, path = 0, []
    
18.                 if pq[0][0] <= start:
    
19.                         _, profit_old, path_old = pq[0]
    
20.                         profit, path = profit_old, path_old
    
21.                         heapq.heappop(pq)
    
22. 
    
23.                 profit += -(end - start)
    
24.                 path.append((start, end))
    
25.                 heapq.heappush(pq, (end, profit, path))
    
26. 
    
27.         for plan in pq:
    
28.                 print(plan)
    
29. 
    
30.         print("Final answer:\n")
    
31.         _, profit, path = min(pq, key=lambda x: x[1])
    
32.         print(-profit, path)
    
33. 
    
34. 
    
35. inputs = [(1, 3), (2, 5), (10, 17), (8, 11), (16, 21), (10, 11), (16, 17), (23, 26), (25, 30)]
    
36. optimize_requests(inputs)
    
37. 
    

复制代码

本人粗鄙的想法。其实是meeting room的变种，用PQ记/选出来所有可能的安排计划，然后遍历一遍找到最大的的安排

第五题难道不是sort一下，过一遍就行了嘛，比较一下conflict的interval t2-t1的和与较大的那个interval，取大的那个? 你们说的我怎么都看不懂。

可以请问一下楼主system design那一轮具体的题目吗？

lijing2441 发表于 2019-2-19 12:51
可以请问一下楼主system design那一轮具体的题目吗？

不好意思，时间有点久远，细节记不清了，不过就是设计各种表格去存user和listing，然后对应的搜索。

看看 谢谢分享

第五题应该用dp来解吧.
例如lz的例子,按照lz的代码跑出来的结果是 15 [(1, 3), (8, 11), (16, 21), (25, 30)]
但是实际上应该是  16 [25,30] [16,21] [8,11] [2,5]

同认为是dp，第一个区间应该是[2,5]

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

dfs

1. class solution:
   
2.     def dfs(self, start_pos, profit, prev_end):
   
3.         #find next eligible request
   
4.         while start_pos < len(self.requests) and prev_end > self.requests[start_pos][0]:
   
5.             start_pos += 1
   
6. 
   
7.         #if no eligible session left can be added: track the profits
   
8.         if start_pos >= len(self.requests):
   
9.             if profit > self.max_profit:
   
10.                 self.ans = self.cur[:]
    
11.                 self.max_profit = profit
    
12.         else:
    
13.             #select this interval
    
14.             new_profit = profit + self.requests[start_pos][1] - self.requests[start_pos][0]
    
15.             self.cur.append(self.requests[start_pos])
    
16.             self.dfs(start_pos+1, new_profit, self.requests[start_pos][1])
    
17.             self.cur.pop()
    
18. 
    
19.             #not select this interval
    
20.             self.dfs(start_pos+1, profit, prev_end)
    
21. 
    
22. 
    
23.     def optimize_requests(self, requests: list):
    
24.         self.requests = sorted(requests)
    
25.         #for each request, we have options to have it or not have it
    
26.         self.ans = []
    
27.         self.cur = []
    
28.         self.max_profit = 0
    
29.         self.dfs(0, 0, 0)
    
30.         print("max profit is {}".format(self.max_profit))
    
31.         return self.ans

复制代码