认识达内从这里开始

认真做教育专心促就业

Java编程笔试面试题

发布：长春达内
来源：达内新闻
时间：2018-08-27 16:48

在Java求职的过程中，HR们经常能弄到各种各样的题目来考核大家，所以，求职者们要注意日常积累，多接触一些题目，以免在面试时遇到难解的问题。本文长春达内IT培训为大家介绍Java编程笔试面试题。

1. 在2.5亿个整数中找出不重复的整数，内存不足以容纳这2.5亿个整数。

方案1：采用2-Bitmap(每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义)进行，共需内存内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

方案2：也可采用上题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

2. 海量数据分布在100台电脑中，想个办法高校统计出这批数据的TOP10。

在每台电脑上求出TOP10，可以采用包含10个元素的堆完成(TOP10小，用最大堆，TOP10大，用最小堆)。比如求TOP10大，我们首先取前 10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大。

求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

3. 怎么在海量数据中找出重复次数最多的一个?

先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考上期IP那题)。

4. 上千万或上亿数据(有重复)，统计其中出现次数最多的钱N个数据。

上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。

5. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现?

这题用trie树比较合适，hash_map也应该能行。

6. 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。

< 上一篇：Java面试：投行经典多线程和并发面试题

下一篇：HashMap的底层原理是什么? >