FB 10.25 onsite + 10.5 on campus

lz能说说第一题的思路吗？

pawprinter 发表于 2016-10-29 05:39
lz能说说第一题的思路吗？

第一题用recursion, 类似有subset, 每次向下传的时候传一个productSoFar 就行了。

spwahaha 发表于 2016-10-29 05:51
第一题用recursion, 类似有subset, 每次向下传的时候传一个productSoFar 就行了。

总归就是求所有subset的product对么，如果要去重用HashSet? or 其他方法呢

spwahaha 发表于 2016-10-28 12:12
先问应该怎么存，然后问怎么求
1.  binary search (mlg(n))
2. O(m + n) 双指针

请问lz可不可以给一个具体的例子呢，m和n代表的是什么呢，vector dot不应该是两个维度一样的向量么？
binary search是怎么应用的呢，谢谢lz

这道题出了用map去找num-1，应该还是需要一个dp数组来记录每次比较的结果吧？

youto 发表于 2016-10-29 06:56
这道题出了用map去找num-1，应该还是需要一个dp数组来记录每次比较的结果吧？

这样的话复杂度就高了。。说了这个思路，面试官让加速，

pawprinter 发表于 2016-10-29 05:56
总归就是求所有subset的product对么，如果要去重用HashSet? or 其他方法呢

他给的数组里都是质数，所以不用去重。。而且他让打印出来，所以空间是O(n)

pawprinter 发表于 2016-10-29 05:59
请问lz可不可以给一个具体的例子呢，m和n代表的是什么呢，vector dot不应该是两个维度一样的向量么？
bi ...

A=[0, 0, 0, 0, 1] B = [1, 0, 0, 0, 0]
存的话存A=[{3:1}] B=[{0:1}]
算的话遍历A， 找B里对应index的值，所以binary  search

spwahaha 发表于 2016-10-29 07:30
这样的话复杂度就高了。。说了这个思路，面试官让加速，

是空间复杂度高了吗？时间上还是o(n)啊，初始化数组全为1，然后用map找num-1，找到后比较dp[map.get(num-1)]+1和dp[i]的大小，更新dp[i]为大的，这样不行吗？

youto 发表于 2016-10-29 07:38
是空间复杂度高了吗？时间上还是o(n)啊，初始化数组全为1，然后用map找num-1，找到后比较dp[map.get(num- ...

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