谷歌onsite西雅图

reboot329 发表于 2019/12/13 12:57:01
请问楼主当时recruiter怎么和你说的呢？ 我马上就要面了(L4), recruiter说的很绝对是4轮算法一轮bq...

我也是4轮算法一个BQ。。懵逼

L3的都这么难了？？？请问是哪个office啊kirkland，fremont还是slu的？

肖途 发表于 2019-12-17 16:37
L3的都这么难了？？？请问是哪个office啊kirkland，fremont还是slu的？

kirkland

第二题感觉应该是用union find中的parent的路径压缩

第二题可以用lazy delete做到摊销常数级

1. import collectionsclass A:
   
2.     def __init__(self):
   
3.         self.dq = collections.deque()
   
4.         self.ack = set()
   
5.         self.max = None
   
6. 
   
7.     def start(self, n):
   
8.         self.max = n + 1
   
9.         self.add()
   
10. 
    
11.     def add(self):
    
12.         for i in range(self.max, self.max + 10):
    
13.             self.dq.append(i)
    
14.         self.max += 10
    
15. 
    
16.     def ackk(self, n):
    
17.         if self.dq[0] < n:
    
18.             self.ack.add(n)
    
19.             if n >= self.max:
    
20.                 self.add()
    
21. 
    
22.         else:
    
23.             self.ack.add(n)
    
24.             while self.dq and self.dq[0] in self.ack:
    
25.                 self.ack.discard(self.dq.popleft())
    
26. 
    
27.             if not self.dq:
    
28.                 self.add()
    
29. 
    
30.         return self.dq[0]
    
31. 
    
32.     def lun(self):
    
33.         return self.dq[0]
    
34. 
    
35. a = A()
    
36. a.start(5)
    
37. print(a.lun())
    
38. print(a.ackk(8))
    
39. print(a.ackk(7))
    
40. print(a.ackk(6))
    
41. 
    
42. 
    
43. 
    

复制代码

刚才的发错了 应该是这个

1. import collections
   
2. class A:
   
3.     def __init__(self):
   
4.         self.dq = collections.deque()
   
5.         self.ack = set()
   
6.         self.max = None
   
7. 
   
8.     def start(self, n):
   
9.         self.max = n + 1
   
10.         self.add()
    
11. 
    
12.     def add(self):
    
13.         for i in range(self.max, self.max + 10):
    
14.             self.dq.append(i)
    
15.         self.max += 10
    
16. 
    
17.     def ackk(self, n):
    
18.         if self.dq[0] < n:
    
19.             self.ack.add(n)
    
20.             if n >= self.max:
    
21.                 self.add()
    
22. 
    
23.         else:
    
24.             self.ack.add(n)
    
25.             while self.dq and self.dq[0] in self.ack:
    
26.                 self.ack.discard(self.dq.popleft())
    
27. 
    
28.             if not self.dq:
    
29.                 self.add()
    
30. 
    
31.         return self.dq[0]
    
32. 
    
33.     def lun(self):
    
34.         return self.dq[0]
    
35. 
    
36. a = A()
    
37. a.start(5)
    
38. print(a.lun())
    
39. print(a.ackk(8))
    
40. print(a.ackk(7))
    
41. print(a.ackk(6))
    
42. 
    

复制代码

李秋实Qiushi 发表于 2020-1-13 06:21
第二题可以用lazy delete做到摊销常数级

[mw_shl_code=python,true]import collectionsclass A:

写错了 请把heap改成deque

第二题, 的确path compression的idea来做，把点都变成间隔，插入新的数时则间隔合并，找unacknowledged时只要第一间隔后面的数就是了

第一轮hashtable 明显不对啊