1. 1G 的文件，每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M，返回频数最高的 100 个词。

使用生成器读取文件。每次读取 65536 行，一共进行 1500 次，当读取不到内容时关闭文件。每

次读取，最终要得到 100 个频数最高的词。每 500 次，进行一次合并和统计，得到最多 50000 个

词，对这 50000 个词提取其中频数最高的 100 个词。最终对最多 300 个筛选出来的词，进行合并

和统计，提取最终频数最高的 100 个词。

筛选出 100 个高频词的步骤：

1、统计每个词出现的次数。维护一个 Key 为词，Value 为该词出现次数的 hash 表。每次读取一个词，如果该字串不在 hash 表中，那么加入该词，并且将 Value 值设为 1；如果该字串在 hash 表中，那么将该字串的计数加一即可。

2、据每个词的引用次数进行排序。冒泡、快排等等都可以。

 

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

用 trie 树统计每个词出现的次数，时间复杂度是 O(n*le)(le 表示单词的平均长度)。然后是找出出现最频繁的前 10 个词，可以用堆来实现，时间复杂度是 O(n*lg10)。所以总的时间复杂度，是 O(n*le) 与 O(n*lg10)中较大的哪一个。

详情扫描二维码了解。http://www.mamicode.com/info-detail-1037262.html

 

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

算法思想：

先做 hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求。

参考博客一：

https://blog.csdn.net/u010601183/article/details/56481868

参考博客二：

https://www.cnblogs.com/lianghe01/p/4391804.html

 

4. 给 2 亿个不重复的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 2 亿个数当中？

unsigned int 的取值范围是 0 到 2^32-1。我们可以申请连续的 2^32/8=512M 的内存，用每一个 bit 对应一个 unsigned int 数字。首先将 512M 内存都初始化为 0，然后每处理一个数字就将其对应的 bit 设置为 1。当需要查询时，直接找到对应 bit，看其值是 0 还是 1 即可。

 

5. 算法的特征？

1） 有穷性： 一个算法必须保证执行有限步骤之后结束；

2） 确切性： 算法的每一步骤必须有确切的定义；

3） 输入：一个算法有 0 个或多个输入，以刻画运算对象的初始情况，所谓 0 个输入是指算法本身给出了初始条件；

4） 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5） 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次数运算后即可完成。

 

6. 冒泡排序的思想？

冒泡思想：通过无序区中相邻记录的关键字间的比较和位置的交换，使关键字最小的记录像气泡一样逐渐向上漂至水面。整个算法是从最下面的记录开始，对每两个相邻的关键字进行比较，把关键字较小的记录放到关键字较大的记录的上面，经过一趟排序后，关键字最小的记录到达最上面，接着再在剩下的记录中找关键字次小的记录，把它放在第二个位置上，依次类推，一直到所有记录有序为止

复杂度：时间复杂度为 O（n2）,空间复杂度为 O(1)

 

7. 快速排序的思想？

快排的基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

复杂度：快速排序是不稳定的排序算法，最坏的时间复杂度是 O（n2）,最好的时间复杂度是(nlogn), 空间复杂度为 O(logn)

 

8. 如何判断单向链表中是否有环？

首先遍历链表，寻找是否有相同地址，借此判断链表中是否有环。如果程序进入死循环，则需要一块空间来存储指针，遍历新指针时将其和储存的旧指针比对，若有相同指针，则该链表有环，否则将这个新指针存下来后继续往下读取，直到遇见 NULL，这说明这个链表无环。

 

9. 基础的数据结构有哪些？

基本的算法有: 排序算法(冒泡排序，插入排序，快速排序，归并排序)，查找(二分查找)，搜索（（DFS）深度优先搜索，（BFS）广度优先搜索)，（Dijkstra 算法），动态规划算法，分类（朴素贝叶斯分类算法等）。

评价算法的好坏一般有两种: 时间复杂度和空间复杂度。时间复杂度：同样的输入规模(问题规模)花费多少时间。 空间复杂度：同样的输入规模花费多少空间(主要是内存)。以上两点越小越好。

稳定性：不会因为输入的不同而导致不稳定的情况发生。算法的思路是否简单：越简单越容易实现的越好。

 

10. 基本的算法有哪些，怎么评价一个算法的好坏？

