最长公共子串
跳台阶n阶
这是一个经典的动态规划问题，可以理解为斐波那契数列的应用。假设每次你可以跳1阶或者2阶，那么到达第n阶的方法有两种情况，一种是从第n-1阶跳上来，另一种是从第n-2阶跳上来。所以到达第n阶的方法就是到达第n-1阶的方法和到达第n-2阶的方法的和。
int climb_stairs(int n) { int dp[n + 1]; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int i = 3; i < n + 1; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }请解释什么是 C10K 问题或者知道什么是 C10K 问题吗？
1亿个数中找10k个最大的。最小堆实现，考虑内存大小问题，不能一次全部将数据读入内存
Top K问题（可以采取的方法有哪些，各自优点？）（重点）
Top K 问题的常见形式：
- 给定10000个整数，找第K大（第K小）的数
- 给定10000个整数，找出最大（最小）的前K个数
- 给定100000个单词，求前K词频的单词
解决Top K问题若干种方法
- 使用最大最小堆。求最大的数用最小堆，求最小的数用最大堆。
- Quick Select算法。使用类似快排的思路，根据pivot划分数组。
- 使用排序方法，排序后再寻找top K元素。
- 使用选择排序的思想，对前K个元素部分排序。
- 将1000…个数分成m组，每组寻找top K个数，得到m×K个数，在这m×k个数里面找top K个数。
- 使用最大最小堆的思路 （以top K 最大元素为例）
按顺序扫描这10000个数，先取出K个元素构建一个大小为K的最小堆。每扫描到一个元素，如果这个元素大于堆顶的元素（这个堆最小的一个数），就放入堆中，并删除堆顶的元素，同时整理堆。如果这个元素小于堆顶的元素，就直接pass。最后堆中剩下的元素就是最大的前Top K个元素，最右的叶节点就是Top 第K大的元素。
note：最小堆的插入时间复杂度为log(n)，n为堆中元素个数，在这里是K。最小堆的初始化时间复杂度是nlog(n)C++中的最大最小堆要用标准库的priority_queue来实现。
struct Node { int value; int idx; Node (int v, int i): value(v), idx(i) {} friend bool operator < (const struct Node &n1, const struct Node &n2) ; }; inline bool operator < (const struct Node &n1, const struct Node &n2) { return n1.value < n2.value; } priority_queue<Node> pq; // 此时pq为最大堆使用Quick Select的思路（以寻找第K大的元素为例）
Quick Select脱胎于快速排序，提出这两个算法的都是同一个人。算法的过程是这样的：
首先选取一个枢轴，然后将数组中小于该枢轴的数放到左边，大于该枢轴的数放到右边。
此时，如果左边的数组中的元素个数大于等于K，则第K大的数肯定在左边数组中，继续对左边数组执行相同操作；
如果左边的数组元素个数等于K-1，则第K大的数就是pivot；
如果左边的数组元素个数小于K，则第K大的数肯定在右边数组中，对右边数组执行相同操作。
这个算法与快排最大的区别是，每次划分后只处理左半边或者右半边，而快排在划分后对左右半边都继续排序。//此为Java实现 public int findKthLargest(int[] nums, int k) { return quickSelect(nums, k, 0, nums.length - 1); } // quick select to find the kth-largest element public int quickSelect(int[] arr, int k, int left, int right) { if (left == right) return arr[right]; int index = partition(arr, left, right); if (index - left + 1 > k) return quickSelect(arr, k, left, index - 1); else if (index - left + 1 == k) return arr[index]; else return quickSelect(arr, k - (index - left + 1), index + 1, right); }使用选择排序的思想对前K个元素排序 （ 以寻找前K大个元素为例）
扫描一遍数组，选出最大的一个元素，然后再扫描一遍数组，找出第二大的元素，再扫描一遍数组，找出第三大的元素。。。。。以此类推，找K个元素，时间复杂度为O(N*K)
设计一个定时器
实现一个LRU算法
哈希+双向链表
8G的int型数据，计算机的内存只有2G，怎么对它进行排序？（外部排序）
我们可以使用外部排序来对它进行处理。首先将整个文件分成许多份，比如说m份，划分的依据就是使得每一份的大小都能放到内存里。然后我们用快速排序或者堆排序等方法对每一份数据进行一个内部排序，变成有序子串。接着对这m份有序子串进行m路归并排序。取这m份数据的最小元素，进行排序，输出排序后最小的元素到结果中，同时从该元素所在子串中读入一个元素，直到所有数据都被输出到结果中为止。
不使用临时变量实现swap函数
```c void swap(int& a,int& b){ a=a^b; b=a^b; a=a^b; } ```
其他算法题
升序的数组中寻找是否有两个数相加为给定值？
八个字母共有多少组合？每个字母可以使用多次，但类似abb,bba算一种
僵尸吃人问题，僵尸吃人后变成人，一个人能够被两个僵尸吃，人被吃后牺牲。问最后多少人存活。
斐波那契数列的非递归写法？
一个整数数组，可能是降序或升序，也可能是先升序再降序，求最大值？
单链表，求中部的N个节点的头节点和尾节点
非递归求二叉树的高度
100本书，两个人轮流拿，每次拿1~5本，你先拿，有没有啥策略可以保证你可以拿到最后一本？
N个M长度数组求交集，求最优解并给出时间复杂度和空间复杂度
两个红球一个白球，三个盒子。问第二个盒子至少一个红球的概率
编程题，字符串去空格
实现字符串反转，以逗号作为切割符，切割的子串以单词作为单元反转。输入：hello world, god bless you。输出：world hello, you bless god
一个1~9组成的字符串，相邻和为10的可消除，求最后长度
30个中文关键词，一篇文本文档，统计文本文档中出现这中文关键词的次数
掰巧克力问题 NM块巧克力，每次掰一块的一行或一列，掰成11的巧克力需要多少次？（1000个人参加辩论赛，1V1，输了就退出，需要安排多少场比赛）
每次拿起一块巧克力，掰一下（无论横着还是竖着）都会变成两块，因为所有的巧克力共有NM块，所以要掰NM-1次，减1是因为最开始的一块是不用算进去的。
烧 香/绳子/其他 确定时间问题：有两根不均匀的香，燃烧完都需要一个小时，问怎么确定15分钟的时长？
（说了求15分钟，没说开始的15分钟还是结束的15分钟，这里是可以求最后的15分钟）点燃一根A，同时点燃另一根B的两端，当另一根B烧完的时候就是半小时，这是再将A的另一端也点燃，从这时到A燃烧完就正好15分钟
赛马：有25匹马，每场比赛只能赛5匹，至少要赛多少场才能找到最快的3匹马？
第一次，分成5个赛道ABCDE，每个赛道5匹马，每个赛道比赛一场，每个赛道的第12345名记为 A1,A2,A3,A4,A5 B1,B2,B3,B4,B5等等，这一步要赛5场。
第二次，我们将每个赛道的前三名，共15匹。分成三组，然后每组进行比赛。这一步要赛3场。
第三次，我们取每组的前三名。共9匹，第一名赛道的马编号为1a,1b,1c，第二名赛道的马编号为2a,2b,2c，第三名赛道的马编号为3a,3b,3c。这时进行分析，1a表示第一名里面的第一名，绝对是所有马中的第一，所以不用再比了。2c表示第二名的三匹里头的最后一匹，3b和3c表示第三名里面的倒数两匹，不可能是所有马里面的前三名，所以也直接排除，剩下1b,1c,2a,2b,3a，共5匹，再赛跑一次取第一第二名，加上刚筛选出来的1a就是所有马里面的最快3匹了。这一步要赛1场。生成随机数问题：给定生成1到5的随机数Rand5()，如何得到生成1到7的随机数函数Rand7()？
思路：由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。
记住下面这个式子：RandNN= N( RandN()-1 ) + RandN() ;// 生成1到N^2之间的随机数
可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度，RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙比如Rand25= 5( Rand5()-1 ) + Rand5()可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写
int rand7(){ int x=INT_MAX; while(x>21){ x=5*(rand5()-1)+rand5(); } return x%7+1; }有十组砝码每组十个，每个砝码重10g，其中一组每个只有9g，有能显示克数的秤最少几次能找到轻的那一组砝码？
砝码分组1~10，第一组拿一个，第二组拿两个以此类推。。第十组拿十个放到秤上称出克数x，则y = 550 - x，第y组就是轻的那组
å有一个天平，九个砝码，一个轻一些，用天平至少几次能找到轻的？
至少2次：第一次，一边3个，哪边轻就在哪边，一样重就是剩余的3个；
第二次，一边1个，哪边轻就是哪个，一样重就是剩余的那个；在24小时里面时针分针秒针可以重合几次
24小时中时针走2圈，而分针走24圈，时针和分针重合24-2=22次，而只要时针和分针重合，秒针一定有机会重合，所以总共重合22次
瓶子换饮料问题：1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶
拿走3瓶，换回1瓶，相当于减少2瓶。但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.（1000-4=996，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是1000+498+1=1499瓶。
放n只蚂蚁在一条树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问总距离或者时间。
碰到就当没发生，继续走，相当于碰到的两个蚂蚁交换了一下身体。其实就是每个蚂蚁从当前位置一直走直到停止的总距离或者时间。
先手必胜策略问题：100本书，每次能够拿1-5本，怎么拿能保证最后一次是你拿
寻找每个回合固定的拿取模式。最后一次是我拿，那么上个回合最少剩下6本。那么只要保持每个回合结束后都剩下6的倍数，并且在这个回合中我拿的和对方拿的加起来为6（这样这个回合结束后剩下的还是6的倍数），就必胜。关键是第一次我必须先手拿（100%6=4）本（这不算在第一回合里面）。
毒药问题，1000瓶水，其中有一瓶可以无限稀释的毒药，要快速找出哪一瓶有毒，需要几只小白鼠
用二进制的思路解决问题。2的十次方是1024，使用十只小鼠喝一次即可。方法是先将每瓶水编号，同时10个小鼠分别表示二进制中的一个位。将每瓶水混合到水瓶编号中二进制为1的小鼠对应的水中。喝完后统计，将死亡小鼠对应的位置为1，没死的置为0，根据死亡小鼠的编号确定有毒的是哪瓶水，如0000001010表示10号水有毒。
100层楼，只有2个鸡蛋，想要判断出那一层刚好让鸡蛋碎掉，给出策略（滴滴笔试中两个铁球跟这个是一类题）
（给定了楼层数和鸡蛋数的情况）二分法+线性查找 从100/2=50楼扔起，如果破了就用另一个从0扔起直到破。如果没破就从50/2=25楼扔起，重复。
N个骰子出现和为m的概率
两个字符串s和p判断p是否是s的子序列
实现一个队列，并且使它支持多线程，队列有什么应用场景
50个人排队衣服号码1-50，一共50个位置，一开始是按顺序排列的，每次单数位置的人出队，后面的人补上去，多少次之后只剩下一个人，那个人衣服号码是啥，50变成n总结一个公式
编程题：版本号比较，版本号类似ip地址就是由.分隔的数字，看那个版本号大，后缀0可以不计eg：2.2.0.0.00和2.2是一样的，9.1大于8.9.9.9.9
地图最近点更新