Java面试系列——数据结构与算法

数据结构与算法 7.1 数据结构基础 如何理解基本的数据结构？

避免孤立地学习知识点，要结合学习。 比如在实际应用中，我们经常会用到查找、排序、增删改查，这些在我们的各种管理系统、数据库系统、操作系统等中都是非常常用的，我们用这个线索来串联知识点：

7.2 算法思想 常见的算法思想有哪些？ 7.3 常用排序算法 常用排序算法有哪些？

在综合复杂稳定的情况下，通常是Hill，需要掌握快速排序和归并

7.4 大数据处理算法什么是海量数据处理？ 如何解决？

所谓海量数据处理，无非是基于海量数据的存储、处理、运算。 massive volume的意思就是数据量太大，所以要么无法在短时间内快速解决，要么数据量太大，一次无法加载到内存中。

解决方案呢？

大数据处理中的分而治之思维？

分而治之/哈希映射+哈希统计+堆/快速/归并排序，说白了就是先映射，再计数，最后排序：

海量日志数据，提取某日百度访问量最大的IP？

分析：“首先是今天，把访问百度的日志里的IP拿出来，一个一个写到一个大文件里。注意IP是32位的，最多2^32个也可以使用映射的方式，比如00，将整个大文件映射成1000个小文件，然后在每个小文件中找出出现频率最高的IP（可以使用hash_map对其中的所有IP进行频率统计1000个文件，然后依次找出每个文件中出现频率最高的IP）和对应的频率。然后在最大的1000个IP中，找到出现频率最高的IP，这就是你想要的。

关于这个话题还有几个问题，如下：

寻找热门查询，统计 300 万个查询字符串中的前 10 个查询？

原标题：搜索引擎会通过日志文件记录用户每次搜索使用的所有搜索字符串，每个查询字符串的长度为1-255字节。 假设当前有1000万条记录（这些查询字符串重复度比较高，虽然总数是1000万条，但是如果去掉重复，也不会超过300万条）。一个查询字符串的重复度越高，意思是查询它 用户越多，越流行），请统计最流行的10个查询字符串，所需内存不能超过1G。

答：从上面第一个问题，我们知道大数据属于小数据。 比如有1亿个IP要找Top 10，可以先把IP分成1000个小文件，保证一个文件中只出现一种IP，对每个小文件中的IP进行hashmap计数统计，按数量排序，最后merge或者min-heap依次处理每个小文件的前10个，得到最终结果。

但是如果数据量比较小，能不能一次性加载到内存中呢？ 比如第二题，虽然有1000万个Query，但是由于重复度高，实际上只有300万个Query，每个Query是255Byte，所以可以考虑全部放到内存中（假设300万个字符串没有重复且为最大长度，那么最大内存占用为3M*1K/4=0.75G。所以所有的字符串都可以存入内存处理），现在只需要一个合适的数据结构，在这里，HashTable绝对是我们的首选。

所以我们放弃分治/哈希映射这一步，直接进行哈希统计，然后排序。 所以，对于这种典型的TOP K问题，对策往往是：hashmap + heap。 如下：

别忘了这篇文章中描述的堆排序思想：“维护一个k个元素的最小堆，即用一个容量为k的最小堆来存放遍历的前k个数，并假设它们是最大的k个数，建堆耗时O(k)，调整堆后（耗时O(logk)），有k1>k2>...kmin（kmin设为小顶堆中最小元素).继续遍历序列，每次将一个元素x与堆顶元素进行比较，如果x>kmin，则更新堆（x进入堆，时间为logk），否则不更新堆更新。这样一来，总时间为O(k*logk+(nk)logk)=O(nlogk)。这种方法得益于堆中，搜索等各种操作的时间复杂度为logk。” --第三章续比特币采用的主要加密算法，Top K算法问题的实现。

当然也可以使用trie树，key域存储查询字符串出现的次数，没有出现则为0。 最后用最少推10个元素对出现频率进行排序。