基本的算法有: 排序算法(简单排序， 快速排序， 归并排序)， 搜索(二分搜索)， 对于其他基本数据结构， 栈， 队列，树，都有一些基本的操作。

稳定性：不会引文输入的不同而导致不稳定的情况发生。算法的思路是否简单：越简单越容易实现的越好。

 

11. 哪种数据结构可以实现递归？

栈可以实现，递归需要保存正在计算的上下文， 等待当前计算完成后弹出，再继续计算， 只有栈先进后出的特性才能实现。

 

12. 你知道哪些排序算法（一般是通过问题考算法）

冒泡， 选择， 快排， 归并。

 

13. 斐波那契数列

斐波那契数列：简单地说，起始两项为 0 和 1，此后的项分别为它的前两项之和。

 

14. 二叉树如何求两个叶节点的最近公共祖先？

二叉树是搜索二叉树 ：

1、原理：二叉搜索树是排序过的 ，位于左子树的结点都比父结点小，位

于右子树的结点都比父结点大，我们只需从根节点开始和两个输入的结点进行比较，如果当前节点的值比两个结点的值都大，那么最低的公共祖先结点一定在该结点的左子树中，下一步开遍历当前结点的左子树。如果当前节点的值比两个结点的值都小，那么最低的公共祖先结点一定在该结点的右子树中，下一步开遍历当前结点的右子树。这样从上到下找到第一个在两个输入结点的值之间的结点。

 

15. 找出二叉树中最远结点的距离？

计算一个二叉树的最大距离有两个情况。

情况 A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。情况 B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。

 

16. set 用 in 时间复杂度是多少，为什么？

O(1)，因为 set 是键值相同的一个数据结构，键做了 hash 处理。

 

17. 深度优先遍历和广度优先遍历的区别？

1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。

2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：

先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

3） 深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。

广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。通常，深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库

中存储的结点数就是深度值，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。

广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此， 程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。

 

18. 求和问题，给定一个数组，数组中的元素唯一，数组元素数量 N >2，若数组中的两个数相加和为 m，则认为该数对满足要求，请思考如何返回所有满足要求的数对（要求去重），并给出该算法的计算复杂度和空间复杂度

时间复杂度 O(n^2) 空间复杂度 O(n)。

 

19. 桶排序（最快最简单的排序）

桶排序的基本思想是将一个数据表分割成许多 buckets，然后每个 bucket 各自排序，或用不同的排序算法，或者递归的使用 bucket sort 算法。也是典型的 divide-and-conquer 分而治之的策略。它是一个分布式的排序，介于 MSD 基数排序和 LSD 基数排序之间。

1、桶排序是稳定的

2、桶排序是常见排序里最快的一种， 大多数情况下比快排还要快

3、桶排序非常快，但是同时也非常耗空间，基本上是最耗空间的一种排序算法

 

20. 青蛙跳台阶问题

一只青蛙要跳上 n 层高的台阶，一次能跳一级，也可以跳两级，请问这只青蛙有多少种跳上这个 n 层高台阶的方法？

思路分析：

这个问题有三种方法来解决，并在下面给出三处方法的 python 实现。

方法 一:递归

设青蛙跳上 n 级台阶有 f(n)种方法，把这 n 种方法分为两大类，第一种最后一次跳了一级台阶，这类方法共有 f(n-1)种，第二种最后一次跳了两级台阶，这种方法共有 f(n-2)种，则得出递推公式f(n)=f(n-1)+f(n-2)，显然，f(1)=1，f(2)=2，递推公式如下：

方法 二: 用循环来代替递归

这种方法的原理仍然基于上面的公式，但是用循环代替了递归，比上面的代码效率上有较大的提升， 可以 AC。

代码实现如下：

方法三：建立简单数学模型，利用组合数公式

设青蛙跳上这 n 级台阶一共跳了 z 次，其中有 x 次是一次跳了两级，y 次是一次跳了一级，则有z=x+y ，2x+y=n，对一个固定的 x，利用组合可求出跳上这 n 级台阶的方法共有种方法又因为 x 在区间[0，n/2]内，所以我们只需要遍历这个区间内所有的整数，求出每个 x 对应的组合数累加到最后的结果即可。

 

