FB 10.25 onsite + 10.5 on campus

spwahaha 发表于 2016-10-29 07:40
map.get(num-1)得到的不就是len嘛， 用一个max变量一直更新max就行了吧，没太看懂为什么要这个dp数组

明白了，之前想的复杂了，谢谢楼主

spwahaha 发表于 2016-10-29 07:33
A=[0, 0, 0, 0, 1] B = [1, 0, 0, 0, 0]
存的话存A=[{3:1}] B=[{0:1}]
算的话遍历A， 找B里对应index的 ...

如果用Map<Index, Value>存呢

pawprinter 发表于 2016-10-29 09:01
如果用Map存呢

觉得不如双指针好，，也是O（m+n）

spwahaha 发表于 2016-10-29 09:06
觉得不如双指针好，，也是O（m+n）

Map的话，只看一个vector，另一个vector对应的维度有没有value可以O(1)判断，那复杂度应该就是O(Math.min(m, n))?
比如v1 = {1:1, 5:1}, v2 = {1:1, 3:1, 6:7}
遍历v1的key-value，输出dotProduct = 1.
这样对么

pawprinter 发表于 2016-10-29 09:01
如果用Map存呢

这道题面试官貌似希望的解法是用两个list来分别保存非0的元素，保证顺序，然后再用双指针遍历找重合的index进行计算

pawprinter 发表于 2016-10-29 09:12
Map的话，只看一个vector，另一个vector对应的维度有没有value可以O(1)判断，那复杂度应该就是O(Math.min ...

但是vector要从硬盘里拿出来，然后各读一遍读进map才能做后面的那些， 光往map存就已经O(m+n)了。。。PS. 面试官让先设计存储格式

spwahaha 发表于 2016-10-29 09:15
但是vector要从硬盘里拿出来，然后各读一遍读进map才能做后面的那些， 光往map存就已经O(m+n)了。。。PS. ...

好的 好的 明白了，谢谢lz！

spwahaha 发表于 2016-10-29 07:31
他给的数组里都是质数，所以不用去重。。而且他让打印出来，所以空间是O(n)

请问lz的follow up怎么做的呢，是先sort么？

pawprinter 发表于 2016-10-29 10:45
请问lz的follow up怎么做的呢，是先sort么？

和subsetII一样，先sort然后加条件判断是否递归

spwahaha 发表于 2016-10-29 10:48
和subsetII一样，先sort然后加条件判断是否递归

明白了，多谢楼主！