FB 10.25 onsite + 10.5 on campus

发面经攒人品

On campus:
   Meeting rooms II, Move zeros (minimize write)
Onsite:
   Coding1: Product of subset of

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

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

n) 时间复杂度

感觉周围人很强， 大家都能把题很好的做出来，不知道Facebook会怎么招。 Good Luck.


  

～这个不能On吧。DP O(n方），Binary search OlgN吧。 能O（N）的应该是order可以打乱，用Hashmap做。

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: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.
这样对么

楼主最后一题 请问如果是LIS 的话 为什么不是 1 3 5 而是 2,3 或者 4,5呢？

忽视我把，，没看见那个BY 1 SORRY~

...好多人都挤在这一天啊...

leixiang5 发表于 2016-10-26 08:45
...好多人都挤在这一天啊...

还是错过了群主

spwahaha 发表于 2016-10-26 09:09
还是错过了群主

哇塞。你是哪位呀～

请问楼主最后一道怎么做的？

最后一题想了想，确实可以O(n)实现，遍历数组，查找map.containsKey(nums[i] - 1)就行了，跟Longest Consecutive Sequence有点像，而跟Longest Increasing Sequence不太像，前者只用查一个值可以直接hash做，后者是一个range就没法这样做了

仔细看了下楼主的意思，其实就是Longest Consecutive Sequence原题