51Testing软件测试论坛

标题: 淘宝的一道面试题 [打印本页]

作者: mcfnhm 时间: 2010-5-4 11:35
标题: 淘宝的一道面试题
淘宝的一道面试题

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

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

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

作者: fivekb 时间: 2010-5-4 14:59
标题: 回复 1# 的帖子
一点想法：仅供参考，不知对否。
建一个100的最小堆来存储最大的100个数，遍历整个文件并不断更新堆可得结果，需要进行优化以满足时间要求，比如遍历方式等，将文件分块之类的……

作者: syang0517 时间: 2010-5-4 16:21
不错，顶。这道题有点意思。

作者: crystal50112 时间: 2010-5-4 18:07
这是测试的面试题？？

作者: 云层 时间: 2010-5-4 22:38
多线程+队列

作者: zeroing7 时间: 2010-5-5 08:04
100G文件里有一堆数字？请问是100G中全部为数字吗？还是100G里有的是数字，还有不是数字的？
如果全为数字，写个C的程序，冒泡排列就可以
如果不是全为数字，先要找出是数字的，再排列！

作者: 月上百合 时间: 2010-5-5 08:55
我也想到了冒炮排序法

作者: peag 时间: 2010-5-5 09:06
::ysssn::: 算法快忘没了，得补补了

作者: davy_chen 时间: 2010-5-5 09:41
借力实现

作者: chengning 时间: 2010-5-5 10:28
冒泡的话估计100G 的数据估计计算量太大了无法实现吧就算CPU 受的了要跑多长时间啊

作者: mcfnhm 时间: 2010-5-6 11:57
标题: 回复 7# 的帖子
问题是100G啊, 100G里全部是数字

作者: mcfnhm 时间: 2010-5-6 11:59
2# 回答的很好, 我当时也这么想的, 我是按1024字节, 1024字节分割的

作者: IUHK 时间: 2010-5-6 12:12
弱弱地问下，文件有索引吗？

作者: hueslife 时间: 2010-5-6 12:57
::JFBQ00125080410a:::
分块取前100个，块内再按算法由大到小取前100个

作者: msnshow 时间: 2010-5-6 13:37
这道题类似之前在论坛看到的，在100G的文件中，查找中值

作者: sosocold 时间: 2010-6-2 08:20
1.算法的话，先找出所有的数字，然后大顶堆排序
2.最简单的是导入数据库，直接一个select,然后按大小排序

作者: wy3552128 时间: 2011-1-8 19:02
集思广益

作者: 愚人 时间: 2011-1-11 20:09
嗯……没思路……

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

作者: 丢了朵朵 时间: 2011-1-12 11:32
这算什么测试?

作者: zwb131442 时间: 2011-1-28 15:48
没意思

作者: xfde51 时间: 2011-1-31 11:40
100G文件中的数字都是连续排列的？例如：“123456823424213234....”无限下去？
那最大的就是9....
如果数字间是有什么分割开的。。。那你也分割开来过滤下就好了。

作者: ryugun 时间: 2011-2-9 15:15
新人觉得~这个题出的需求不明不白~~需求测试阶段就过不了了~
100G的文件这个说法根本就没说清楚~万一这100G里全是字符，没有数字咋办？
如果需求没啥问题，小弟认为这里考的关键点在于算法和程序的处理时间上~~~不知对不？

作者: lityelf 时间: 2011-2-9 21:19

纠结ing，，，，，

作者: archonwang 时间: 2011-2-10 09:43
算法问题还是方法问题？

作者: 51happy 时间: 2011-4-19 23:10
这是测试的面试题目？

作者: y_test 时间: 2011-4-20 08:36
100G 那还的分析数据都有什么类型的，根据具体的类型还要分析

作者: lingting 时间: 2013-3-21 15:32
我想到的方案，不知道是否可行，请专家点评

去前100个数进行排序。在依次循环取101 - 最后的数，和倒叙后的第100个数进行比较，大于则加入队列中。原来的第100个数被丢弃。

这样是否在性能上存在问题。在排序和执行上应该比较短的，但是需要全部数据循环一次 - 100 。。

作者: lingting 时间: 2013-3-21 15:32
飞飞飞飞飞飞

作者: hutao001 时间: 2013-3-21 16:10
这不是测试的面试题吧？

欢迎光临 51Testing软件测试论坛 (http://bbs.51testing.com/)