Google 10/21 一轮电面

刚电面完Google，没听清哪里人，直接上题:
Given a list of events containing start time, end time and ID, find a list of conflicted events

第一次techinical电面，倒没有那么紧张。题目不难，过程还算顺利，少考虑了2个case，写的过程中我还co

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

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

呀？

最后祝大家即将面试的同学Goooooood Luck！

(PS: 有去Zappos实习过的同学嚒，想问下进了finalist有多大几率拿offer啊，谢谢！！！)

请教一下lz少考虑的2个case分别是什么？

感觉最近哪家面试都好爱问这种intervals的问题啊，这题和leetcode的meeting rooms II 很像，那题是返回冲突的最大个数，这题是返回所有冲突的id。贴一下自己的代码以供参考。

1. class Event:
   
2.         def __init__(self, id, start, end):
   
3.                 self.id = id
   
4.                 self.start = start
   
5.                 self.end = end
   
6. 
   
7. def conflictedEvents(A):
   
8.         res = []
   
9. 
   
10.         heap = []
    
11.         heapq.heapify(heap)
    
12. 
    
13.         for event in A:
    
14.                 heapq.heappush(heap, (event.start, event.id, 1))    // start
    
15.                 heapq.heappush(heap, (event.end, event.id, -1))    // end
    
16. 
    
17.         count = 0
    
18.         curEvent = None
    
19.         isConflicted = False
    
20. 
    
21.         while heap:
    
22.                 time, eid, value = heapq.heappop(heap)
    
23. 
    
24.                 if value == 1:
    
25.                         if count == 0:
    
26.                                 curEvent = eid
    
27.                                 isConflicted = False
    
28.                         elif count == 1:
    
29.                                 if isConflicted == False:
    
30.                                         res.append(curEvent)
    
31.                                         isConflicted = True   // append curEvent to the result list only once.
    
32.                                 res.append(eid)
    
33.                         else:
    
34.                                 res.append(eid)
    
35.                 else:
    
36.                         if count == 0:
    
37.                                 curEvent = None
    
38.                 count += value
    
39. 
    
40.         return res

复制代码

比如Event(id, start, end)类型：[(1,0,15),(2,10,15),(3,15,20)] 返回的id是[1,2]

孤笑客 发表于 2015-10-22 09:07
请教一下lz少考虑的2个case分别是什么？

我用的一个comparing event，两个miss了的case 一个是conflict的时候是否应该update comparing event，还有一个是没有conflict的时候是否应该update comparing event.

比如[0,5][2,3][3,4], 前两个有conflict，但不需要update event到[2,3]因为5>3

可能有些不清楚，基本就是if需不需要else了

tangvictor 发表于 2015-10-22 09:17
感觉最近哪家面试都好爱问这种intervals的问题啊，这题和leetcode的meeting rooms II 很像，那题是返回冲突 ...

惭愧leetcode都没完整看过一遍，heap的思路我那时候没想到，最后问interviewer他也没说什么别的解法哈哈

tinir 发表于 2015-10-22 01:05
惭愧leetcode都没完整看过一遍，heap的思路我那时候没想到，最后问interviewer他也没说什么别的解法哈哈

其实heap和sort都一样，如果是sort就sort start一个list，sort end一个list，按先后时间顺序start就加1，end就减1。。

祝楼主好运，明天应该就有结果了。。我19号面的，也只面了一题后来一直followup问题，昨天通知要加面。。

tangvictor 发表于 2015-10-22 21:37
其实heap和sort都一样，如果是sort就sort start一个list，sort end一个list，按先后时间顺序start就加1， ...

3Q! 借你吉言啦!

Update: mountain view onsite invitation revived just now
Super excited!!