Uber OA

4道OA题70分钟
1) 给你两个array 找出其中开始和最后character match的返回
比较a[0] == b[0] && a[a.length - 1] == b[b.length - 1]
2）非常简

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

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

X：
[‘0’,‘0’,‘0’,‘0’,‘0’]    LLC3   -》[‘1’,‘1’,‘0’,‘1’,‘0’]
用正常的array update来做会超时

这个第四题其实就是等效成，实现一个interface，支持两个操作，add number，还有find first number not added, 是个挺常见的题。两个接口能都实现o(1), 直观一点可以是unionfind， 相当于每次添加就是union周围的两个数。 简单一点，就用hashmap，记录没个range的边界，每次加数的时候更新边界。这个题google总考，看见过几次。

说实话我只看懂了第四题
第四题用set+pq来做如何？
时间复杂度NlogN

emmm 应该如此

补充内容 (2020-10-22 08:23):
pq是指 heap

ND0406 发表于 2020-10-21 17:22:17
说实话我只看懂了第四题
第四题用set+pq来做如何？
时间复杂度NlogN

关键是L 需要查第一个0的位置应该是(1)一个O(n)的操作我超时fail了一半test cases。我感觉可以用位运算做可以变成o

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

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

jianghaon0 发表于 2020-10-21 17:36:56
关键是L 需要查第一个0的位置应该是(1)一个O(n)的操作我超时fail了一半test cases。我感觉可以用位运算做可以变成o

你这个是 每个L操作都On时间
我的L操作是logN时间

4. 把值为0的位置下标存成LinkedHashSet？这样就是removeHead或者remove

第4题是不是可以用TreeSet做，查第一个0和把任意位置改成1都是O(log n)时间

世纬夫特 发表于 2020-11-19 06:41
第4题是不是可以用TreeSet做，查第一个0和把任意位置改成1都是O(log n)时间

我也觉得TreeSet好， 可以LogN拿最小值和delete

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

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