有一个1G大小的文件，里面每一行是一个word，一个word的大小不超过16字节，内存限制为1M。 返回频率最高的100个词？ 海量数据分布在100台电脑中。 想办法高效统计这批数据的TOP10？

如果每个数据元素只出现一次比特币采用的主要加密算法，并且只出现在某台机器上，那么可以按照以下步骤统计出出现次数TOP10的数据元素：

但是如果同一个元素在不同的电脑上重复出现怎么办，如下面的例子，这时候，你可以有两种方法：

有10个文件，每个文件1G，每个文件的每一行存储用户的查询，每个文件的查询可能会重复。 问你按查询频率排序？

方案一：

方案二：一般查询总量是有限的，但是重复次数比较多。 可以一次将所有查询添加到内存中。 这样我们就可以使用trie tree/hash_map直接统计每个query的出现次数，然后根据出现次数进行fast/heap/merge排序。

方案三：与方案一类似，但是hash做好后分多个文件，可以交给多个文件处理，使用分布式架构（如MapReduce）进行处理，最后合并。

给定两个文件a和b，每个文件存储50亿个url，每个url占用64字节，内存限制为4G，让你找出文件a和b的共同url？

可以估算出每个文件的大小为5G×64=320G，远大于内存限制的4G。 所以不可能将其完全加载到内存中进行处理。 考虑采取分而治之的方法。

如果允许一定的错误率，可以使用Bloom filter，4G内存可以表示大约340亿比特。 使用Bloom filter将其中一个文件中的url映射到这340亿位，然后将另一个文件的url一个一个读取，检查是否匹配Bloom filter。 如果是这样，该url应该是一个普通的url（注意会有一些错误率）。 “

如何在海量数据中找到重复次数最多的？

解决方法：先做hash，然后求模映射到小文件，找到每个小文件中重复次数最多的，记录重复次数。 然后在上一步得到的数据中找出重复次数最多的就是你要找的那个（详见上一题）。

几千万或者几亿条数据（有重复），统计出现次数最多的前N条数据？

解决方案：当前机器的内存应该可以存储几千万或者几亿的数据。 所以可以考虑使用hash_map/search binary tree/red-black tree等来统计次数。 然后使用堆取最常出现的前N个数据。

一个文本文件大约有10000行，每行一个词，要求统计出现次数最多的前10个词。 请给出思路和时间复杂度分析？

方案一：如果文件太大，一次性读入内存，可以使用哈希取模的方法，将大文件分解成多个小文件。 对于单个小文件，使用hash_map统计每个小文件中最常见的10个文件。 然后合并出现的单词以找到最后 10 个最常出现的单词。

方案二：将大文件通过hash取模分解成多个小文件后，除了用hash_map统计每个小文件中出现频率最高的10个词外，还可以使用trie树统计每个词出现的次数. 时间复杂度为O(nle)（le表示词的平均长度），最后也找到出现次数最多的前10个词（可以用堆实现），时间复杂度为O(nlg10 ).

一个文本文件，找到频繁出现的前10个词，但是这次文件比较长，说几亿或者十亿行，总之不能一次性读入内存，请问最优解？

解法一：首先，根据hash和取模将文件分解成多个小文件，用上题的方法对单个文件找出每个文件中出现频率最高的10个词。 然后合并处理，找出最后出现频率最高的10个词。

找出100w个数中最大的100个数？

方案一：使用局部淘汰法。 选取前100个元素排序，记录为序列L。然后将剩余元素x扫描一次，与100个排序元素中最小的元素进行比较。 如果大于最小元素，则删除最小元素，利用L中插入排序的思想将x插入到序列中。依次循环，直到扫描完所有元素。 复杂度为 O(100w*100)。

方案二：利用快速排序的思路，每次划分后只考虑比轴大的部分，当比轴大的部分超过100时，用传统的排序算法排序，取前100。复杂度为 O(100w*100)。

