问道amazon的电面题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道amazon的电面题

问道amazon的电面题# JobHunting - 待字闺中

c*02011-02-20 08:02

1 楼

k sorted list, with one list with n integers. Sort all the lists.
单机版，比较简单，maintain一个heap就行了。kn*lg(k)
extention, 给m个机器，请充分利用，加快sort的速度。
我大概从几个方面来解，都被否决了。
1，每个slave machine，分配一个list，然后再主机merge，（他说没有加快时间）
2，我想两个两个merge，（他还是不够满意）
3，我想利用bucket的想法，（他说数可能不是平均分布）
真的不知道怎么玩了，谁懂的给讲讲.谢谢!

g*s2011-02-20 08:02

2 楼

yes, it doesn't help at all.
this should be right.

【在 c*****0 的大作中提到】

: k sorted list, with one list with n integers. Sort all the lists.
: 单机版，比较简单，maintain一个heap就行了。kn*lg(k)
: extention, 给m个机器，请充分利用，加快sort的速度。
: 我大概从几个方面来解，都被否决了。
: 1，每个slave machine，分配一个list，然后再主机merge，（他说没有加快时间）
: 2，我想两个两个merge，（他还是不够满意）
: 3，我想利用bucket的想法，（他说数可能不是平均分布）
: 真的不知道怎么玩了，谁懂的给讲讲.谢谢!

c*02011-02-20 08:02

3 楼

第二个时间复杂度，我分析的不好。
感觉应该是小于 k*n*lg(k), 大于 k*n. 请指点一二。

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

:
: yes, it doesn't help at all.
: this should be right.

g*s2011-02-20 08:02

4 楼

merge in parallel. draw a picture and u will see the total complexity is
x + x/2 + x/4 ... = 2x, where x = k*n.

【在 c*****0 的大作中提到】

: 第二个时间复杂度，我分析的不好。
: 感觉应该是小于 k*n*lg(k), 大于 k*n. 请指点一二。

p*r2011-02-20 08:02

5 楼

...
x equals the total length of previous two lists
it's not constant k*n

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

: merge in parallel. draw a picture and u will see the total complexity is
: x + x/2 + x/4 ... = 2x, where x = k*n.

g*s2011-02-20 08:02

6 楼

k lists, each n long. total x=k*n ah.

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

: ...
: x equals the total length of previous two lists
: it's not constant k*n

c*02011-02-20 08:02

7 楼

Thanks, that should be correct for k machines.
By the way, if the two way-merging method is used in one machine, then the
total complexity should be (2^k) * n, is that right?

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

: merge in parallel. draw a picture and u will see the total complexity is
: x + x/2 + x/4 ... = 2x, where x = k*n.

l*a2011-02-20 08:02

8 楼

i think it is k*n*lg(n).
because there are lg(n) levels.
each level the complexity is k*n in total.

【在 c*****0 的大作中提到】

: 第二个时间复杂度，我分析的不好。
: 感觉应该是小于 k*n*lg(k), 大于 k*n. 请指点一二。

e*a2011-02-20 08:02

9 楼

For multi machines, the best you can achieve is 2nlogk.
suppose k=8, you have 4 machines
level1, merge two lists on each machine, runtime 2*n
level2, now you reduced 8 lists into 4. If you continue the above scheme,
you can only use two machines. How do you use 4 machines? Well, for each
pair, take one list's median, binary search in the other list.
So you have list A: [A1, ..., An, A_n+1, ... A_2n], and list B [B1, ..., Bk,
B_k+1, ..., B_2n]. Now you use two machines to merge two sublists, and
concatenate the results. Again, runtime is 2*n
So you achieve in total 2n*logk.

m*d2011-02-20 08:02

10 楼

面试题：
http://jobguideweb.com/it-jobs/google.html

【在 c*****0 的大作中提到】

u*e2011-02-20 08:02

11 楼

可不可以这样，当k>m时，两个两个merge
当kge，完成后再按i序对相邻的机器进行conjunction以正确方式插入叠盖部分。T＝O(k *
n/m * logk)+O(Conjunction)
conjunction的方法是（assume i+2的最小节点不会比i的最大节点还小）：
当i>1时，记录下merge时首元素最大的node，并将该node之前的所有node从后往前merg
e回 i-1 list的尾部。
conjunction的worst case很难看，是(k-1)*n/m.但对随机生成的均衡队列，average可
以认为是小数。且conjunction可以并发进行，所以
O(conjunction)可以忽略。
总的T=O(k*n/m*logk);
这种方法适合起始当k>>m使得通过两两merge生成的k'<=m个队列时相对均衡或给的每个
原list就相对较均衡的情况下。这样conjunction的代价很小。
如果k<=m，且分布不均匀
依然是进行分段的思路：
1 把list[0]等分成m段
2 当i>0时对第i台机子在每个list里二分找到该list在该机器的段起点（大于list[0]在
对应段起点的最小值）
3 每台机子不等长k merge，每个list的结束标志是它的值大于list[0]在该机器的段终
点。
4 把每台机器结果串起来就行。

【在 c*****0 的大作中提到】