淘宝的一道面试题

mcfnhm · 发表于 2010-5-4 11:35:49

淘宝的一道面试题

在一个100G的文件里有一堆数字，试找出100个最大的数字？！

【只要求写出，解题的思想及其所用到的知识，因为完整的解题过程太长】

zhangting85 · 发表于 2010-5-4 13:09:27

问题难点为文件大小达100G，假如文件大小为1k，这个问题很好解决。
所以，把文件进行分割，每块中取最大的100个数字，再把各块的100个数字进行比较。
则所需时间可限制在可接受范围内。

fivekb · 发表于 2010-5-4 14:59:24

一点想法：仅供参考，不知对否。
建一个100的最小堆来存储最大的100个数，遍历整个文件并不断更新堆可得结果，需要进行优化以满足时间要求，比如遍历方式等，将文件分块之类的……

syang0517 · 发表于 2010-5-4 16:21:28

不错，顶。这道题有点意思。

crystal50112 · 发表于 2010-5-4 18:07:21

这是测试的面试题？？

云层 · 发表于 2010-5-4 22:38:08

多线程+队列

zeroing7 · 发表于 2010-5-5 08:04:39

100G文件里有一堆数字？请问是100G中全部为数字吗？还是100G里有的是数字，还有不是数字的？
如果全为数字，写个C的程序，冒泡排列就可以
如果不是全为数字，先要找出是数字的，再排列！

月上百合 · 发表于 2010-5-5 08:55:09

我也想到了冒炮排序法

peag · 发表于 2010-5-5 09:06:21

::ysssn::: 算法快忘没了，得补补了

davy_chen · 发表于 2010-5-5 09:41:36

借力实现

chengning · 发表于 2010-5-5 10:28:54

冒泡的话估计100G 的数据估计计算量太大了无法实现吧就算CPU 受的了要跑多长时间啊

mcfnhm · 发表于 2010-5-6 11:57:11

问题是100G啊, 100G里全部是数字

mcfnhm · 发表于 2010-5-6 11:59:41

2# 回答的很好, 我当时也这么想的, 我是按1024字节, 1024字节分割的

IUHK · 发表于 2010-5-6 12:12:52

弱弱地问下，文件有索引吗？

hueslife · 发表于 2010-5-6 12:57:55

::JFBQ00125080410a:::
分块取前100个，块内再按算法由大到小取前100个

msnshow · 发表于 2010-5-6 13:37:46

这道题类似之前在论坛看到的，在100G的文件中，查找中值

sosocold · 发表于 2010-6-2 08:20:38

1.算法的话，先找出所有的数字，然后大顶堆排序
2.最简单的是导入数据库，直接一个select,然后按大小排序

wy3552128 · 发表于 2011-1-8 19:02:21

集思广益

愚人 · 发表于 2011-1-11 20:09:22

嗯……没思路……

最大的只有一个吧，100个还能称“最”

丢了朵朵 · 发表于 2011-1-12 11:32:50

这算什么测试?

		自动登录	找回密码
密码			(注-册)加入51Testing

[讨论] 淘宝的一道面试题