解法三：在上一题中，我们已经提到用一个包含100个元素的最小堆来完成。 复杂度为 O(100w*lg100)。

找到 5 亿个整数的中位数？

这个例子比上面那个更明显。 首先我们把int分成2^16个区域，然后读取数据统计落入每个区域的数有多少。 那么我们就可以根据统计结果判断这个中位数属于哪个区域，就知道这个区域有多少个。 几个大数字恰好是中位数。 然后在第二次扫描中，我们只统计那些落在这个区域的数字。

其实如果不是int而是int64，经过3次这样的划分，我们就可以把它降到可以接受的程度。 即可以先把int64分成224个区，然后确定区内最大的数，再把区分成220个子区，再确定子区内最大的数，再确定区内的数个数分区只有2^20，可以直接使用direct addr table进行统计。

它还需要计算两次。 如果数据存储在硬盘上，则需要读取两次。

该方法有点类似于基数排序。 打开一个大小为65536的Int数组，第一次读取，统计Int32的高16位，即0-65535，全部计为0，65536-131071计为1。相当于将数除以65536，Int32除以65536的结果不会超过65536种情况，所以只需要开一个长度为65536的数组来统计即可。 每读取一个数，数组中对应的计数+1。 考虑到负数的情况，需要将结果加上32768，记录到对应的数组中。

第一轮统计完后，遍历数组，逐个累加统计，看中位数在哪个区间，比如在区间k，那么区间0-k-1的数个数之和应该在2.5亿个整数中找到没有重复的整数，注意，内存是不够放这2.5亿个整数的。 给定40亿个未排序的非重复unsigned int整数，再给一个数，如何快速判断这个数是否在这40亿个数中？

使用位图/Bitmap方式申请512M内存，一位代表一个unsigned int值。 读入40亿个数，设置对应位，读入要查询的数，查看对应位是否为1，为1表示存在，为0表示不存在.

7.5 加密算法 什么是摘要算法？ 什么？

消息摘要算法的主要特点是加密过程不需要密钥，加密后的数据无法解密。 目前只有CRC32算法可以解密和逆向。 只有通过相同的消息摘要算法输入相同的明文数据，才能得到相同的密文。 . 消息摘要算法不存在密钥管理和分发的问题，适用于分布式网络。 消息摘要算法主要用于“数字签名”领域，作为明文的摘要算法。

数字签名主要采用非对称密钥加密技术和数字抽象技术。 数字签名技术是用发送方的私钥对摘要信息进行加密，与原文一起传送给接收方。 接收方只能用发送方的公钥对加密后的摘要信息进行解密，然后利用HASH函数对接收到的原文生成摘要信息，并与解密后的摘要信息进行比较。 如果相同，说明接收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改了。

因此，数字签名可以验证信息的完整性。

数字签名是一个加密过程，而数字签名验证是一个解密过程。

著名的摘要算法包括RSA的MD5算法和SHA-1算法以及大量的变种

什么是加密算法？ 什么？

数据加密的基本过程是将原始的明文文件或数据按照一定的算法进行处理，使其成为一段不可读的代码，称为“密文”，只有输入相应的密钥后才能显示出原文。 这样就达到了保护数据不被不法分子窃取和读取的目的。 此过程的逆过程是解密，将编码信息转换为其原始数据的过程。

加密算法分类

密钥加密技术的密码体系分为对称密钥体系和非对称密钥体系两种。 相应地，数据加密技术分为两类，即对称加密（私钥加密）和非对称加密（公钥加密）。

对称加密一般以数据加密标准（DES，Data Encryption Standard）算法为代表，非对称加密一般以RSA（Rivest Shamir Adleman）算法为代表。

对称加密的加密密钥和解密密钥相同，非对称加密的加密密钥和解密密钥不同。 加密密钥可以公开，而解密密钥需要保密。

什么是国密算法？ 什么？