挺感谢面试官了，问了我将近50分钟，自己也更加了解自己欠缺什么了。

1 C++多态如何实现

? ? 常规套路，这个很基础就不说了。

2 把析构函数声明为虚函数的作用，和实现的原理

? ? 自己没懂实现原理应该怎么回答，回来后想了想，应该按照多态的思路去回答，子类重写了父类的析构函数，那么在调用到析构函数的时候就会发生多态，从而调用子类的析构函数，再调用父类的析构函数。先子类析构再父类析构是C++标准的规定，实现原理自己没有搜到，但这么做的原因很好找。

3 C++中static关键字总结

? ? 类外：

????? ? 静态全局变量：文件之外不可见

????? ? 静态局部变量：

????????????? ? 1 存在全局区，程序运行期间始终存在。

????????????? ? 2 只初始化1次。

????????????? ? 3 作用域是局部的。

????? ? 修饰函数：文件之外不可见

? ? 类中

????? ? 修饰成员变量：

????????????? ? 1 所有对象共享一个数据，没有创建对象已经存在。

????????????? ? 2 在类外初始化

????????????? ? 3 优势：有访问权限控制，不在全局变量的名字空间中

????? ? 修饰成员函数

????????????? ? 1 没有this指针，只能使用静态成员变量

? ? 普通成员函数可以使用静态成员变量和静态成员函数。

一个很好的总结链接送给大家：

https://www.cnblogs.com/BeyondAnyTime/archive/2012/06/08/2542315.html

4 概率题，54张扑克牌，连摸三张，花色相同的概率

? ? 考虑大小王，应该是52/54 * 12/53 * 11/52?

5 outptr了解过吗？

? ? 下来之后百度都搜不到。

6 在数组n中找第k大的数，怎么找？

? ? 最蠢的肯定是对所有数据快排或归并O(NlogN)。自己知道这个题最快肯定是O(N)但是当时紧张，没能仔细思考。

? ? 再者就是冒泡k次，能把前k大的数全部找出来，O(kN)。

? ? 下来之后又搜了一下，看了别人的思路：

? ? 1 利用快排

????? ? random()一个数做pv值，大于pv放右边（n个），小于pv放左边（m个）。

????? ? 比较m和k的大小

????????? ? m<k, 把右边的n个数再选pv值，做排序，比较new_m和(k-m)的关系，递归。

????????? ? m>k, 把左边的m个数再选pv值，做排序，比较new_m和k的关系，递归。

????? ? 据说时间复杂度是O(N*logk)，怎么证明我就不知道了。

????? ? 自己后来想了想，貌似用这个方法复杂度应该是O(N)：

????????? ? 首先，如果使用快排找第k大的数，那么时间复杂度肯定和k无关的，再者有aT(n/b)+O(n^d)这个公式：子问题的重复次数是1，因为只选择一侧继续选pv值做划分，子问题的规模是一个概率值，应该是1/2，b为2，d应该是1，这就是每次划分需要遍历数组。那么logba = 0 < d -->O(logN)

https://blog.csdn.net/wangbaochu/article/details/52949443

7 问了哈希实现的方法有哪些，解决哈希冲突的方法有哪些。

? ? 基础题。

后面就开始魔幻问题了，毕竟自己没有做过项目，答题基本全靠想象

8 qq用户ID是32位的整数，现在要你存储所有用户的状态，状态仅有在线和不在线两种，日均在线用户数量大约2亿。

? ? 完全不知道怎么去思考，自己知道的所有和大数据相关的基本就只有堆排序和布隆过滤器了，一时脑抽就问是不是布隆过滤器，面试官微笑说那你就讲讲吧，可是自己对布隆过滤器也只是了解，从来没用过，面试官等我说完就问我，那你数据怎么删除。然后就投降了。

? ? 自己下来之后看了看，应该是bitmap吧，因为只有两种状态，所以1bit就可以表示一个用户的状态，对于40亿的用户量，需要 5亿字节的内存，就是2^29，500MB吧。目前只能这样了。

9 领导让你给微信抢红包增加一个限制功能：每个用户每分钟最多抢5个，问每个用户的数据结构什么样，用什么结构存储，怎么避免内存的浪费。

? ? 自己从来没遇到过，一开始连1分钟怎么确定都不知道，居然回答了timer()定时器和中断函数，面试官哈哈大笑...毕竟自己做硬件的，思维还是转变不过来，后面一想，额，sys_time可以查的，那果断加一个时间戳额。所以每个用户的数据就是

char num; 表示抢了多少次红包。

sys_time; 存放系统时间。

int User_ID;

后面自己慌慌张张，乱说一通，最后答道了用map存放数据，key是User_ID。

逻辑是第一次抢红包的时候（map中没有）就记录一个sys_time()，然后num++。

再抢红包的时候查找到用户ID对应的节点，然后比较sys_time()是否到了5分钟，如果到了，那么num=0，如果没到，num!=5，还可以抢，num++，如果num==5那么不能抢。

然后面试官问那么过期的数据如何删除呢，然后就懵逼了。

自己下来后想了想，或许可以用hash+map的方法。维护60个map，新增的参加抢红包的用户数据轮流存储在map中，根据sys_time()%60，决定存储在哪一个map，然后每隔一秒就clear()一个map。

举例：

在sys_time() == 7.00秒的时候（具体可能用定时器实现吧），清空7号map的所有数据。

在sys_time()==7.20秒的时候，有一个用户抢红包了，那么，就在0-59号map中找，如果找到了，就判断num。如果没找到，那么就插入7号map。

在sys_time()==1分钟+7.00秒的时候，删除7号map中的所有元素，表示1分钟已经到了，num限制解除。

这样的话精度是1s，也就是你在0.99秒第一次抢红包（存在0号map中），只需要等待59.01秒就可以再次抢红包了。

?每个节点存储
int?User_ID;?//做key值
char?num;?//表示剩余的抢红包次数
时间戳sys_time();?//第一次抢红包时候的时间
cs