大数据方面的问题

100亿数字，怎么统计前100大的？
分治+堆
海量数据处理：十道面试题与十个海量数据处理方法总结
 数据结构与算法（19）：海量数据处理

C++基础

c++的存储区

变量还有另一种属性——存储期(storage duration，也称生命期)。存储期是指变量在内存中的存在期间。这是从变量值存在的时间角度来分析的。存储期可以分为静态存储期(static storage duration)和动态存储期(dynamic storage duration)。这是由变量的静态存储方式和动态存储方式决定的。

所谓静态存储方式是指在程序运行期间，系统对变量分配固定的存储空间。而动态存储方式则是在程序运行期间，系统对变量动态地分配存储空间。

先看一下内存中的供用户使用的存储空间的情况。这个存储空间可以分为三部分，即：
程序区
静态存储区
动态存储区

数据分别存放在静态存储区和动态存储区中。全局变量全部存放在静态存储区中，在程序开始执行时给全局变量分配存储单元，程序执行完毕就释放这些空间。在程序执行过程中它们占据固定的存储单元，而不是动态地进行分配和释放。

c++的set和unordered_set

STL中map、set的数据结构及底层实现

c++中的set是经过排序的数据，这里数据的值必须是唯一的，查找插入和删除的时间复杂度都是 $O(logn)$

当数据元素增多时（10000到20000个比较），map和set的插入和搜索速度变化如何？

1000的数据时set最多比较14次，2000数据时最多比较15次。

unordered_set的查找时间是O(1)，但是建立时间比较长，数据是无序的，而且按照散列函数插入时间比较长。

c++的虚函数

c++虚函数

虚函数是C++中用于实现多态(polymorphism)的机制。核心理念就是通过基类访问派生类定义的函数。

虚在所谓“推迟联编”或者“动态联编”上，一个类函数的调用并不是在编译时刻被确定的，而是在运行时刻被确定的。由于编写代码的时候并不能确定被调用的是基类的函数还是哪个派生类的函数，所以被成为“虚”函数。

编译器发现一个类中有被声明为virtual的函数，就会为其搞一个虚函数表，也就是 VTABLE。VTABLE实际上是一个函数指针的数组，每个虚函数占用这个数组的一个slot。一个类只有一个VTABLE，不管它有多少个实例。派生类有自己的VTABLE，但是派生类的VTABLE与基类的VTABLE有相同的函数排列顺序，同名的虚函数被放在两个数组的相同位置上。在创建类实例的时候，编译器还会在每个实例的内存布局中增加一个vptr字段，该字段指向本类的VTABLE。通过这些手段，编译器在看到一个虚函数调用的时候，就会将这个调用改写。

void bar(A * a)
{
a->foo();
}

会被改写为：

void bar(A * a)
{
(a->vptr[1])();
}

线程安全

智能指针

reference

大量面经总结(包括牛客网的和我听来的)

[海量数据处理：十道面试题与十个海量数据处理方法总结](

dragon

面试问题小结