x****n
发帖数: 29 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: xychen (xychen), 信区: JobHunting
标 题: 一道MS面试题
发信站: BBS 未名空间站 (Tue Apr 24 22:08:59 2012, 美东)
如何用100机器，sort large file of terabyte 64位整数？
请问这是考并行排序算法吗？ |
d****n
发帖数: 1637 | 2 我的愚见。
每个机器拿1%数据。回去sort.(it can use external sort strategy)
一个host, 查看每个机器，如果是lowest , 假设是ascending order, 拿来，如果不是
，hold.
怎么选最小的 struct over 100 machines, 可以用 max/min heap.
我干过 sort 800Gb 的文件，用2小时。不过是用一个机器。 |
c****p
发帖数: 6474 | 3 把值域分100份，落入相应值域的数分到同一个机器上。
每个机器排完序之后和它在hypercube上的同维邻居做merge sort。【 在 xychen (
xychen) 的大作中提到: 】 |
a*w
发帖数: 4495 | 4 为啥不给64或128台？
100台有什么特别含义？
【在 c****p 的大作中提到】
: 把值域分100份，落入相应值域的数分到同一个机器上。
: 每个机器排完序之后和它在hypercube上的同维邻居做merge sort。【 在 xychen (
: xychen) 的大作中提到: 】
|
d****n
发帖数: 1637 | 5 I guess it meant to fit "one percent".
【在 a*w 的大作中提到】
: 为啥不给64或128台？
: 100台有什么特别含义？
|
y***d
发帖数: 2330 | 6 既然每个机器覆盖不同的值域，为什么最后还要 merge sort？
【在 c****p 的大作中提到】
: 把值域分100份，落入相应值域的数分到同一个机器上。
: 每个机器排完序之后和它在hypercube上的同维邻居做merge sort。【 在 xychen (
: xychen) 的大作中提到: 】
|
f********o
发帖数: 1163 | 7 同问这个问题。
【在 y***d 的大作中提到】
: 既然每个机器覆盖不同的值域，为什么最后还要 merge sort？
|
d****n
发帖数: 1637 | 8 machine1:1 2 4 5 9 10
machine2: 2 3 5 7 9
merge 1 &2 : 1 2 2 3 4 5 5 7 9 9 10
machine3: 2 10 13
machine4: 7 11 19
merge 3 &4 : 2 7 10 11 13 19
take merged 1&2 and 3&4 : 1 2 2 2 2 3 4 5 5 7 7 9 9 10 10 11 13 19
done |
|
y***d
发帖数: 2330 | 9 binary merge is not good for this case, too much disk writing.
【在 d****n 的大作中提到】
: machine1:1 2 4 5 9 10
: machine2: 2 3 5 7 9
: merge 1 &2 : 1 2 2 3 4 5 5 7 9 9 10
: machine3: 2 10 13
: machine4: 7 11 19
: merge 3 &4 : 2 7 10 11 13 19
: take merged 1&2 and 3&4 : 1 2 2 2 2 3 4 5 5 7 7 9 9 10 10 11 13 19
: done
|
m*p
发帖数: 1331 | |
x****n
发帖数: 29 | 11 我答得也是external sort. 但不知道是细节没有答好，还是有其他并行排序方法。
好像这道题比较难呢，这还是电面。
【在 x****n 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: xychen (xychen), 信区: JobHunting
: 标 题: 一道MS面试题
: 发信站: BBS 未名空间站 (Tue Apr 24 22:08:59 2012, 美东)
: 如何用100机器，sort large file of terabyte 64位整数？
: 请问这是考并行排序算法吗？
|
X****r
发帖数: 3557 | 12 For these kind of questions, your interaction with the interviewer, your
approach to the problem, and your thinking process are probably much
more important than the exact solution you gave at the end.
【在 x****n 的大作中提到】
: 我答得也是external sort. 但不知道是细节没有答好，还是有其他并行排序方法。
: 好像这道题比较难呢，这还是电面。
|
x****n
发帖数: 29 | 13 交流应该没问题，HR都肯定过的，而且刚好对external sort熟悉。所以才认为可能要用
并行的方法。
【在 X****r 的大作中提到】
: For these kind of questions, your interaction with the interviewer, your
: approach to the problem, and your thinking process are probably much
: more important than the exact solution you gave at the end.
|