21. 删除排序数组中的重复数字 Remove Duplicates from Sorted Array

给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回 新的数组的长度。 不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。

样例：

给出数组 A =[1,1,2]，你的函数应该返回长度 2，此时 A=[1,2]。

分析：遍历，跳过重复元素。时间复杂度 O(n)。

思考：其他条件不变，如果可以允许出现两次重复将如何处理？ 样例：

给出数组 nums = [1,1,1,2,2,3]。

你的函数应当返回长度 length = 5, 且前 5 个元素分别为 1, 1, 2, 2 and 3。

 

22. 两数之和 Two Sum

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数 twoSum 需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。

样例：

给 出 numbers = [2, 7, 11, 15], target = 9, 返 回 [1, 2]. 分析：

给定一个数列（注意不一定有序），和一个指定的数值 target。从这个数列中找出两个数相加刚好等于 target，要求给出这两个数的下标（注意数列下标是从 1 而不是从 0 开始）。

首先将数列排序。由于最后要得求的是两个数的原有下标，而不是两个数本身，因此要用一个新的对象 Item 来封装原有数列元素，并记录该元素的原有下标。排序是针对数列元素本身数值的，分别用一个index1 指针和一个index2 指针指向排序后的数列的首位，如果指向的两个数相加的和等于target， 则搜索结束；如果和小于 target，则由于 index2 此时指向的已经是数组中的最大数了，因此只能令

index1 向右移动一次；如果和大于 target，则由于此时 index1 已经指向数组中的最小数了，因此只能令 index2 向左移动一次。用一个循环重复上述过程，直到和等于 target 宣告搜索成功，或者

index1>=index2 宣告搜索失败。

空间复杂度 O(n)，因为构造了一个新的 Item 序列。时间复杂度方面，如果假设 Python 的 sort 算法是用的快速排序的话，那排序的时间复杂度为 O(n*logn)，搜索过程的时间复杂度为 O(n)，因此总的时间复杂度为 O(n*logn)。

注意给的数列也许长度为 0，这样无论 target 是多少都是搜索失败。而且题目中给的 example 明显是是在误导人，不仔细看误以为数列原本就有序。此外，数列下标是从 1 而不是从 0 开始的。

 

23. 删除元素 Remove Element

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。元素的顺序可以改变， 并且对新的数组不会有影响。

样例：

给出一个数组 [0,4,4,0,0,2,4,4]，和值 4

返回 4 并且 4 个元素的新数组为[0,0,0,2] 分析：

题目已经暗示可以将需要删除的元素移至数组末尾，因此用两个下标 m 和 n，m 用来从左至右遍历数组寻找该元素，n 从右至左记录可以用来交换的尾部位置。

 

24. 加一 Plus One

给一个由包含一串数字的列表组成的非负整数加上一。

注意点：列表前面的数字表示高位 ，注意最高位也可能进位。例子：

输入: [1, 2, 3, 4, 9]

输出: [1, 2, 3, 5, 0]

解题思路：

用一个 int 数组代表一个数值，最左边是最高位，现要求加上 1，同样地返回一个 int 数组代表计算结果。非常简单的模拟加法，注意进位问题，如果是 99，999 这种，最后加上 1 后还要在数组最左边插入一个元素 1。

 

25. 用两个队列如何实现一个栈，用两个栈如何实现一个队列？

两个栈实现一个队列：

栈的特性是先进后出（FILO），队列的特性是先进先出（FIFO），在实现 delete 时，将一个栈中的数据依次拿出来压入到另一个为空的栈，另一个栈中数据的顺序恰好是先压入栈 1 的元素此时在栈

2 的上面，为了实现效率的提升，在 delete 时，判断栈 2 是否有数据，如果有的话，直接删除栈顶元素，在栈 2 为空时才将栈 1 的数据压入到栈 2 中，从而提高程序的运行效率，实现过程可以分为下面几个步骤：

1、push 操作时，一直将数据压入到栈 2 中

2、delete 操作时，首先判断栈 2 是否为空，不为空的情况直接删除栈 2 栈顶元素，为空的话

将栈 1 的数据压入到栈 2 中，再将栈 2 栈顶元素删除。两个队列实现一个栈 ：

