Yelp intern 电面跪经

今天下午刚面完Yelp实习，感觉已跪妥，发个面经为接下来的面试攒RP
面试官是个Engineering manager, 上来自我介绍了一下，why Yelp

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

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

问了几个问题就结束了

求RP, 希望下次技术面不要又紧张得发挥失常

1. class Solution(object):
   
2.     def merge(self, intervals):
   
3.         """
   
4.         :type intervals: List[Interval]
   
5.         :rtype: List[Interval]
   
6.         """
   
7. 
   
8.         times = []
   
9.         for s,e in intervals:
   
10.             times.append((s,0))
    
11.             times.append((e,1))
    
12. 
    
13.         times.sort()
    
14.         s = []
    
15.         res = []
    
16.         for t in times:
    
17.             if t[1]==0:
    
18.                 s.append(t)
    
19.             else:
    
20.                 tmp = s.pop()
    
21.                 if not s:
    
22.                     res.append([tmp[0], t[0]])
    
23.         return res
    
24.             
    
25. 
    
26. #[1,6],[8,10],[15,18]
    
27. intervals = [[1,3],[2,6],[8,10],[15,18]]
    
28. so = Solution()
    
29. a = so.merge(intervals)
    
30. print(a)

复制代码

楼主后来多久收到消息

jimmyshie123 发表于 2016-11-2 21:34
楼主后来多久收到消息

一星期后收到的，跪了

若就是merge intervals本身的话，sort再检查overlap: time complexity O(N)

1. vector<pair<int, int>> mergeIntervals(vector<pair<int, int>>& intervals) {
   
2.   // sort given intervals by starting point
   
3.   sort(intervals.begin(), intervals.end(), [](pair<int, int> a, pair<int, int> b) {
   
4.     return a.first < b.first;
   
5.   });
   
6. 
   
7.   vector<pair<int, int>> res;
   
8.   for (auto& i : intervals) {
   
9.     // current interval has no overlap with previous ones
   
10.     if (res.empty() || res.back().second < i.first) res.push_back(i);
    
11.     // have overlap, but not completely covered by previous ones
    
12.     else if (res.back().second < i.second) res.back().second = i.second;
    
13.   }
    
14.   return res;
    
15. }
    

复制代码

asdfg0042 发表于 2016-11-3 01:55
一星期后收到的，跪了

噢，好 ＃＃＃＃＃