Google VO + timeline

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

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

Timeline:
10月初recruiter电话直撩
跳过店面约好11/15 onsite
12/02电话通知过HC
12/16 team match完


求大米

zhang123587 发表于 2021-12-19 17:25
比较 interval 的时候，可以先按 startTime 排序，找到距离 interval 最近的不相交的 interval[j] ，然后 ...

1. 
   
2. '''
   
3. assume intervals must contain at least one element
   
4. '''
   
5. 
   
6. from typing import List
   
7. import bisect
   
8. class shortestTwoSubarray:
   
9.     # if no negative, find all intervals sum to k in O(n)
   
10.     # both end of intervals will be inclusive
    
11.     # the returned intervals list should be in a sorted order (sorted by start)
    
12.     def all_intervals_sum_k(self, xs: List[int], k: int) -> List[List[int]]:
    
13.         start, acc, res = 0, 0, []
    
14.         for i, x in enumerate(xs):
    
15.             acc += x
    
16.             while start <= i and acc >= k:
    
17.                 if acc == k and start < i:
    
18.                     res.append([start, i])
    
19.                 acc -= xs[start]
    
20.                 start += 1
    
21.         return res
    
22.         
    
23.     # if negative, find all intervals sum to k in O(n^2)
    
24.     # both end of intervals will be inclusive
    
25.     # the returned intervals list should be in a sorted order (sorted by start)
    
26.     def all_intervals_sum_k_with_negative(self, xs: List[int], k: int) -> List[List[int]]:
    
27.         n, res = len(xs), []
    
28.         for start in range(n):
    
29.             acc = 0
    
30.             for end in range(start, n):
    
31.                 acc += xs[end]
    
32.                 if acc == k:
    
33.                     res.append([start, end])
    
34.         return res
    
35.    
    
36.     # from all intervals sums up to k, find the two shortest
    
37.     # O(nlog(n)), n is the number of intervals sums up to k
    
38.     def two_shortest_intervals(self, xs: List[int], k: int) -> List[List[int]]:
    
39.         intervals = self.all_intervals_sum_k(xs, k)
    
40.         if len(intervals) < 2:
    
41.             return []
    
42.         def length(interval):
    
43.             return interval[1]-interval[0]+1
    
44.         n = len(intervals)
    
45.         right_side_shortest = [float('inf')]*n
    
46.         # the shortest intervals length of subarray intervals[i:], O(n)
    
47.         right_side_shortest[-1] = length(intervals[-1])
    
48.         for i in range(n-2, -1, -1):
    
49.             right_side_shortest[i] = min(right_side_shortest[i+1], length(intervals[i]))
    
50.         print(right_side_shortest)
    
51.         # use binary search to find the right most non-overlapping index idx,
    
52.         # as well as the shortest interval length of subarray intervals[idx:]
    
53.         # O(nlog(n))
    
54.         res = float('inf')
    
55.         for i, [start, end] in enumerate(intervals):
    
56.             idx = bisect.bisect_left(intervals, [end, float('-inf')], i+1, n)
    
57.             if idx == n:
    
58.                 continue
    
59.             res = min(length(intervals[i])+right_side_shortest[idx], res)
    
60.         return res
    
61.    
    
62. s = shortestTwoSubarray()
    
63. arr = [1, 5, 7, 1, 2, 3, 5, 3, 3, 1, 1, 4]
    
64. k = 6
    
65. actual = s.two_shortest_intervals(arr, k)
    
66. assert actual==4, f"first test failed with answer == {actual}"
    
67.         
    

复制代码

是挺烦的，不知道有没有更简洁、复杂度更好的方法。好奇楼主怎么做的。

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

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

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

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

请问我刚刚定了面试的时间，可是时间表上没有每一轮是考什么，都是这样的吗？

我是做图像的，电话面试的时候，面试官和我聊了不少图像的知识。VO的时候会考专业知识吗？ 谢谢！

pengzhao0524 发表于 2021-12-16 20:04:59
请问我刚刚定了面试的时间，可是时间表上没有每一轮是考什么，都是这样的吗？

我是做图像的，电话面试的时候，面试官和我聊了不少图像的知识。VO的时候会考专业知识吗？ 谢谢！

不知道诶…我是面的码农岗位，4轮coding+1轮BQ

第4题怎么做？先扫一遍找到所有intervals with sum = k, O(n)。然后再每两个interval比较一下，看有没有overlap，找到最小element intervals，O(m^2)?

emilys 发表于 2021-12-17 14:59
第4题怎么做？先扫一遍找到所有intervals with sum = k, O(n)。然后再每两个interval比较一下，看有没有ove ...

有点点像410，但不是

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

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

emilys 发表于 2021-12-17 16:59
第4题怎么做？先扫一遍找到所有intervals with sum = k, O(n)。然后再每两个interval比较一下，看有没有ove ...

有负数的话怎么O(n)求所有intervals啊…

匿名者 发表于 2021-12-19 17:34
是挺烦的，不知道有没有更简洁、复杂度更好的方法。好奇楼主怎么做的。

第四题其实是subarray吧？不是interval

emilys 发表于 2021-12-17 17:59
第4题怎么做？先扫一遍找到所有intervals with sum = k, O(n)。然后再每两个interval比较一下，看有没有ove ...

我也是这么做的