因为队列是先进先出，所以要拿到队列中最后压入的数据，只能每次将队列中数据 pop 到只剩一个，此时这个数据为最后压入队列的数据，在每次 pop 时，将数据压入到另一个队列中。每次执行 delete 操作时，循环往复。

 

26. 爬楼梯 Climbing Stairs

假设你正在爬楼梯，需要 n 步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例：

比如 n=3，1+1+1=1+2=2+1=3，共有 3 中不同的方法

返 回 3 解题思路：

如果按照从右至左的逆序递归求解，其实就相当于搜索算法了，会造成子搜索过程的重复计算。搜索算法一般都可以用动态规划来替代，因此这里就用 1D 动态规划。

然后可以发现，f(x)的求解只依赖于 f(x-1)和 f(x-2)，因此可以将空间复杂度缩小到 int[3]。于是你就会发现，这其实就是一个裴波拉契数列问题。

 

27. 落单的数Single Number

给出 2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。样例：

给出 [1,2,2,1,3,4,3]，返回 4。

解题思路：

异或操作，知道的人立马能做出来，不知道的人想破脑袋也想不出这个方法。当然用 hashmap/map 之类的把所有元素插一遍也能找出这个只出现过一次的元素，但是想必面试官不会很开心。位操作还是有很多技巧的，还需要继续深入学习。

 

28. 搜索旋转排序数组 Search in Rotated Sorted Array

假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为 4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。

你可以假设数组中不存在重复的元素。样例：

给出[4, 5, 1, 2, 3]和 target=1，返回 2

给出[4, 5, 1, 2, 3]和 target=0，返回 -1 解题思路：

采用了二分搜索，不过旋转后的数组要讨论的情况增多了。其实旋转后的数组的大小关系一般如下图：先通过中点与左顶点的关系来分类讨论中点落在了哪一部分，如果在左半边，则继续讨论目标数在中点的左边还是右边；如果在右半边，同样讨论目标数的位置。同时需要注意特殊情况只剩下两个数时， 例如[3,1]，这时求出的中点也是 3，如果中点不匹配，应考虑 1。这种情况不好与上面的情况合并，单独列出。

思考：

其他条件不变，假如有重复元素又将如何？是否会影响运行时间复杂度？如何影响？为何会影响？ 写出一个函数判断给定的目标值是否出现在数组中。

样例：

给出[3,4,4,5,7,0,1,2]和 target=4，返回 true。

 

29. 三数之和 3Sum

给出一个有 n 个整数的数组 S，在 S 中找到三个整数 a, b, c，找到所有使得 a + b + c = 0 的三元组。

注意事项：在三元组(a, b, c)，要求 a <= b <= c，结果不能包含重复的三元组。样例：

如 S = {-1 0 1 2 -1 -4}, 你需要返回的三元组集合的是：

(-1, 0, 1)、(-1, -1, 2)

解题思路：

求一个列表中所有和为零的二元组的一种思路是先把列表排序，再用两个指针从两头向中间移动。如果前后两个数的和小于 0，则左指针右移；如果和大于 0，则右指针左移。求三元组时可以参考这种做法，第一个数 a 确定后，可以理解为求列表中和为-a 的二元组。由于不要考虑重复的元组，遇到重复的数可以直接跳过。

 

30. 四数之和 4Sum

给一个包含 n 个数的整数数组 S，在 S 中找到所有使得和为给定整数 target 的四元组(a, b, c,d)。注意事项：

四元组(a, b, c, d)中，需要满足 a <= b <= c <= d。答案中不可以包含重复的四元组。

样例：

例如，对于给定的整数数组 S=[1, 0, -1, 0, -2, 2] 和 target=0. 满足要求的四元组集合为：

(-1, 0, 0, 1)

(-2, -1, 1, 2)

(-2, 0, 0, 2)

解题思路：

想参照之前的一题 3Sum 的解法来解决，结果超时了。换个思路，空间换时间。既然有四个数，那就把前两个数之和和后两个数之和分别当做一个数。现在要求的就是在一个列表中哪两个数的和为特定值。可以先遍历一遍列表，存值和它的下标的键值对，第二遍遍历列表寻找（目标值-当前值）是否在之前的键值对中，如果在就是符合的一组解。

 

