Facebook 脸书 莫名其妙跪经

第一题 空间复杂度就是K啊，你只能每次放k个数进去去top那个然后再取第二个。没有比这个更优化做法目前。是不是K很大？如果是，你理解错了，如果K很大是类似系统设计的题吧？

fangwei007 发表于 2018/11/02 01:39:33


这两个月运气差到爆炸, 开了三年的车, lease到期的前一个月被淹了, 引擎全换, 花了1.5W, 艾玛, 所有事情全在这俩月

摸摸 来年再战 运气这东西都是一阵一阵的

pat pat, recruiter有说是挂在debrief还是hc阶段了吗?

https://leetcode.com/problems/merge-k-sorted-lists/solution/
solution 5，其实就是merge sort，时间nlogk，空间constant
供参考

groundzyy1 发表于 2018-11-2 03:51
记不太清了，也没仔细看全文，之前面亚麻也是merge这个，好像外排序的方式在时间复杂度上更好。

我觉得不是时间复杂度更好，是可以并行执行，最后变成了多线程（甚至是分布式）和单线程的区别把。

补充内容 (2018-11-2 12:21):
空间复杂度确实是merge sort比priority queue要好 尤其是当k很大的时候

ydzhang 发表于 2018-11-2 06:05
第一题 空间复杂度就是K啊，你只能每次放k个数进去去top那个然后再取第二个。没有比这个更优化做法目前。是 ...

heap的size就是K啊, 我们一直再算时间复杂度; 如果两两merge, 空间复杂度可不止K. 原题问的也是每一行的n可能很大, 这是coding轮, 跟系统设计没关系.

张个灯结彩 发表于 2018-11-2 11:31
https://leetcode.com/problems/merge-k-sorted-lists/solution/
solution 5，其实就是merge sort，时间nl ...

请看清楚我的题目, 是sorted arrays不是lists, 不是lists, 不是lists!!!!

和楼主情况类似 昂赛之后等offer 结果过了10天之后被拒 说very tough decision

fangwei007 发表于 2018-11-2 22:11
heap的size就是K啊, 我们一直再算时间复杂度; 如果两两merge, 空间复杂度可不止K. 原题问的也是每一行的n ...

I am confused.

time complexity is you have to process every elements, and each will go into the heap
so, n*log(k)

space complexity is k (k elements in the heap at a time)

ydzhang 发表于 2018-11-3 03:37
I am confused.

time complexity is you have to process every elements, and each will go into the ...

没错的, 本来就这样, 前面有个人算错了复杂度, heap的解法时间复杂度 nklogk, 空间复杂度k. 这里的n是每一行的元素个数, 跟你说的其实是一样的, 不用confused, 你是对的.

之前有个人胡说了个说log(nk), 还装的跟自己很对似的