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

回复 1# 的帖子

一点想法：仅供参考，不知对否。
建一个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

回复 7# 的帖子

问题是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

这算什么测试?
页: [1] 2
查看完整版本: 淘宝的一道面试题