新鲜Uber电面

给两个数组
[1, 3, 5, 9  ]
[1, 3, 7, 11]
计算他们的similarity = intersection / union
此题

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

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

ng>补充内容 (2019-2-2 03:23):
求点大米 谢谢

求问第二个follow up 应该怎么优化呢？

russzheng 发表于 2019-2-2 07:55
求问第二个follow up 应该怎么优化呢？

我也不知道
我答了很多种可能
从Bitmap, 到sparse matrix, 到Binary Search, 到针对数组的range分类, 最后答的是

因为大部分都是0 说明很有可能对于比如 array
[1, 3, 5, 7 ... ]
数字1来说, 大部分别的array都不包含1. 因此 我们可以把所有的Array 分成2类 包含1的和不包含1的, 这样包含1的应该是个很小的集合, 比如只占总数的1%, 然后这些array之间的similarity肯定不是0了, 就一一计算.
然后在处理数字3, 5, 7, 直到处理完所有的出现在array中的数字.
过程中把所有的已经处理过的pair记录标记下来, 例如用hashmap, 以免重复处理.

面试官也没说对错 时间到了.

csehao 发表于 2019-2-2 08:00
我也不知道
我答了很多种可能
从Bitmap, 到sparse matrix, 到Binary Search, 到针对数组的range分类,  ...

我还在想，如果所有的array都是sorted，那在算jaccard similarity之前可以先判断 b[0] > a[a.length - 1] || b[b.length - 1] < a[0] 因为这样子就肯定不会有重合。这样子就相当于大多数pair都只是constant time，但是因为要算所有的pairs 所以时间复杂度的average case最小也是o(n^2)。但如果绝大多数都是0，那可以对range分类 排序 然后时间复杂度的average case应该接近o(n)？

russzheng 发表于 2019-2-2 08:18
我还在想，如果所有的array都是sorted，那在算jaccard similarity之前可以先判断 b[0] > a[a.length - 1] ...

这个我跟面官提到了 他说假设range非常大 而且大部分都有重合 所以这个应该不是他想要的 就move on了.

请问一下楼主前两问是这么想的吗：

第一问 ：two pointers or binary search
follow up: while 循环跳过重复就行了

follow up 2: 我觉得楼主说的根据起始元素来看的方法挺好的
我第一个想法有点类似 我想到union find去了 就是把similarity不为0的元素group一起 group在一起的array找similarity 如果不是一个group肯定为0

Venus 发表于 2019-2-9 06:07
请问一下楼主前两问是这么想的吗：

第一问 ：two pointers or binary search

第一问就是two pointer就可以了

有没有可能把数组sort一下，然后只有临近的 similarity可能是1？但感觉复杂度也挺高的

数百万个数组，感觉是倒排索引？假设m个数组，要比m^2次。倒排索引之后，只有是公共元素的才需要考虑，例子里面
[1, 3, 5, 9  ]
[1, 3, 7, 11]
=》
1 : [A, B]
3: [A, B]
5 : [A]
...

只需要考虑很少的像1和3这样的元素。