Facebook 脸书 莫名其妙跪经

fangwei007 发表于 2018-11-3 04:41
没错的, 本来就这样, 前面有个人算错了复杂度, heap的解法时间复杂度 nklogk, 空间复杂度k. 这里的n是每 ...

我是不明白为啥这个不是最优。这个就是最优啊。

LZ 有实力找工作有时真心觉得要运气system design 能不能指点下呢? 我的想法是aggregator 可以在streaming job or ETL 来应用, 优化存储, retention的处理我觉得因该适用aggregator or ETL 的方式来优化sharding的部分指的是range sharding 道不同的data center然后data center 因为distributed 所以要synchonization ?

guo0693 发表于 2018/11/02 12:18:01


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

补充内容 (2018-11-2 12:21):
空间复杂度确实是merge sort比priorit...

空间复杂度是priority queue好，不算最后结束占的n，只用k，merge sort需要额外n。如果把最后结果算的空间算上，就是priority queue需要额外k。

时间复杂度啥priority queue是每个数字都要经历一次logk，merge sort 的话并不算每个数字都要logk。理论上有个巨长无比的数组最后合并，只需要n时间。

很久不做算法题了，可能这儿说的不对。但是，逻辑上就是外排序最后用merge sort是有原因的。

groundzyy1 发表于 2018/11/04 03:21:32


空间复杂度是priority queue好，不算最后结束占的n，只用k，merge sort需要额外n。如果把最后结果算的空间算上，就是priority queue需要额外k。

时间复杂度啥pr...

手机上补充不了，应该还有个就是可以并行进行merge sort

fangwei007 发表于 2018-11-2 02:02
另外啊, 其实不想说, 但是 你分析heap的时间复杂度是错的, log(k*n) 是什么 ?
heap初始化是k*logk
然 ...

楼主，如果是k个array，每个Array长度为n
那么总共需要sort的元素数目为k*n
那么用heap sort 时间复杂度应该是k*n * log（k*n）吧？ （参照heap sort average performance O(nlogn)）
空间复杂度，用queue的话是o（k）
您觉得呢？


补充内容 (2018-11-7 09:52):
而且，用heap sort 每个元素都要进heap一次，出heap一次，感觉 时间复杂度应该是k*n * log（k*n）。

漫漫人生路 发表于 2018/11/07 09:45:38


楼主，如果是k个array，每个Array长度为n
那么总共需要sort的元素数目为k*n
那么用heap sort 时间复杂度应该是k*n * log（k*n）吧？ （参照heap sort...

k个array是已经sort好了的，所以不是一个kn数量的排序。heap的大小是k。

漫漫人生路 发表于 2018-11-7 09:45
楼主，如果是k个array，每个Array长度为n
那么总共需要sort的元素数目为k*n
那么用heap sort 时间复杂 ...

楼下已经回你了.
再提醒一遍, heap的size是k, 不是k*n, 所以肯定不是log(k*n)

每次push和pop都是logk, 所以是O(k*n*log(k))

这个题好好做一做, 不然真的会挂的

补充内容 (2018-11-7 23:13):
你可能理解不对, heap里面不是push所有元素, 还是每个row的头指针, 然后pop + 移动指针 + push, 维持heap的size是k, 不是k * n, 这样希望你能清楚理解

fangwei007 发表于 2018-11-7 23:09
楼下已经回你了.
再提醒一遍, heap的size是k, 不是k*n, 所以肯定不是log(k*n)

好的，谢谢楼主讲解，这里的确是想错了，heap的size为k决定了进heap的时间是log（k）， 这里跟需要sort的元素总数目并不是相等的。

脸家好像做题做得顺并没有什么用，我当时也是你这样。。听说是有一套很玄学的culture fit的衡量标准==

junhe 发表于 2018-11-8 05:06
脸家好像做题做得顺并没有什么用，我当时也是你这样。。听说是有一套很玄学的culture fit的衡量标准==

什么culture fit标准 ?? 具体有什么 ??