认识达内从这里开始

认真做教育专心促就业

Java大数据面试常见的几大算法问题

发布：宁波达内培训
来源：企业面试题
时间：2020-02-22 16:00

目前Java大数据的人才稀缺，很多想进入大数据行业的人们经过了大数据培训学成出来，只剩下最后一步就能顺利进入大数据行业，就是Java大数据面试。很多IT人才技术操作很优秀，没有可挑剔的，但是就是在面试时总卡壳，同时毕业的学员都已经收到好几个offer了，但是这部分学员就是吃吃得不到企业的青睐，这是为什么呢，原因有很多，其中之一就是Java大数据面试题不过关，Java大数据面试常见的几大算法问题都有哪些，下面分享一些面试题的干货。

1、递归和迭代

对程序员来说，递归应该是一个与生俱来的思想(a built-in thought)，可以通过一个简单的例子来说明。

问题：有n步台阶，一次只能上1步或2步，共有多少种走法。

步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。

为了走完n步台阶，只有两种方法：从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数，那么f(n) = f(n-1) + f(n-2)。

步骤2: 确保开始条件是正确的。

f(0) = 0;

f(1) = 1;

最直接的想法是将递归转换为迭代，对于这个例子来说，迭代花费的时间更少。

2、海量日志数据，提取出某日访问百度次数最多的那个IP

可以给出的方案是：IP的数目还是有限的，最多2^32个，所以可以考虑使用hash将ip直接存入内存，然后进行统计。

具体讲解一下该方案：前提条件是同一天，并且是访问百度的日志中的IP取出来，逐个写到一个大文件中。注意到IP是32位的，最多有个2^32个 IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP及相应的频率。然后再在这 1000个最大的IP中，找出那个频率最大的IP，就是所求的答案。

3、这是一道腾讯的面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中?

这道题有两种解决方案：

方案一：申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在;

方案二：给定一个数可能在也可能不在其中，把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类: 1.最高位为0 2，最高位为1 并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿;与要查找的数的最高位比较并接着进入相应的文件再查找，再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1，并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿;与要查找的数的次最高位比较并接着进入相应的文件再查找。以此类推，就可以找到了,而且时间复杂度为O(logn)。

< 上一篇：十个经典的Python面试题

下一篇：程序员如何解答面试环节的薪资问题？ >