31. 下一个排列Next Permutation

给定一个整数数组来表示排列，找出其之后的一个排列。

注意事项：排列中可能包含重复的整数。样例：

给出排列[1,3,2,3]，其下一个排列是[1,3,3,2]

给出排列[4,3,2,1]，其下一个排列是[1,2,3,4] 解题思路：

通过一个例子来说明，原数组为[1,7,3,4,1]。我们想要找到比 173421 大一点的数，那就要优先考虑

将后面的数字变换顺序，而 421 从后往前是升序的（也就是这三个数字能组成的最大的数），变换了反而会变小，所以要先找到降序的点。可以看出 3 是第一个降序的点，要想整个数变大，3 就要变大，从后往前找到第一个比 3 大的数 4，将 3 和 4 交换位置得到 174321，既然原来 3 所在位置的数字变大了，那整个数肯定变大了，而它之后的数是最大的（从后往前是升序的），应转换成最小的，直接翻转。

 

32. 第 K 个 排 列 Permutation Sequence

给定 n 和 k，求 123..n 组成的排列中的第 k 个排列。注意事项：1 ≤ n ≤ 9。

样例：

对于 n = 3, 所有的排列如下：

解题思路：

因为 n 个不同的数字可以组成 n!个序列，那么首位确定的序列都有(n-1)!种不同的可能性，而且这些序列都根据首位的大小进行了分组，1…是最小的(n-1)!个，2…是(n-1)!+1 到 2(n-1)!个，那么现在只需要计算 k 中有几个(n-1)!就可以确定首位的数字，同样可以通过这样的方法来确定第二位、第三位…… 此外，由于列表下标从 0 开始，所以 k 要减去 1。

 

33. 判断数独是否合法 Valid Sudoku

请判定一个数独是否有效。该数独可能只填充了部分数字，其中缺少的数字用 . 表示。注意事项：

一个合法的数独（仅部分填充）并不一定是可解的。我们仅需使填充的空格有效即可。说明：什么是 数独？（详细解释可以扫下面二维码连接）。

解题思路：

用三个列表表示横向、纵向和小正方形的情况。特别需要注意的是小正方形内的元素的表示方法：

board[i/3*3+j/3][i%3*3+j%3]。

 

34. 链表求和 Add Two Numbers

你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序， 使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。

样例：

输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)，返回 7 -> 0 -> 8。

解题思路：

把两个链表当成是相同长度的，短的那个想象成后面都是 0；如果进位的话，在初始化下一个节点的时候将其赋值为 1 即可，所以在计算当前节点的值时要加上自己本来的值。

 

35. 链表划分 Partition List

给定一个单链表和数值 x，划分链表使得所有小于 x 的节点排在大于等于 x 的节点之前。你应该保留两部分内链表节点原有的相对顺序。

解题思路：

看成有一串珠子，有红和蓝两种颜色，现在要把红色和蓝色分别集中到一起。可以遍历每个珠子， 如果是蓝色就串在一条线上，红色的串在另一条线上，最后把两条线连起来就可以了。注意，在比较大的那串数中，最后的指针要置为 None，因为那是排序后的最后一个节点。

 

36. 旋转链表

给定一个链表，旋转链表，使得每个节点向右移动 k 个位置，其中 k 是一个非负数。样例：

给出链表 1->2->3->4->5->null 和 k=2 返回 4->5->1->2->3->null

 

37. 两两交换链表中的节点

例子：

输入: head = 1->2->3->4 输出: 2->1->4->3

解题思路：

比较常见的链表操作。下面看一下典型情况，如要交换链表中 A->B->C->D 中的 B 和 C 需要做如下操作：

将 A 指向 C； 将 B 指向 D； 将 C 指向 B；

在头节点之前加一个假节点就可以使所有的交换都符合上面的情况。

 

38. 重排链表

解题思路：

由于是一个单向链表，从尾部不断取元素比较困难，所以我们要将链表反转，又因为是同时从两头取元素，所以我们只需要反转后半段链表。我们先通过快慢指针来获得链表的中间节点，并将链表截断。接着翻转后半段链表，最后依次从两个链表中提取元素进行连接。需要注意的是，在截断时注意哪个链表比较长，合并的时候不要遗漏元素。