收到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一样呢？
: 哪里来的这个要求？

a*q2015-06-04 07:06

21 楼

有BB，网上申请serve被拒了，说已经有BB了，如何解？谢谢！

l*h2015-06-04 07:06

22 楼

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

b*e2015-06-04 07:06

23 楼

找个ld，让她申请bb

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

: 有BB，网上申请serve被拒了，说已经有BB了，如何解？谢谢！

w*x2015-06-04 07:06

24 楼

嗯，是啊。有道理。
可能面试官自己也搞错了

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

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

t*52015-06-04 07:06

25 楼

What is bb?

t*n2015-06-04 07:06

26 楼

a. BestBuy
b. BednBreakfast
c. Blackberry
d. BlueBird

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

: What is bb?

w*32015-06-04 07:06

27 楼

是BigBoob

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

: a. BestBuy
: b. BednBreakfast
: c. Blackberry
: d. BlueBird

G*22015-06-04 07:06

28 楼

一个人不能同时有Serve和BB，先关掉一个，才能给你另一个。

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

: 有BB，网上申请serve被拒了，说已经有BB了，如何解？谢谢！

G*22015-06-04 07:06

29 楼

这是网站，读读就知道了。 www.bluebird.com

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

: What is bb?

G*k2015-06-04 07:06

30 楼

可能人家只能写check吧

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

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

z*22015-06-04 07:06

31 楼

回过头来还得用bank account还CC,何苦呢？

a*q2015-06-04 07:06

32 楼

只有张BB，申了以后还没用过，听说现在Load钱进去也很麻烦
请问serve有什么不同？我主要就是想交房租和utility什么的（目前用支票交），相当
于间接用CC，赚点点数，这样可行吗？谢谢！

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

: 一个人不能同时有Serve和BB，先关掉一个，才能给你另一个。

c*z2015-06-04 07:06

33 楼

BB写check是跟checking一样有个支票本，还是网上填，他们给寄到对方地址呢？

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

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

t*j2015-06-04 07:06

34 楼

好东西