Uber 2018 新鲜电面

上周领英上SE manager找到我，电话聊了一下，移交recruiter。uber的recruiter很奇怪，早早就要求填身份相关信息，国籍，visa status等。不过还好给了电面，不然还在想是不是暗中过滤掉没身份的。

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

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

补充内容 (2018-11-18 02:20):
抱歉有个条件忘记说了，数组已经是sorted的，所以我用2 pointer比较找的重合

补充内容 (2018-11-24 02:23):
居然拿到了昂赛，感人！求大米啊！各位题友们求大米！没米寸步难行啊！谢谢大家！

复杂度 sum(size(array_i)) i from 0 to n, 用map+set 每个数扫一遍

2 pointers 只能做两个数组，多个数组还需要结合divide-n-conquer, 是吧？

edu 发表于 2018-11-23 05:45
2 pointers 只能做两个数组，多个数组还需要结合divide-n-conquer, 是吧？

我是用2 pointer先得到一个答案，用2 pointer做答案和下一个数组，以此循环做完全部数组

所有数组重合的element。 这一题感觉不难啊。Leet的哪一题？

感觉应该有两个方法吧
1. 用一个hashset，把所有数加进去，然后找加不进去的，空间复杂度很高
2.另一个用priorityqueue 然后把第一每个list的第一个element加进去，然后和peek 出来的element 比较，然后如果相等的话，就取出来

把所有数字加进map的空间复杂读是O(n)，n为所有元素的个数。

可以用O(k)空间和O(n)时间完成，k为数组个数(k <= n)。
1. 用一个数组存放k个指针分别指向当前扫描的数组的index。
2.先看第0个数组指向哪个数字(p_0 = 0)，然后移动后k-1个数组的指针直到指向相同或更大的数字。如果所有数组都指向相同的数字，那么这个数字所有数组都有。
3.重复步骤2，直到遍历完第一个数组。
注：不用担心为找第0个数组相等的数在后面数组跳过的数，也不用担心后面的数组没遍历完。因为那些数字第0个数组没有，所以必然不是所有数组都包含的数字。

1. def commonElement(lists):
   
2.     if len(lists) == 0:
   
3.         return []
   
4.     res, indices = [], [0] * len(lists)
   
5.     for p, n in enumerate(lists[0]):
   
6.         allFound = True
   
7.         for lid in range(1, len(lists)):  # iterate over remaining lists
   
8.             while indices[lid] < len(lists[lid]) and lists[lid][indices[lid]] < n:
   
9.                 indices[lid] += 1
   
10.             if indices[lid] == len(lists[lid]) or lists[lid][indices[lid]] > n:
    
11.                 allFound = False
    
12.                 break  # one list does not contain n
    
13.         if allFound:
    
14.             res.append(n)  # all lists contain n
    
15.     return res

复制代码

johnkonet 发表于 2019-1-18 10:15
把所有数字加进map的空间复杂读是O(n)，n为所有元素的个数。

可以用O(k)空间和O(n)时间完成，k为数组个 ...

This is awesome!