java⽂件操作⾯试题_java处理超⼤⽂件⾯试题
1. 给定a、b两个⽂件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你出a、b⽂件共同的url？
⽅案1：可以估计每个⽂件安的⼤⼩为50G×64=320G，远远⼤于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分⽽治之的⽅法。
s 遍历⽂件a，对每个url求取，然后根据所取得的值将url分别存储到1000个⼩⽂件(记为)中。这样每个⼩⽂件的
⼤约为300M。
s 遍历⽂件b，采取和a相同的⽅式将url分别存储到1000各⼩⽂件(记为)。这样处理后，所有可能相同的url都在对应的⼩⽂件(
)中，不对应的⼩⽂件不可能有相同的url。然后我们只要求出1000对⼩⽂件中相同的url即可。
s 求每对⼩⽂件中相同的url时，可以把其中⼀个⼩⽂件的url存储到hash_set中。然后遍历另⼀个⼩⽂件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到⽂件⾥⾯就可以了。
⽅案2：如果允许有⼀定的错误率，可以使⽤Bloom filter，4G内存⼤概可以表⽰340亿bit。将其中⼀个⽂件中的url使⽤Bloom filter映射为这340亿bit，然后挨个读取另外⼀个⽂件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url(注意会有⼀定的错误率)。
ps：个⼈认为⽅案1中的估计是不是有问题 50亿就是5*10的9次⽅。⼩于等于5*2的30次⽅，即5G。
2. 有10个⽂件，每个⽂件1G，每个⽂件的每⼀⾏存放的都是⽤户的query，每个⽂件的query都可能重复。要求你按照query的频度排序。 ⽅案1：
s 顺序读取10个⽂件，按照hash(query)%10的结果将query写⼊到另外10个⽂件(记为)中。这样新⽣成的⽂件每个的⼤⼩⼤约玻璃垫片
也1G(假设hash函数是随机的)。
s ⼀台内存在2G左右的机器，依次对⽤hash_map(query, query_count)来统计每个query出现的次数。利⽤快速/堆/归并排 序按照出现次数进⾏排序。将排序好的query和对应的query_cout输出到⽂件中。这样得到了10个排好序的⽂件(记为)。
s 对这10个⽂件进⾏归并排序(内排序与外排序相结合)。
⽅案2：
⼀般query的总量是有限的，只是重复的次数⽐较多⽽已，可能对于所有的query，⼀次性就可以加⼊到内存了。这样，我们就可以采⽤trie 树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
⽅案3：
与⽅案1类似，但在做完hash，分成多个⽂件后，可以交给多个⽂件来处理，采⽤分布式的架构来处理(⽐如MapReduce)，最后再进⾏合并。(与1相⽐就是处理构架不同)
3. 有⼀个1G⼤⼩的⼀个⽂件，⾥⾯每⼀⾏是⼀个词，词的⼤⼩不超过16字节，内存限制⼤⼩是1M。返回频数最⾼的100个词。
⽅案1：顺序读⽂件中，对于每个词x，取，然后按照该值存到5000个⼩⽂件(记为)中。这样每个⽂件⼤概是200k左右。如果其中的有的⽂件超过了1M⼤⼩，还可以按照类似的⽅法继续往下分，知道分解得到的⼩⽂件的⼤⼩都不超过1M。对每个⼩⽂件，统计每个⽂件中出现的词以及相应的频率(可以采⽤trie树/hash_map等)，并取出出现频率最⼤的100个词(可以⽤含100个结点的最⼩堆)，并把100词及相应的频率存⼊⽂件，这样⼜得到了5000个⽂件。下⼀步就是把这5000个⽂件进⾏归并(类似与归并排序)的过
程了。
4. 海量⽇志数据，提取出某⽇访问百度次数最多的那个IP。
⽅案1：⾸先是这⼀天，并且是访问百度的⽇志中的IP取出来，逐个写⼊到⼀个⼤⽂件中。注意到IP是32位的，最多有个IP。同样可以采⽤映射的⽅法，⽐如模1000，把整个⼤⽂件映射为1000个⼩⽂件，再出每个⼩⽂中出现频率最⼤的IP(可以采⽤hash_map进⾏频率统计，然后再出频率最⼤的⼏个)及相应的频率。然后再在这1000个最⼤的IP中，出那个频率最⼤的IP，即为所求。环保防尘网
5. 在2.5亿个整数中出不重复的整数，内存不⾜以容纳这2.5亿个整数。
⽅案1：采⽤2-Bitmap(每个数分配2bit，00表⽰不存在，01表⽰出现⼀次，10表⽰多次，11⽆意义)进⾏，共需内存内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看
bitmap，把对应位是01的整数输出即可。
⽅案2：也可采⽤上题类似的⽅法，进⾏划分⼩⽂件的⽅法。然后在⼩⽂件中出不重复的整数，并排序。然后再进⾏归并，注意去除重复的元素。 6. 海量数据分布在100台电脑中，想个办法⾼校统计出这批数据的TOP10。
⽅案1：
s 在每台电脑上求出TOP10，可以采⽤包含10个元素的堆完成(TOP10⼩，⽤最⼤堆，TOP10⼤，⽤最⼩堆)。⽐如求TOP10⼤，我们⾸先取前10个元素调整成最⼩堆，如果发现，然后扫描后⾯的数据，并与堆顶元素⽐较，如果⽐堆顶元素⼤，那么⽤该元素替换堆顶，然后再调整为最⼩堆。最后堆中的元素就是TOP10⼤。
s 求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利⽤上⾯类似的⽅法求出TOP10就可以了。
7. 怎么在海量数据中出重复次数最多的⼀个？
⽅案1：先做hash，然后求模映射为⼩⽂件，求出每个⼩⽂件中重复次数最多的⼀个，并记录重复次数。然后出上⼀步求出的数据中重复次数最多的⼀个就是所求(具体参考前⾯的题)。
8. 上千万或上亿数据(有重复)，统计其中出现次数最多的钱N个数据。
⽅案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采⽤hash_map/搜索⼆叉树/红⿊树等来进⾏统计次数。然后就是取出前N个出现次数最多的数据了，可以⽤第6题提到的堆机制完成。
9. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
⽅案1：这题⽤trie树⽐较合适，hash_map也应该能⾏。
10. ⼀个⽂本⽂件，⼤约有⼀万⾏，每⾏⼀个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
书立⽅案1：这题是考虑时间效率。⽤trie树统计每个词出现的次数，时间复杂度是O(n*le)(le表⽰单词的平准长度)。然后是出出现最频繁的前10个词，可以⽤堆来实现，前⾯的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较⼤的哪⼀个。
11. ⼀个⽂本⽂件，出前10个经常出现的词，但这次⽂件⽐较长，说是上亿⾏或⼗亿⾏，总之⽆法⼀次读⼊内存，问最优解。
⽅案1：⾸先根据⽤hash并求模，将⽂件分解为多个⼩⽂件，对于单个⽂件利⽤上题的⽅法求出每个⽂件件中10个最常出现的词。然后再进⾏归并处理，出最终的10个最常出现的词。
12. 100w个数中出最⼤的100个数。
⽅案1：在前⾯的题中，我们已经提到了，⽤⼀个含100个元素的最⼩堆完成。复杂度为O(100w*lg100)。螺柱焊
⽅案2：采⽤快速排序的思想，每次分割之后只考虑⽐轴⼤的⼀部分，知道⽐轴⼤的⼀部分在⽐100多的时候，采⽤传统排序算法排序，取前100个。复杂度为O(100w*100)。
太空袋此⽅案假设数据全部可以载⼊内存，⽽且这个复杂度是指平均的情况，可以⽤SELECT来做
⽅案3：采⽤局部淘汰法。选取前100个元素，并排序，记为序列L。然后⼀次扫描剩余的元素x，与排好序的100个元素中最⼩的元素⽐，如果⽐这个最⼩的要⼤，那么把这个最⼩的元素删除，并把x利⽤插⼊排序的思想，插⼊到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。 这个⽅法就是插⼊排序
13. 寻热门查询：
搜索引擎会通过⽇志⽂件把⽤户每次检索使⽤的所有检索串都记录下来，每个查询串的长度为1-255字节。假设⽬前有⼀千万个记录，这些查询串的重复读⽐较⾼，虽然总数是1千万，但是如果去除重复和，不超过3百万个。⼀个查询串的重复度越⾼，说明查询它的⽤户越多，也就越热门。请你统计最热门的10个查询串，要求使⽤的内存不能超过1G。
(1) 请描述你解决这个问题的思路；
(2) 请给出主要的处理流程，算法，以及算法的复杂度。
⽅案1：采⽤trie树，关键字域存该查询串出现的次数，没有出现为0。最后⽤10个元素的最⼩推来对出现频率进⾏排序。
⽅案2：可以采⽤hash分块，然后统计各个块中的最热门的10个查询，然后⽤堆排序，时间复杂度=N
+n*m +nlog10 +m*10log10.此可以⽤来处理超过内存容量的情况
14. ⼀共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何到个数中的中数？
⽅案1：先⼤体估计⼀下这些数的范围，⽐如这⾥假设这些数都是32位⽆符号整数(共有个)。我们把0到的整数划分为N个范围段，每个段包含个整数。⽐如，第⼀个段位0到，第⼆段为到，…，第N个段为到。然后，扫描每个机器上的N个
数，把属于第⼀个区段的数放到第⼀个机器上，属于第⼆个区段的数放到第⼆个机器上，…，属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。下⾯我们依次统计每个机器上数的个数，⼀次累加，直到到第k个机器，在该机器上累加的数⼤于或等于，⽽在第k-
1个机器上的累加数⼩于，并把这个数记为x。那么我们要的中位数在第k个机器中，排在第位。然后我
们对第k个机器的数排序，并出第个数，即为所求的中位数。复杂度是的。
⽅案2：先对每台机器上的数进⾏排序。排好序后，我们采⽤归并排序的思想，将这N个机器上的数归并起来得到最终的排序。到第个便
是所求。复杂度是的。
15. 最⼤间隙问题
给定n个实数，求着n个实数在实轴上向量2个数之间的最⼤差值，要求线性的时间算法。
⽅案1：最先想到的⽅法就是先对这n个数据进⾏排序，然后⼀遍扫描即可确定相邻的最⼤间隙。但该⽅法不能满⾜线性时间的要求。故采取如下⽅法：
s 到n个数据中最⼤和最⼩数据max和min。
s ⽤n-2个点等分区间[min, max]，即将[min, max]等分为n-1个区间(前闭后开区间)，将这些区间看作桶，编号为，且桶的上界和桶i+1的下届相同，即每个桶的⼤⼩相同。每个桶的⼤⼩为：。实际上，这些桶的边界构成了⼀个等差数列(⾸项为min，公差为)，且认为将min放⼊第⼀个桶，将max放⼊第n-1个桶。
s 将n个数放⼊n-1个桶中：将每个元素分配到某个桶(编号为index)，其中，并求出分到每个桶的最⼤最⼩数据。
s 最⼤间隙：除最⼤最⼩数据max和min以外的n-2个数据放⼊n-1个桶中，由抽屉原理可知⾄少有⼀个桶是空的，⼜因为每个桶的⼤⼩相同，所以最⼤间隙不会在同⼀桶中出现，⼀定是某个桶的上界和⽓候某个桶的下界之间隙，且该量筒之间的桶(即便好在该连个便好之间的
桶)⼀定是空桶。也就是说，最⼤间隙在桶i的上界和桶j的下界之间产⽣。⼀遍扫描即可完成。
ps：这个⽅案很巧妙， 抽屉原理->⾄少有⼀个桶是空
16. 将多个集合合并成没有交集的集合：给定⼀个字符串的集合，格式如：。要求将其中交集不为空的集
合合并，要求合并完成的集合之间⽆交集，例如上例应输出。
(1) 请描述你解决这个问题的思路；
(2) 给出主要的处理流程，算法，以及算法的复杂度；
(3) 请描述可能的改进。
⽅案1：采⽤并查集。⾸先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于，⾸先查看aaa和bbb是否在同⼀个并查集中，如果不在，那么把它们所在的并查集合并，然后再看bbb和ccc是否在同⼀个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话，⾸先可以记录每个节点的根结点，改进查询。合并的时候，可以把⼤的和⼩的进⾏合，这样也减少复
杂度。
⽅案2：采⽤倒排表的⽅法做
17. 最⼤⼦序列与最⼤⼦矩阵问题
数组的最⼤⼦序列问题：给定⼀个数组，其中元素有正，也有负，出其中⼀个连续⼦序列，使和最⼤。
发泄壶⽅案1：这个问题可以动态规划的思想解决。设表⽰以第i个元素结尾的最⼤⼦序列，那么显然。基
于这⼀点可以很快⽤代码实现。
最⼤⼦矩阵问题：给定⼀个矩阵(⼆维数组)，其中数据有⼤有⼩，请⼀个⼦矩阵，使得⼦矩阵的和最⼤，并输出这个和。
⽅案1：可以采⽤与最⼤⼦序列类似的思想来解决。如果我们确定了选择第i列和第j列之间的元素，那么在这个范围内，其实就是⼀个最⼤⼦序列问题。如何确定第i列和第j列可以词⽤暴搜的⽅法进⾏。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议