收到congressman的回复 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>EB23 - 劳工卡

收到congressman的回复

收到congressman的回复# EB23 - 劳工卡

l*h2015-06-04 07:06

1 楼

之前看到面经:"n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min
heap的方法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开
销，写了代码。"
min heap的方法容易解释，但是怎么O(1) space合并而时间效率和min heap一样呢？

h*x2015-06-04 07:06

2 楼

用cc 去load serve，然后通过email转账给ld的bb，用bb写check付房租...

n*a2015-06-04 07:06

3 楼

说我们的cases are currently undergoing case adjudication,这个意思是说到最后
一步了吗？pd是12年五月

b*u2015-06-04 07:06

4 楼

heap size n:
mn*logn
heap size k:
mn * log n * log k
（每个数要经历logn次merge）
所以还是同阶

t*u2015-06-04 07:06

5 楼

可以再萌一点吗

s*y2015-06-04 07:06

6 楼

如果是今年交的，应该是最后一步了，
去年交的话，可能会RFE体检

【在 n***a 的大作中提到】

: 说我们的cases are currently undergoing case adjudication,这个意思是说到最后
: 一步了吗？pd是12年五月

l*h2015-06-04 07:06

7 楼

没有太看懂你的
用一个size为n的min heap, 可以达到 mn*logn.
问题是现在只准用O(1) space, 要达到同样的时间效率

【在 b*****u 的大作中提到】

: heap size n:
: mn*logn
: heap size k:
: mn * log n * log k
: （每个数要经历logn次merge）
: 所以还是同阶

a*02015-06-04 07:06

8 楼

新大陆被最新再一次发现

【在 t***u 的大作中提到】

: 可以再萌一点吗

n*a2015-06-04 07:06

9 楼

自己顶一下，是tsc的

如果是今年交的，应该是最后一步了，去年交的话，可能会RFE体检

【在 s***y 的大作中提到】

: 如果是今年交的，应该是最后一步了，
: 去年交的话，可能会RFE体检

w*x2015-06-04 07:06

10 楼

NODE* mergLists(NODE* lsts[], int n)
{
if (lsts == NULL || n <= 0)
return NULL;
while (n > 1)
{
for (int i = 0; i < n; i += 2)
{
if (i+1 >= n)
{
lsts[(n-1)/2] = lsts[i];
break;
}
lsts[i/2] = mergeTwoList(lsts[i], lsts[i+1]);
}
n = (n+1)/2;
}
return lsts[0];
}

s*l2015-06-04 07:06

11 楼

直接用serve的bill pay 就好了！为什么还去 bb 转一圈

【在 h********x 的大作中提到】

: 用cc 去load serve，然后通过email转账给ld的bb，用bb写check付房租...

l*h2015-06-04 07:06

12 楼

通过多次两路归并？这个复杂度比min heap要高吧，
假如合并之后的总数据长度为n,
多次两路归并 O(nlog(n))
多路归并(用min heap): O(nlog(k)), k是原始linkedlist个数

【在 w****x 的大作中提到】

: NODE* mergLists(NODE* lsts[], int n)
: {
: if (lsts == NULL || n <= 0)
: return NULL;
: while (n > 1)
: {
: for (int i = 0; i < n; i += 2)
: {
: if (i+1 >= n)
: {

s*h2015-06-04 07:06

13 楼

serve可以email转账？

b*u2015-06-04 07:06

14 楼

假设k 是常数。也就是用一个常数size的heap
这样每轮merge对每个数插入的开销减小了，merge的轮数增多了。但是开销仅仅增大了
logk 倍

【在 l**h 的大作中提到】

: 没有太看懂你的
: 用一个size为n的min heap, 可以达到 mn*logn.
: 问题是现在只准用O(1) space, 要达到同样的时间效率

t*n2015-06-04 07:06

15 楼

yes

【在 s****h 的大作中提到】

: serve可以email转账？

p*22015-06-04 07:06

16 楼

但是怎么O(1) space合并而时间效率和min heap一样呢？
哪里来的这个要求？

l*42015-06-04 07:06

17 楼

serve limit太少不够房租 T_T

r*n2015-06-04 07:06

18 楼

interesting
are you suggesting double-layer merge?
merge every k lists and then merge n/k items from the previous merge
m*n*lgk*lg(n/k)
but in the second layer of merge, you still need O(n) space

【在 b*****u 的大作中提到】

: 假设k 是常数。也就是用一个常数size的heap
: 这样每轮merge对每个数插入的开销减小了，merge的轮数增多了。但是开销仅仅增大了
: logk 倍

t*n2015-06-04 07:06

19 楼

cc load的上限不够房租

★ 发自iPhone App: ChineseWeb 8.2.2

【在 h********x 的大作中提到】

: 用cc 去load serve，然后通过email转账给ld的bb，用bb写check付房租...

l*h2015-06-04 07:06

20 楼

原题：
http://www.mitbbs.com/article_t/JobHunting/32279127.html
第五轮，n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min heap的方
法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开销，写了
代码。

【在 p*****2 的大作中提到】

: 但是怎么O(1) space合并而时间效率和min heap一样呢？
: 哪里来的这个要求？