Uber电面

Linkedin的recruiter主动联系，两周前电面，面的是seattle的office 已挂
问题是找similartiy of 2 int arrays
similartiy de

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

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

后来想到其实O(1) space 就可以解决
但是代码没写完，题不难，但是第一次面试不会搞codepair， 与U家无缘

这题时间O(n)，空间O(1)的解法是什么？

在楼主这里贡献一个U家电面面经，weighted random sampling… 之前就看过这个题目，感觉最近出的频率有点大啊，大家好好准备吧

fancz2002 发表于 2018-9-28 23:32
这题时间O(n)，空间O(1)的解法是什么？

我觉得2 pointers可以解决

zws0818 发表于 2018-9-29 17:05
我觉得2 pointers可以解决

那得sort吧, 所以时间就多了一点

zws0818 发表于 2018-9-29 17:05
我觉得2 pointers可以解决

不sort怎么双指针？能详细说说吗？

mengyi2008 发表于 2018-9-28 12:30
在楼主这里贡献一个U家电面面经，weighted random sampling… 之前就看过这个题目，感觉最近出的频率有点大 ...

具体讲下？

fancz2002 发表于 2018-9-30 05:44
不sort怎么双指针？能详细说说吗？

感觉这道题和lc伞撕酒很像，两个方法，一个是用set,另外一个就是先排序再扫~

koga 发表于 2018-10-3 06:52
具体讲下？

https://medium.com/@peterkellyon ... ection-3ff222917eb6

看看这个吧，基本就是这个意思，基于权重返回一个random value

看到O(1)自动往bit-map方向想的是不是没救了
不过这题如果改成字母就可以用了