2020-08-04 update

1.vector中resize() 和 reserve() 函数的区别？

reserve 容器预留空间 ,但并不真正创建对象，在创建对象前，不能引用容器内元素，因此加入元素后，需要push_back() 和 insert()函数
resize() 改变容器大小，并且创建对象。调用函数后，可以直接引用容器内对象。
reserve()只有一个参数，即需要预留容器的空间
resize() 两个参数，第一个容器新的大小，第二个是加入容器中的新元素
共同点是：都保证了vector中空间（capacity）的大小，但是resize() 会调整 size() 的大小

2.说一下new/delete 和malloc/free函数的区别？ malloc是库函数吗？还是系统调用函数？

区别：

malloc/free是C/C++语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。但是new能够自动分配空间大小，而malloc需要计算字节数。
new/delete能进行对对象进行构造和析构函数的调用进而对内存进行更加详细的工作，而malloc/free不能。
new是类型安全的，而malloc不是，比如：

  int* p = new float[2]; // 编译时指出错误

  int* p = malloc(2*sizeof(float)); // 编译时无法指出错误

  new operator 由两步构成，分别是 operator new 和 construct

返回值。malloc分配失败时，返回的是空指针。new抛出std::bad_alloc异常。
new/delete是保留字，不需要头文件支持；malloc/free需要头文件库函数支持。

联系：

既然new/delete的功能完全覆盖了malloc/free，为什么C++还保留malloc/free呢？因为C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。如果用free释放“new创建的动态对象”，那么该对象因无法执行析构函数而可能导致程序出错。如果用delete释放“malloc申请的动态内存”，理论上讲程序不会出错，但是该程序的可读性很差。所以new/delete，malloc/free必须配对使用。

4.写一个插入排序

#include<iostream>
#include<vector>
using namespace std;
void swap(vector<int> &arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};
void insertsort(vector<int> &arr){
    int N = arr.size();
    for(int i=1;i<N;++i){
        for(int j=i;j>0;--j){
            if(arr[j]<arr[j-1]){
                swap(arr,j,j-1);
            }
        }
    }
};

int main(){
    vector<int> array = {5,3,0,6,1,4};
    insertsort(array);
    for(int i=0;i<array.size();++i){
        std::cout << array[i] <<" ";
    }
    return 0;
}

5.static 的作用？

饰普通变量，修改变量的存储区域和生命周期，使变量存储在静态区，在 main 函数运行前就分配了空间，如果有初始值就用初始值初始化它，如果没有初始值系统用默认值初始化它。
修饰普通函数，表明函数的作用范围，仅在定义该函数的文件内才能使用。在多人开发项目时，为了防止与他人命名空间里的函数重名，可以将函数定位为 static。
修饰成员变量，修饰成员变量使所有的对象只保存一个该变量，而且不需要生成对象就可以访问该成员。
修饰成员函数，修饰成员函数使得不需要生成对象就可以访问该函数，但是在 static 函数内不能访问非静态成员。成员函数：特点：区别与普通成员函数是，其没有this指针，它不属于某一个对象拥有，他属于整个类所有

优点：由于没有this指针的开销，静态成员函数相比较全局函数，速度上会有少许的增长

6.你了解面向对象吗？

封装，继承、多态

封装是信息隐藏，是指利用抽象数据类型将数据和基于数据的操作封装在一起，使其构成一个不可分割的独立实体，数据被保护在抽象数据类型的内部，尽可能地隐藏内部的细节，只保留一些对外接口使之与外部发生联系。系统的其他对象只能通过包裹在数据外面的已经授权的操作来与这个封装的对象进行交流和交互。也就是说用户是无需知道对象内部的细节，但可以通过该对象对外的提供的接口来访问该对象。

对于封装而言，一个对象它所封装的是自己的属性和方法，所以它是不需要依赖其他对象就可以完成自己的操作。使用封装有三大好处：

1、良好的封装能够减少耦合。

2、类内部的结构可以自由修改。

3、可以对成员进行更精确的控制。

4、隐藏信息，实现细节

7 .你喜欢合肥/上海吗？

8. 你对我公司了解吗？宣讲会来了吗？

10. 花一分钟时间介绍一下自己

11. 实习项目介绍一下

12. 如果用三个标签描述你自己

13、有什么示例可以证明的这些吗？

14、介绍一下让你感到最开心的事情

15、业余时间你做什么？

16、一般做什么运动？打什么球？

17、你未来的职业规划是什么样的？

18、你期望中的团队或者工资是怎么样的？

19、按照你的经验如果做到一个团队协作？

20、为什么要选择。。。？

21、最后你有什么问题要问我们吗？

22. extern?

放在变量和函数前，表明该变量和函数在别处已有定义，在该行只是声明，并没有分配内存，此处是为了引用别处已定义好的变量函数，起到跨越文件使用变量和函数的作用，其实可以直接include相应的头文件来使用，主要是可以加快编译速度。

例如，A模块 extern int a； A模块源文件 a =10; B模块同样 extern int a；我们会发现B模块中并没有a的内存分配，但同样也能使用a，原因在于B模块会从A模块中找到定义。另外 extern int a = 10 等同于 int a =10; 但是另外一个文件include该文件时，会造成编译器发现有两个a 全局变量。因此我们通常将声明放在头文件

extern c {} ，表明是C语言的接口函数，由于C和C++对函数命名的不一致，C++支持函数重载，而C语言不支持，需要C++编译器编译的时候告知编译器，此处调用的是C中函数，需要编译器选择C语言的编译规则来编译和链接此处的函数。

23. inline 内联函数

特征：

相当于把内联函数里面的内容写在调用内联函数处；
相当于不用执行进入函数的步骤，直接执行函数体；
相当于宏，却比宏多了类型检查，真正具有函数特性；
编译器一般不内联包含循环、递归、switch 等复杂操作的内联函数；
在类声明中定义的函数，除了虚函数的其他函数都会自动隐式地当成内联函数。

24. inline优缺点

优点

内联函数同宏函数一样将在被调用处进行代码展开，省去了参数压栈、栈帧开辟与回收，结果返回等，从而提高程序运行速度。
内联函数相比宏函数来说，在代码展开时，会做安全检查或自动类型转换（同普通函数），而宏定义则不会。
在类中声明同时定义的成员函数，自动转化为内联函数，因此内联函数可以访问类的成员变量，宏定义则不能。
内联函数在运行时可调试，而宏定义不可以。

缺点

代码膨胀。内联是以代码膨胀（复制）为代价，消除函数调用带来的开销。如果执行函数体内代码的时间，相比于函数调用的开销较大，那么效率的收获会很少。另一方面，每一处内联函数的调用都要复制代码，将使程序的总代码量增大，消耗更多的内存空间。
inline 函数无法随着函数库升级而升级。inline函数的改变需要重新编译，不像 non-inline 可以直接链接。
是否内联，程序员不可控。内联函数只是对编译器的建议，是否对函数内联，决定权在于编译器。

25. 说说引用，什么时候用引用好，什么时候用指针好？

答：

使用引用参数的主要原因有两个：

程序员能修改调用函数中的数据对象
通过传递引用而不是整个数据–对象，可以提高程序的运行速度

一般的原则：

对于使用引用的值而不做修改的函数：

如果数据对象很小，如内置数据类型或者小型结构，则按照值传递
如果数据对象是数组，则使用指针（唯一的选择），并且指针声明为指向const的指针
如果数据对象是较大的结构，则使用const指针或者引用，已提高程序的效率。这样可以节省结构所需的时间和空间
如果数据对象是类对象，则使用const引用（传递类对象参数的标准方式是按照引用传递）

对于修改函数中数据的函数：

如果数据是内置数据类型，则使用指针
如果数据对象是数组，则只能使用指针
如果数据对象是结构，则使用引用或者指针
如果数据是类对象，则使用引用

26. 堆/栈的区别？

管理方式不同：

对于栈来讲，是由编译器自动管理，无需我们手工控制；

对于堆来说，申请和释放工作由程序员控制，容易产生memory leak。
空间大小不同：

对于栈来讲，一般都是有一定的空间大小的，一般默认的栈空间大小为1M，同时，我们是可以进行修改的；

对于堆来说，在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。
能否产生碎片不同：

对于栈来讲，不会有碎片，因为栈是先进后出的队列，以至于永远都不可能有一个内存块从栈中间弹出，在他弹出之前，在他上面的后进的栈内容已经被弹出；

对于堆来说，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。
生长方向不同：

对于栈来讲，生长方向是向下的，是向着内存地址减小的方向增长；

对于堆来说，生长方向是向上的，也就是向着内存地址增加的方向。
分配方式不同：

对于栈来讲，栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloc函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。

对于堆来说，堆都是动态分配的，没有静态分配的堆。
分配效率不同：

对于栈来讲，栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。

对于堆来说，堆则是C/C++函数库提供的，它的机制是很复杂的。显然，堆的效率比栈要低得多。

从这里我们可以看到，堆和栈相比，由于大量new/delete的使用，容易造成大量的内存碎片；由于没有专门的系统支持，效率很低；由于可能引发用户态和核心态的切换，内存的申请，代价变得更加昂贵。所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址，EBP和局部变量都采用栈的方式存放。

27. null与nullptr区别

NULL在C++中就是0，这是因为在C++中void* 类型是不允许隐式转换成其他类型的，所以之前C++中用0来代表空指针，但是在重载整形的情况下，会出现上述的问题。所以，C++11加入了nullptr，可以保证在任何情况下都代表空指针，而不会出现上述的情况，因此，建议以后还是都用nullptr替代NULL吧，而NULL就当做0使用。

28. STL中map和unordered_map 区别

需要引入的头文件不同

map:

#include < map >

unordered_map:

#include < unordered_map >

内部实现机理不同

map： map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找，删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。

unordered_map: unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序是无序的。

优缺点以及适用处

map：

1、优点：

1）有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作

2）红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高

2、缺点：空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间

3、适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

1、优点：因为内部实现了哈希表，因此其查找速度非常的快

2、缺点：哈希表的建立比较耗费时间

3、适用处：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map

29. c++ 中list, vector, map, set 区别与用法比较

List封装了链表,Vector封装了数组, list和vector得最主要的区别在于vector使用连续内存存储的，他支持[]运算符，而list是以链表形式实现的，不支持[]。

Vector对于随机访问的速度很快，但是对于插入尤其是在头部插入元素速度很慢，在尾部插入速度很快。List对于随机访问速度慢得多，因为可能要遍历整个链表才能做到，但是对于插入就快的多了，不需要拷贝和移动数据，只需要改变指针的指向就可以了。另外对于新添加的元素，Vector有一套算法，而List可以任意加入。

Map,Set属于标准关联容器，使用了非常高效的平衡检索二叉树：红黑树，他的插入删除效率比其他序列容器高是因为不需要做内存拷贝和内存移动，而直接替换指向节点的指针即可。

Set和Vector的区别在于Set不包含重复的数据。Set和Map的区别在于Set只含有Key，而Map有一个Key和Key所对应的Value两个元素。

Map和Hash_Map的区别是Hash_Map使用了Hash算法来加快查找过程，但是需要更多的内存来存放这些Hash桶元素，因此可以算得上是采用空间来换取时间策略。

vector 向量相当于一个数组

在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。

优点：

(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push_back() pop_back()
(2) 随机访问方便，即支持[ ]操作符和vector.at()
(3) 节省空间。

缺点：

(1) 在内部进行插入删除操作效率低。
(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。
(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放

list 双向链表

每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。

优点：

(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop

缺点：

(1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
(2) 相对于verctor占用内存多

deque

双端队列 double-end queue

deque是在功能上合并了vector和list。

优点：

(1) 随机访问方便，即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop

缺点：

(1) 占用内存多

使用区别：

1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

数据结构

deque,queue,vector,stack,list

X a(n,t);

a.insert(p,t);

a.insert(p,n,t);

a.erase(p);

a.clear;

a.front();

a.back();

a.push_front(t);

a.push_back(t);

a.pop_front(t);

a.pop_back(t);

a[n];

a.at(t);

30. 继承的种类

clip_image002.png

31. 线程与进程

https://zhuanlan.zhihu.com/p/60375108

进程与线程的区别

进程是CPU资源分配的基本单位，线程是独立运行和独立调度的基本单位（CPU上真正运行的是线程）。
进程拥有自己的资源空间，一个进程包含若干个线程，线程与CPU资源分配无关，多个线程共享同一进程内的资源。
线程的调度与切换比进程快很多。

32. 并发与并行

并发：

在操作系统中，某一时间段，几个程序在同一个CPU上运行，但在任意一个时间点上，只有一个程序在CPU上运行。

当有多个线程时，如果系统只有一个CPU，那么CPU不可能真正同时进行多个线程，CPU的运行时间会被划分成若干个时间段，每个时间段分配给各个线程去执行，一个时间段里某个线程运行时，其他线程处于挂起状态，这就是并发。并发解决了程序排队等待的问题，如果一个程序发生阻塞，其他程序仍然可以正常执行。

并行：

当操作系统有多个CPU时，一个CPU处理A线程，另一个CPU处理B线程，两个线程互相不抢占CPU资源，可以同时进行，这种方式成为并行。

区别：

并发只是在宏观上给人感觉有多个程序在同时运行，但在实际的单CPU系统中，每一时刻只有一个程序在运行，微观上这些程序是分时交替执行。

在多CPU系统中，将这些并发执行的程序分配到不同的CPU上处理，每个CPU用来处理一个程序，这样多个程序便可以实现同时执行。

例子：

你吃饭吃到一半，电话来了，你一直到吃完了以后才去接，这就说明你不支持并发也不支持并行。

你吃饭吃到一半，电话来了，你停了下来接了电话，接完后继续吃饭，这说明你支持并发。

你吃饭吃到一半，电话来了，你一边打电话一边吃饭，这说明你支持并行。

并发的关键是你有处理多个任务的能力，不一定要同时。并行的关键是你有同时处理多个任务的能力。所以我认为它们最关键的点就是：是否是『同时』。

33. 进程的三个状态

就绪状态，运行状态，阻塞状态

34. 进程从执行状态转换到阻塞状态的可能原因是本进程：

需要等待其他进程的执行结果

执行了P操作

35. Kill与kill-9

kill是Linux下常见的命令。其man手册的功能定义如下：

kill – send a signal to a process

明朗了，其实kill就是给某个进程id发送了一个信号。默认发送的信号是SIGTERM，而kill -9发送的信号是SIGKILL，即exit。exit信号不会被系统阻塞，所以kill -9能顺利杀掉进程。当然你也可以使用kill发送其他信号给进程。

经常使用的killall呢？

killall – kill processes by name 即，通过指定进程名的方式杀死进程。

36. 构造函数为什么不能是虚函数？

虚函数采用的是虚调用的办法，虚调用是一种可以在只知道部分信息的情况下正常工作的机制，特别是在我们只知道接口而不知道准确的对象类型的函数。但是，要创建一个类对象，必须要让构造函数知道对象的准确类型，所以构造函数不能为虚！

37. 析构函数为何常常为虚函数？

创建一个对象时我们总是要明白指定对象的类型。我们往往通过基类的指针来销毁对象。这时候假设析构函数不是虚函数，就不能正确识别对象类型从而不能正确调用析构函数。

38. 虚拟内存

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如RAM）的使用也更有效率。

注意：虚拟内存不只是“用磁盘空间来扩展物理内存”的意思——这只是扩充内存级别以使其包含硬盘驱动器而已。把内存扩展到磁盘只是使用虚拟内存技术的一个结果，它的作用也可以通过覆盖或者把处于不活动状态的程序以及它们的数据全部交换到磁盘上等方式来实现。对虚拟内存的定义是基于对地址空间的重定义的，即把地址空间定义为“连续的虚拟内存地址”，以借此“欺骗”程序，使它们以为自己正在使用一大块的“连续”地址。

39. 虚拟内存提供了三个重要的能力：缓存，内存管理，内存保护

将主存视为一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在磁盘和主存之间来回传送数据
为每个进程提供了一致的地址空间，简化内存管理
保护了每个进程的地址空间不被其他进程破坏

40. 那么虚表指针在什么时候，或者说在什么地方初始化呢？

答案：是在构造函数中进行虚表的创建和虚表指针的初始化。还记得构造函数的调用顺序吗，在构造子类对象时，要先调用父类的构造函数，此时编译器只“看到了”父类，并不知道后面是否后还有继承者，它初始化父类对象的虚表指针，该虚表指针指向父类的虚表。当执行子类的构造函数时，子类对象的虚表指针被初始化，指向自身的虚表。

41. 虚函数与纯虚函数区别：

虚函数和纯虚函数可以定义在同一个类中，含有纯虚函数的类被称为抽象类，而只含有虚函数的类不能被称为抽象类。
虚函数可以被直接使用，也可以被子类重载以后以多态的形式调用，而纯虚函数必须在子类中实现该函数才可以使用，因为纯虚函数在基类只有声明而没有定义。
虚函数和纯虚函数都可以在子类中被重载，以多态的形式被调用。
虚函数和纯虚函数通常存在于抽象基类之中，被继承的子类重载，目的是提供一个统一的接口。
在虚函数和纯虚函数的定义中不能有static标识符，因为被static修饰的函数在编译时候要求前期绑定,然而虚函数却是动态绑定，而且被两者修饰的函数生命周期也不一样。
虚函数必须实现，如果不实现，编译器将报错。
对于虚函数来说，父类和子类都有各自的版本。由多态方式调用的时候动态绑定。
实现了纯虚函数的子类，该纯虚函数在子类中就变成了虚函数，子类的子类即孙子类可以覆盖该虚函数，由多态方式调用的时候动态绑定。
虚函数是C++中用于实现多态的机制。核心理念就是通过基类访问派生类定义的函数。
多态性指相同对象收到不同消息或不同对象收到相同消息时产生不同的实现动作。
如果一个类中含有纯虚函数，那么任何试图对该类进行实例化的语句都将导致错误的产生，因为抽象基类(ABC)是不能被直接调用的。必须被子类继承重载以后，根据要求调用其子类的方法。

42. malloc的原理？brk系统调用和mmap系统调用的作用分别是什么？

malloc根据用户要求从堆里动态分配内存空间。为减少内存碎片降低内存开销，采用内存池的方式。首先分配较大内存为堆，分为大小不同的内存块进行管理。malloc利用隐式链表，在分配时遍历整个链表，选择大小合适的内存块分配。内存分配时会调用brk或mmap系统，小于128K时调用brk在堆中分配，大于128K时调用mmap在映射区分配。

43. 进程的缺陷的，主要体现在两点上：

进程只能在一个时间干一件事，如果想同时干两件事或多件事，进程就无能为力了。
进程在执行的过程中如果阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖于输入的数据，也将无法执行。

如果这两个缺点理解比较困难的话，举个现实的例子也许你就清楚了：如果把我们上课的过程看成一个进程的话，那么我们要做的是耳朵听老师讲课，手上还要记笔记，脑子还要思考问题，这样才能高效的完成听课的任务。而如果只提供进程这个机制的话，上面这三件事将不能同时执行，同一时间只能做一件事，听的时候就不能记笔记，也不能用脑子思考，这是其一；如果老师在黑板上写演算过程，我们开始记笔记，而老师突然有一步推不下去了，阻塞住了，他在那边思考着，而我们呢，也不能干其他事，即使你想趁此时思考一下刚才没听懂的一个问题都不行，这是其二。

44. 线程的优点

因为要并发，我们发明了进程，又进一步发明了线程。

进程和线程的并发层次不同：

进程属于在处理器这一层上提供的抽象；
线程则属于在进程这个层次上再提供了一层并发的抽象。如果我们进入计算机体系结构里，就会发现，流水线提供的也是一种并发，不过是指令级的并发。这样，流水线、线程、进程就从低到高在三个层次上提供我们所迫切需要的并发！

除了提高进程的并发度，线程还有个好处，就是可以有效地利用多处理器和多核计算机。现在的处理器有个趋势就是朝着多核方向发展，在没有线程之前，多核并不能让一个进程的执行速度提高，原因还是上面所有的两点限制。但如果讲一个进程分解为若干个线程，则可以让不同的线程运行在不同的核上，从而提高了进程的执行速度。

例如：我们经常使用Word进行文字排版，实际上就打开了多个线程。这些线程一个负责显示，一个接受键盘的输入，一个进行存盘等等。这些线程一起运行，让我们感觉到我们输入和屏幕显示同时发生，而不是输入一些字符，过一段时间才能看到显示出来。在我们不经意间，还进行了自动存盘操作。这就是线程给我们带来的方便之处。

45. 进程与线程的区别

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位。
线程是进程的一个实体, 是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。
一个线程可以创建和撤销另一个线程，同一个进程中的多个线程之间可以并发执行。

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

46. 一个由C/C++编译的程序占用的内存分配：

栈区（stack）：由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆区（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS（操作系统）回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
全局区（静态区）（static）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
文字常量区：常量字符串就是放在这里的。程序结束后由系统释放。
程序代码区：存放函数体的二进制代码。

int a=0;  全局初始化区  

char *p1;  全局未初始化区  

int main()  

{  

 int b; //栈  

 char s[]="abc"; //栈  

 char *p2; //栈  

 char *p3="123456"; //123456/0在常量区，p3在栈上。  

 

 static int c =0；//全局（静态）初始化区  

 p1 = (char *)malloc(10); //分配得来得10和20字节的区域就在堆区

 p2 = (char *)malloc(20);    

 strcpy(p3,"123456"); //123456/0放在常量区，编译器可能会将它与p3所指向的"123456"  优化成一个地方。  

}

47. NMS 非极大值抑制的原理与C++代码实现

非极大值抑制：先假设有6个候选框，根据分类器类别分类概率做排序，从小到大分别属于车辆的概率分别为A、B、C、D、E、F。

1、从最大概率矩形框F开始，分别判断A~E与F的重叠度IOU是否大于某个设定的阈值;

2、假设B、D与F的重叠度超过阈值，那么就扔掉B、D；并标记第一个矩形框F，是我们保留下来的。

3、从剩下的矩形框A、C、E中，选择概率最大的E，然后判断E与A、C的重叠度，重叠度大于一定的阈值，那么就扔掉；并标记E是我们保留下来的第二个矩形框。

4、一直重复这个过程，找到所有曾经被保留下来的矩形框。

*//**升序排列*

bool cmpScore(Bbox lsh, Bbox rsh) {

    if (lsh.score < rsh.score)

    return true;

    else

    return false;

 }

\8. https://blog.csdn.net/krais_wk/article/details/80938752

48. 单峰函数求极值

#include<bits/stdc++.h>

using namespace std;

double a,b,c;

inline double f(double x) {

  return a*x*x+b*x+c;

}

int main(void)

{

  cin>>a>>b>>c;

  //形如y=ax^2+by+c的二次函数

  double l=-1e9,r=1e9;

  while (l+1e-9<r)

  {

    double lmid=l+(r-l)/3.0;

    //图像上位于1/3部分的靠左的mid值 

    double rmid=l+(r-l)/3.0*2.0;

    //图像上位于2/3部分的靠右的mid值

    if (f(lmid)<f(rmid)) l=lmid;

    else r=rmid;

    //求单峰极值 

  } 

  cout<<"X="<<l<<'\n';

  cout<<"Y="<<f(l); 

}

49. Eigen矩阵储存

数据存储：Matrix创建的矩阵默认是按列存储，Eigen在处理按列存储的矩阵时会更加高效。如果想修改可以在创建矩阵的时候加入参数，如:

Matrix<int,3, 4, ColMajor> Acolmajor;

Matrix<int,3, 4, RowMajor> Arowmajor;

50. 激光slam与视觉SLAM的优劣

51. SIFT缺点（Scale-invariant feature transform）

SIFT是十分经典的算法，但有以下缺点：

实时性不高
特征点比较少
对边缘光滑的图像有时无能为力

52. SIFT提取策略

构建尺度空间

这是一个初始化操作，尺度空间理论目的是模拟图像数据的多尺度特征。

高斯卷积核是实现尺度变换的唯一线性核，于是一幅二维图像的尺度空间定义为：

clip_image005.png

其中 G(x,y,σ) 是尺度可变高斯函数。

（x，y）是空间坐标，是尺度坐标。σ大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的σ值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。

图像金字塔的建立：对于一幅图像I,建立其在不同尺度(scale)的图像，也成为子八度（octave），这是为了scale-invariant，也就是在任何尺度都能够有对应的特征点，第一个子八度的scale为原图大小，后面每个octave为上一个octave降采样的结果，即原图的1/4（长宽分别减半），构成下一个子八度（高一层金字塔）。

LoG近似DoG找到关键点<检测DOG尺度空间极值点>

为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。一个点如果在DOG尺度空间本层以及上下两层的26个领域中是最大或最小值时，就认为该点是图像在该尺度下的一个特征点,如图所示。

使用Laplacian of Gaussian能够很好地找到找到图像中的兴趣点，但是需要大量的计算量，所以使用Difference of Gaussian图像的极大极小值近似寻找特征点.DOG算子计算简单，是尺度归一化的LoG算子的近似,极值点检测用的Non-Maximal Suppression.有关DOG寻找特征点的介绍及方法详见.
除去不好的特征点

这一步本质上要去掉DoG局部曲率非常不对称的像素。
给特征点赋值一个128维方向参数

上一步中确定了每幅图中的特征点，现在利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。

为(x,y)处梯度的模值和方向公式。其中L所用的尺度为每个关键点各自所在的尺度。至此，图像的关键点已经检测完毕，每个关键点有三个信息：位置，所处尺度、方向，由此可以确定一个SIFT特征区域。

梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。随着距中心点越远的领域其对直方图的贡献也响应减小.Lowe论文中还提到要使用高斯函数对直方图进行平滑，减少突变的影响。

在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每45度一个柱，总共8个柱, 或者每10度一个柱，总共36个柱。Lowe论文中还提到要使用高斯函数对直方图进行平滑，减少突变的影响。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。
关键点描述子的生成

首先将坐标轴旋转为关键点的方向，以确保旋转不变性。以关键点为中心取8×8的窗口。

图左部分的中央为当前关键点的位置，每个小格代表关键点邻域所在尺度空间的一个像素，利用公式求得每个像素的梯度幅值与梯度方向，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，然后用高斯窗口对其进行加权运算。

图中蓝色的圈代表高斯加权的范围（越靠近关键点的像素梯度方向信息贡献越大）。然后在每4×4的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，即可形成一个种子点，如图右部分示。此图中一个关键点由2×2共4个种子点组成，每个种子点有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。

计算keypoint周围的16*16的window中每一个像素的梯度，而且使用高斯下降函数降低远离中心的权重。

这样就可以对每个feature形成一个448=128维的描述子，每一维都可以表示4*4个格子中一个的scale/orientation. 将这个向量归一化之后，就进一步去除了光照的影响。

根据SIFT进行Match

生成了A、B两幅图的描述子，（分别是k1128维和k2128维），就将两图中各个scale（所有scale）的描述子进行匹配，匹配上128维即可表示两个特征点match上了。

实际计算过程中，为了增强匹配的稳健性，Lowe建议对每个关键点使用4×4共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。为了排除因为图像遮挡和背景混乱而产生的无匹配关系的关键点,Lowe提出了比较最近邻距离与次近邻距离的方法,距离比率ratio小于某个阈值的认为是正确匹配。因为对于错误匹配,由于特征空间的高维性,相似的距离可能有大量其他的错误匹配,从而它的ratio值比较高。Lowe推荐ratio的阈值为0.8。但作者对大量任意存在尺度、旋转和亮度变化的两幅图片进行匹配，结果表明ratio取值在0. 4~0. 6之间最佳，小于0. 4的很少有匹配点，大于0. 6的则存在大量错误匹配点。(如果这个地方你要改进，最好给出一个匹配率和ration之间的关系图，这样才有说服力)作者建议ratio的取值原则如下:

ratio=0. 4　对于准确度要求高的匹配；

ratio=0. 6　对于匹配点数目要求比较多的匹配；

ratio=0. 5　一般情况下。

也可按如下原则:当最近邻距离<200时ratio=0. 6，反之ratio=0. 4。ratio的取值策略能排分错误匹配点。

当两幅图像的SIFT特征向量生成后，下一步我们采用关键点特征向量的欧式距离来作为两幅图像中关键点的相似性判定度量。取图像1中的某个关键点，并找出其与图像2中欧式距离最近的前两个关键点，在这两个关键点中，如果最近的距离除以次近的距离少于某个比例阈值，则接受这一对匹配点。降低这个比例阈值，SIFT匹配点数目会减少，但更加稳定。

53. kd-tree

K-D树的构造

超平面的选择：采用最大方差法，计算出每个维度上的方差，取最大方差所在维度为垂直于超平面的方向轴（不是作为超平面而是作为方向轴）。因为方差越大，说明数据点在该维度上越为分散，从而分割的效果越好。
节点的选择：中值选择法，在数据结构的知识中已知平衡二叉树的平均查询效率最好，所以在选择各子树根节点时应该尽量保证分割后的树仍然能达到或接近平衡状态。将方向轴上的数据进行排序，取中值点为子树根节点进行超平面分割。
对左右子树重复以上过程，直至树建立完成。

算法原理

向下遍历：在遍历KD树时，根据每个节点的方向轴数据来确定遍历顺序。从根节点开始，将查找点与根节点方向轴上的数据进行比较，小于则进入左子树查找，反之则进入右子树查找。重复此过程直到遍历到叶子节点。完成向下遍历操作。

向上回溯：显然，遍历得到的点很大可能不是最近点，仅仅是处于同一子空间而已，既无法保证其距离小于查找点到叶子节点父节点的距离，也无法保证其距离小于查找点到另一子空间中节点的距离。所以要进行回溯。首先，向上回溯到叶子节点的父节点，计算查找点到该父节点的距离，若小于之前距离则把该父节点当作最邻近点，并更新最短距离。反之则不更新。然后，以查找点为圆心，到查询到的邻近点距离为半径（此时可能是叶子节点也可能是叶子节点的父节点）进行画圆。观察是否与叶子节点的父节点另一子空间相交。若相交，则进入另一子空间继续查询（重复遍历和回溯操作）。若不相交，则继续回溯并重复该操作，直至回溯到根节点方止。

向下遍历：

1.先从（7,2）查找，x=7为超平面方向轴，因为x=2 < x=7,所以遍历到左空间中的（5,4）节点。

2.在（5，4）点上查找时，y = 4为超平面的方向轴，因为由于查找点为y值为4.5，4.5>4，因此进入右子空间查找到（4,7）。

3.形成搜索路径<（7,2），（5,4），（4,7）>，取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。

向上回溯：

1.然后回溯到父节点（5,4），计算其与查找点之间的距离为3.041。3.041<3.202，所以最邻近点更新为（5，4），最短距离更新为3.041。

2.以（2，4.5）为圆心，以3.041为半径作圆，如图所示。可见该圆和y = 4超平面相交，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。

3.回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。

4.回溯至根节点（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面相交。

5.至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。

54. 深度与视差转换关系：

depth = (fx * baseline) / disparity

深度方向的测量误差与测量距离的平方成正比，而X/Y方向的误差与距离成正比。

随着测量距离的增加，深度方向的误差比X/Y方向更难控制。

55. ORB（Oriented FAST and Rotated BRIEF）优点

一定的尺度不变性：利用图像金子塔实现，由于金字塔层数有限，因此只能在一定范围保证尺度的不变性。
旋转不变性：首先利用灰度质心法计算出特征的方向，然后计算旋转后的BRIEF描述子。
抗噪能力：计算BRIEF的时候不是使用一个点的灰度，而是使用了点周围5×5区域的灰度。
应该也有一定的光照不变性：因为FAST提取的时候是比较灰度，rBRIEF的计算也是比较灰度。
速度快：使用了FAST角点，BRIEF描述子，二者均很快。速度是SIFT的100倍，SURF的10倍。

56. ORB特征提取的流程

提取流程概览

l 构造金字塔

l 提取FAST角点

l 利用灰度质心法，计算旋转角度

l 计算旋转后的BRIEF描述子

提取FAST角点

2.1 如何分配每一层提取的特征点数量。

金字塔层数越高，图像的面积越小，所能提取到的特征数量就越小。基于这个原理，我们可以按照面积将特征点均摊到金字塔每层的图像上。我们假设第0层图像的宽为W，长为 L ，缩放因子s（这里的0<S<1）。那么整个金字塔总的面积为

2.2 什么是FAST角点，如何提取？

FAST角点，通过对比中心与周围点（半径为3的圆上的点）灰度的差别，即可确定是否为关键点，速度贼快。

具体的步骤为：

像素p ，其灰度为Ip ;
设置一个阈值T ,比如Ip的20%。
以 p为圆心，选择半径为3的圆上的16个像素点。

4）如果圆上面有连续的N个点的亮度大于阈值 Ip+T或者小于Ip-T，则判定此点为FAST角点。通常N的取值有FAST-9，FAST-11，FAST-12最常见。对于FAST-12有高效的检测方法，首先检测12点、3点、6点和9点钟的像素（1,5,9,13），如果至少有3个是成功的，才有可能是角点，再去进一步的检测，否则就直接pass。

按照上述步骤对图像上每个像素处理一遍，可以获取大量的FAST角点。那，FAST角点容易出现扎堆现象，要用非极大值抑制再处理一遍（Non-maximal suppression）。

Oriented FAST，旋转角度计算

ORB计算角度也比较简单，首先一个圆形区域的灰度质心，连接质心和圆心形成一个向量，这个向量的角度就是角点的角度。圆的半径取为15，因为整个patch一般取的是31×31的。

注意，现在我们已经把坐标系的圆心设在了关键点上，那么灰度质心为

clip_image024.jpg

计算Rotation-Aware BRIEF， rBRIEF

4.1 BRIEF描述子

BRIEF是一个二进制的描述子，计算和匹配的速度都很快。

4.2 Steered BRIEF

BRIEF描述子是没有考虑旋转不变性的，Steered BRIEF根据Oriented FAST计算出的角度，把原始的256个点对的坐标旋转之后，再取灰度。从而实现了旋转不变性。

4.3 Rotation-Aware BRIEF

上述过程虽然解决了旋转问题，但是也造成了描述子一些性能的下降。

这个问题的解决是使用了学习的方法，利用了大量的数据，选择出了效果最好的256个点对位置。以后每次提取特征点都使用这256个位置。

4.4 抗噪能力的提高

在计算BRIEF描述子的时候，ORB使用的不是每个点的灰度，而是周围5×5的patch的灰度。因此起到了低通滤过的效果，对噪声有更强的鲁棒性。

ORB-SLAM对ORB特征的改进

ORBSLAM中并没有使用OpenCV的实现，因为OpenCV的版本提取的ORB特征过于集中，会出现扎堆的现象。这会降低SLAM的精度，对于闭环来说，也会降低一幅图像上的信息量。ORB-SLAM中的实现提高了特征分布的均匀性。

最简单的一种方法是把图像划分成若干小格子，每个小格子里面保留质量最好的n个特征点。这种方法看似不错，实际上会有一些问题。当有些格子里面能够提取的数量不足n个的时候（无纹理区域），整幅图上提取的特征总量就达不到我们想要的数量。`

ORB-SLAM中的实现就解决了这么一个问题，当一个格子提取不到FAST点的时候，自动降低阈值。ORB-SLAM主要改进了FAST角点提取步骤。

对于金字塔的每一层。

划分格子，格子的大小为30×30pixels

单独对每个格子提取FAST角点，如果提取不到点，就降低FAST阈值。这样保证纹理较弱的区域也能提取到一些FAST角点。这一步可以提取大量的FAST点。

基于四叉树，均匀的选取

clip_image022.png

个FAST点。

上述步骤中，基于四叉树的方法有点复杂，下面分析一下。

如果图片的宽度比较宽，就先把分成左右w/h份。一般的640×480的图像开始的时候只有一个node。

如果node里面的点数>1，把每个node分成四个node，如果node里面的特征点为空，就不要了，删掉。

新分的node的点数>1，就再分裂成4个node。如此，一直分裂。

终止条件为：node的总数量无法再进行分裂。

然后从每个node里面选择一个质量最好的FAST点。

clip_image029.png

clip_image030.jpg

clip_image031.jpg

56. 最小二乘法的推导

https://blog.csdn.net/u011026329/article/details/79183114

最小二乘法和梯度下降法有哪些区别？

迭代法，即在每一步update未知量逐渐逼近解，可以用于各种各样的问题（包括最小二乘），比如求的不是误差的最小平方和而是最小立方和。

梯度下降是迭代法的一种，可以用于求解最小二乘问题（线性和非线性都可以）。高斯-牛顿法是另一种经常用于求解非线性最小二乘的迭代法（一定程度上可视为标准非线性最小二乘求解方法）。

还有一种叫做Levenberg-Marquardt的迭代法用于求解非线性最小二乘问题，就结合了梯度下降和高斯-牛顿法。

然后Levenberg-Marquardt方法的好处就是在于可以调节:

如果下降太快，使用较小的λ，使之更接近高斯牛顿法

如果下降太慢，使用较大的λ，使之更接近梯度下降法

57. 深拷贝与浅拷贝

在未定义显示拷贝构造函数的情况下，系统会调用默认的拷贝函数——即浅拷贝，它能够完成成员的一一复制。当数据成员中没有指针时，浅拷贝是可行的；但当数据成员中有指针时，如果采用简单的浅拷贝，则两类中的两个指针将指向同一个地址，当对象快结束时，会调用两次析构函数，而导致指针悬挂现象，所以，此时，必须采用深拷贝。
深拷贝与浅拷贝的区别就在于深拷贝会在堆内存中另外申请空间来储存数据，从而也就解决了指针悬挂的问题。简而言之，当数据成员中有指针时，必须要用深拷贝。

带实例的解释

默认的拷贝构造函数是浅拷贝

浅拷贝就是对象的数据成员之间的简单赋值，如你设计了一个没有类而没有提供它的拷贝构造函数，当用该类的一个对象去给令一个对象赋值时所执行的过程就是浅拷贝，如：

class A 

{ 

 public:

 A(int _data) : data(_data){} 

 A(){}

 private:

 int data;

 };

int main() 

{ 

 A a(5), b = a; // 仅仅是数据成员之间的赋值 

}

这一句b = a;就是浅拷贝，执行完这句后b.data = 5;

如果对象中没有其他的资源（如：堆，文件，系统资源等），则深拷贝和浅拷贝没有什么区别，

但当对象中有这些资源时，例子：

class A 

{ 

 public:

 A(int _size) : size(_size)

 {

     data = new int[size];

 } // 假如其中有一段动态分配的内存 

 A(){};

  ~A()

 {

     delete [] data;

 } // 析构时释放资源

 private:

 int* data;

 int size; 

}

int main() 

{ 

 A a(5), b = a; // 注意这一句 

}

这里的b = a会造成未定义行为，因为类A中的复制构造函数是编译器生成的，所以b = a执行的是一个浅拷贝过程。我说过浅拷贝是对象数据之间的简单赋值，比如：

b.size = a.size;

b.data = a.data; // Oops!

这里b的指针data和a的指针指向了堆上的同一块内存，a和b析构时，b先把其data指向的动态分配的内存释放了一次，而后a析构时又将这块已经被释放过的内存再释放一次。对同一块动态内存执行2次以上释放的结果是未定义的，所以这将导致内存泄露或程序崩溃。

所以这里就需要深拷贝来解决这个问题，深拷贝指的就是当拷贝对象中有对其他资源（如堆、文件、系统等）的引用时（引用可以是指针或引用）时，对象的另开辟一块新的资源，而不再对拷贝对象中有对其他资源的引用的指针或引用进行单纯的赋值。如：

class A 

{ 

 public:

 A(int _size) : size(_size)

 {

    data = new int[size];

 } // 假如其中有一段动态分配的内存 

 A(){};

 A(const A& _A) : size(_A.size)

 {

    data = new int[size];

 } // 深拷贝 

 ~A()

 {

    delete [] data;

 } // 析构时释放资源

 private:

 int* data; 

    int size;

 }

int main() 

{ 

 A a(5), b = a; // 这次就没问题了 

}

总结：深拷贝和浅拷贝的区别是在对象状态中包含其它对象的引用的时候，当拷贝一个对象时，如果需要拷贝这个对象引用的对象，则是深拷贝，否则是浅拷贝。

59. python中哪些是可变数据类型，哪些是不可变数据类型。可变数据类型：列表list和字典dict；不可变数据类型：整型int、浮点型float、字符串型string和元组tuple。

60. python深拷贝和浅拷贝的区别? python的等号和copy有什么区别?

61. 值传递，地址传递，引用传递的联系和区别

62. 快排和堆排的优缺点和应用场景

63. 实现归并排序

#include <iostream>
#include <vector>
using namespace std;
vector<int> merge(const vector<int> &L,const vector<int> &R){
    vector<int> res={};
    int i=0;
    int j=0;
    while(i<L.size() and j <R.size()){
        if (L[i] <= R[j]){
            res.push_back(L[i]);
            i++;
        }else{
            res.push_back(R[j]);
            j++;
        }
    }
    while(i<L.size()){
        res.push_back(L[i]);
        i++;
    };
    while(j<R.size()){
        res.push_back(R[j]);
        j++;
    };

    return res;
}

vector<int> MergeSort(vector<int> &arr){
    int l = arr.size();
    if(l<2){ return arr;};
    int mid = l/2;
    vector<int> L={};
    vector<int> R={};
    L.reserve(mid);
    for(int i=0;i<mid;i++){
        L.push_back(arr[i]);
    }
    for(int j=mid;j<l;j++){
        R.push_back(arr[j]);
    }

    L = MergeSort(L);
    R = MergeSort(R);

    return merge(L,R);
}
int main() {
    vector<int> array = {5,3,0,6,1,4},res;
    res = MergeSort(array);
    cout << "after Merge Sort..." <<endl;
    for(auto i:res){
        cout << i<<" ";
    }

    return 0;
}

64. 实现快速排序

#include <iostream>
#include <vector>
using namespace std;
//This a quickSort Algorithm. The main thought is divide and conquer.

void swap(vector<int> &arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int partition(vector<int>&arr,int low,int high){ //conquer
    int i = low-1;
    int pivot = arr[high];
    for(int j=low;j<high;j++){
        if(arr[j] <= pivot) {  //find the number which is smaller than pivot,and we can confirm the true place of pivot(arr[high]).
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr,i+1,high);
    return i+1;
}

void quickSort(vector<int> &arr,int low,int high){
    if (low<high){
        int pi = partition(arr,low,high);
        quickSort(arr,low,pi-1);  //divide
        quickSort(arr,pi+1,high);
    }
}



int main() {
    vector<int> arr = {1,2,4,8,12,1,3,9,2,5,7,8,122,654,7654,211};
    int n = arr.size();
    cout << "before quick sort..." <<endl;
    for(auto v: arr){
        cout << v <<" ";
    };
    cout << endl;
    quickSort(arr,0,n-1);
    cout << "After quick sort..." <<endl;
    for(auto v: arr){
        cout << v <<" ";
    };
    return 0;
}

65. C++中sort底层是什么，是否稳定，还有哪些稳定排序算法

66. 项目用了哪些多线程技术？

67. 光流算法原理

68. C++编译过程

69. C++里面vector、list、deque的区别

70. topK要求nlogk

71. C++中什么是左值什么是右值

72. python 元组和列表的区别

73. python 当中的with说一下

74. linux基本操作：

l 怎么设置环境变量: .bashrc，然后source一下

l 统计当前文件夹下面.jpg文件的数量：ls -l | grep '.*.jpg' | wc -l

l 计算当前文件夹的大小：du -sh

75. 描述一下随机森林

76. 随机森林主要用于解决什么类的问题？

77. 实习经历中提到了数据清洗，讲解一下清洗的工作是怎么做的？

78. 梯度爆炸和梯度消失怎么解决

造成梯度消失和梯度爆炸问题是网络太深，网络权值更新不稳定造成的，本质上是因为梯度反向传播中的连乘效应。另外一个原因是当激活函数使用 sigmoid 时，梯度消失问题更容易发生，因此可以考虑的解决方法如下：

\1. 压缩模型层数

\2. 改用其他的激活函数如 ReLU

\3. 使用 BN 层

\4. 使用类似ResNet的shortcut连接结构

79. C++程序编译过程

需要编译和链接

编译就是把文本形式源代码翻译为机器语言形式的目标文件的过程。

链接是把目标文件、操作系统的启动代码和用到的库文件进行组织，形成最终生成可执行代码的过程。

从图上可以看到，整个代码的编译过程分为编译和链接两个过程，编译对应图中的大括号括起的部分，其余则为链接过程。

编译过程

编译过程又可以分成两个阶段：编译和汇编。

编译

编译是读取源程序（字符流），对之进行词法和语法的分析，将高级语言指令转换为功能等效的汇编代码，源文件的编译过程包含两个主要阶段：

编译预处理

读取c源程序，对其中的伪指令（以# 开头的指令）和特殊符号进行处理。

伪指令主要包括以下四个方面：

链接过程

由汇编程序生成的目标文件并不能立即就被执行，其中可能还有许多没有解决的问题。

例如，某个源文件中的函数可能引用了另一个源文件中定义的某个符号（如变量或者函数调用等）；在程序中可能调用了某个库文件中的函数，等等。所有的这些问题，都需要经链接程序的处理方能得以解决。

链接程序的主要工作就是将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。

根据开发人员指定的同库函数的链接方式的不同，链接处理可分为两种：

静态链接

在这种链接方式下，函数的代码将从其所在的静态链接库中被拷贝到最终的可执行程序中。这样该程序在被执行时这些代码将被装入到该进程的虚拟地址空间中。静态链接库实际上是一个目标文件的集合，其中的每个文件含有库中的一个或者一组相关函数的代码。

动态链接

在此种方式下，函数的代码被放到称作是动态链接库或共享对象的某个目标文件中。链接程序此时所作的只是在最终的可执行程序中记录下共享对象的名字以及其它少量的登记信息。在此可执行文件被执行时，动态链接库的全部内容将被映射到运行时相应进程的虚地址空间。动态链接程序将根据可执行程序中记录的信息找到相应的函数代码。

对于可执行文件中的函数调用，可分别采用动态链接或静态链接的方法。使用动态链接能够使最终的可执行文件比较短小，并且当共享对象被多个进程使用时能节约一些内存，因为在内存中只需要保存一份此共享对象的代码。但并不是使用动态链接就一定比使用静态链接要优越。在某些情况下动态链接可能带来一些性能上损害。

GCC的编译链接

我们在linux使用的gcc编译器便是把以上的几个过程进行捆绑，使用户只使用一次命令就把编译工作完成，这的确方便了编译工作，但对于初学者了解编译过程就很不利了，下图便是gcc代理的编译过程：

预编译

将.c 文件转化成 .i文件

使用的gcc命令是：gcc –E

对应于预处理命令cpp

编译

将.c/.h文件转换成.s文件

使用的gcc命令是：gcc –S

对应于编译命令 cc –S

汇编

将.s 文件转化成 .o文件

使用的gcc 命令是：gcc –c

对应于汇编命令是 as

链接

将.o文件转化成可执行程序

使用的gcc 命令是： gcc

对应于链接命令是 ld

总结起来编译过程就上面的四个过程：预编译处理(.c) －－> 编译、优化程序（.s、.asm）－－> 汇编程序(.obj、.o、.a、.ko) －－> 链接程序（.exe、.elf、.axf等）。

总结

一般情况下，我们只需要知道分成编译和链接两个阶段，编译阶段将源程序（*.c) 转换成为目标代码（一般是obj文件，至于具体过程就是上面说的那些阶段），链接阶段是把源程序转换成的目标代码（obj文件）与你程序里面调用的库函数对应的代码连接起来形成对应的可执行文件（exe文件）就可以了，其他的都需要在实践中多多体会才能有更深的理解。

80. Bundle Adjustment

BA的思想就是根据视觉图像同时估计相机位姿和空间点位置，通过构造相应的最小二乘问题进行优化求解，又由于SLAM问题天然适合使用图优化表示，因此往往是使用图优化的方式进行优化求解。甚至我们可以称BA为带有相机位姿和空间点的图优化。

81. hessian矩阵为何稀疏

稀疏性指的是H矩阵的稀疏性，而考虑海塞矩阵由

clip_image041.png

计算得到，因此H矩阵的稀疏性直接来源于雅克比矩阵J。J矩阵中含有大量的0项，为什么呢？考虑J矩阵是代价函数e对相机位姿和路标点进行求导得到的，而一个相机位姿在一个时刻看到的路标点是少数有限个，因此求导后J矩阵含有很多0项，具体一点以代价函数的

clip_image043.png

分量为例，其对应的J仅有两个非0项，组合之后的J自然非0项也很少，因此H矩阵是非常稀疏的。

Hessian矩阵判断

（1）如果是正定矩阵，则临界点处是一个局部极小值

（2）如果是负定矩阵，则临界点处是一个局部极大值

（3）如果是不定矩阵，则临界点处不是极值

实二次型矩阵为正定二次型的判断方法

判断一个矩阵是否是正定方法：

1、顺序主子式：实对称矩阵为正定矩阵的充要条件是的各顺序主子式都大于零。

2、特征值：矩阵的特征值全大于零，矩阵为正定。矩阵的特征值全小于零，矩阵为负定。否则是不定的。

82. 关于边缘化

83. 在滑动窗口中的应用

84. ORBSLAM中的回环

https://zhuanlan.zhihu.com/p/61850005

85. TCP UDP区别

86. 什么时候进程会被阻塞

87. DBoW2利用 K叉树的好处是什么呢？主要是加速。

可以加速判断一个特征属于哪个单词。如果不使用K叉树，就需要与每个单词比较（计算汉明距离），共计需要比较

clip_image063.png

次。而使用K叉树之后，需要的比较次数变为

clip_image065.png

次。大大提高了速度。这里利用了K叉树的快速查找特性。
DBoW中存储了Direct Index，也就每个节点存储有一幅图像上所有归属与该节点的特征的index。在两帧进行特征匹配的时候，只需要针对每一个节点进行匹配就好了，大大缩小了匹配空间，加速了匹配速度。ORB-SLAM帧间匹配都使用了这个trick。
除此之外，如下图，DBoW的每个单词中还存储了Inverse index，每个Inverse Index中存储有所有有此单词的图像index，以及对应的权重：

在进行闭环搜索的时候，可以加快搜索过程的。具体的，我们只需要找与当前关键帧有相同单词的关键帧就可以了。

88. DBoW2是如何计算相似分数的。

在构建词典的时候，使用了大量的数据。在这个环境中有的单词出现的次数多，有的单词出现的少。直观想一下，出现次数多的单词其实对环境不具有区分度，反而出现次数少的单词很有区分性。比如一个单词叫做“地砖”，环境中很多，用这个单词来比较两幅图像的话就不能显著区分两个环境。因此，引入一个TF-IDF（Term Frequency-Inverse Document Frequency）的权重，来降低这种单词的作用。

为该单词出现的次数，ni为所有单词的总次数。（注：这里说的是训练过程，词典构建过程。）明显的， ni越大，权重越小。

至此词典就构建OK了：一个K叉树，两个index（Inverse index，Direct Index），一个权重（TF-IDF）。

下面开始使用词典比较图像相似度。将一幅图像A的所有特征转换为词袋向量，这里不仅仅要考虑单词有无的问题，还要考虑单词的权重。A中有的单词多，有的单词少。单词多自然要加大权重，单词少自然要减少权重啦。引入另一个权重叫做TF（Term Frequency）

[图片上传失败...(image-7d513a-1596547753169)]

89. ORB-SLAM中的回环

ORB-SLAM维护了一个数据库，这个数据库里面保存了每个单词能看到的关键帧。（inverse index）。每个关键帧都要从这个数据库中检测回环，检测完回环之后，每个关键帧都会加入到这个数据库中。当一个关键帧被删除之后，这个数据库也会被同时更新。这样做的好处就是加快回环搜索的速度，这个与DBoW的inverse index是相同的思想，只不过ORB-SLAM自己去维护了以下而已。

2.1 搜索闭环候选帧

下面进入正式的流程，因为ORB-SLAM使用了共视图，很多操作都可以采用共视图辅助。

做了降频，要求闭环与闭环之间至少经过10个关键帧。
计算一个相对分数minsocre：计算当前帧与其共视图中的帧的相似分数，取其中最小的那个作为minsocre。因为DBoW计算出的绝对分数不具有可比性，取当前帧与共视帧之间最小的相似度作为基准，如果大于这个基准才有可能是闭环帧。
从上文中说的数据库中查找闭环候选帧。

因为数据库中维护了Inverse Index，所以可以快速找到与当前帧有共同单词的关键帧。其中就会有一个关键帧具有的共同单词数最大，为maxcommonwords。根据这个设一个阈值，mincommons = 0.8 * maxcommonwords，据此去掉共同单词太少的候选关键。再加上minscore的要求干掉一部分关键帧。再再加上候选帧不能在当前帧的共视图中的条件，又干掉一部分。之后，把相连的的候选帧归为一组，每个组计算一个累加分数，可以找到一个最大分数bestAccScore。据此，设置一个阈值，minScoreToRetain = 0.75*bestAccScore。用这个阈值干掉一部分分组，这样可以干掉一些孤立的闭环帧候选帧（孤立的可能都是错误的闭环）。剩下的这些分组中的关键帧就是闭环候选帧啦。
连续性检测。现在，进一步对候选关键帧进行筛选。闭环不仅仅是单帧对单帧的匹配，好的闭环应该是多帧对多帧的闭环。也就是形成连续闭环，如下图所示。

[图片上传失败...(image-eacd41-1596547753169)]

至此可以得到若干的比较可靠的候选关键帧了：mvpEnoughConsistentCandidates。上面那么多的步骤，都是为了保证准确率。SLAM中要求闭环的准确率达到100%。

2.2 几何校验，sim3

下面，还要进行几何校验。对每一个候选帧与当前帧计算Sim3变换。

l 匹配当前帧与闭环帧之间的特征点，利用DBoW加速一下（Direct Index的应用），匹配太少的候选帧直接就干掉了。

l 计算一个Sim3初值。

l 利用Sim3初值将候选关键帧的地图点再投影到当前帧，得到更多匹配。

l 然后优化Sim3. 第2-4步是在RANSAC框架下做的，只要有一个帧通过了测试，就跳出去了。这样就选出了一个闭环帧。

l 把闭环帧的共视关键帧全部取出来，形成了局部地图，把局部地图点再投到当前帧匹配，又形成了更多的匹配。检查一下匹配点的数量来确定是否接受此次闭环。

l 至此，已经找到了一个闭环帧，并且计算出了当前帧与闭环帧之间的Sim3变换。

2.3 Loop fusion

下面要去做Loop fusion：调整关键帧位姿，更新共视图。

首先，把当前帧和当前帧的相邻帧（共视帧&共视帧的共视帧），根据前面的Sim3变换对齐到闭环帧上。这样做的好处是可以迅速把相机拉回到闭环位姿，并且把局部地图也拉回去了，可以保证定位的连续性。

然后，更新共视图关系，把闭环帧和闭环帧的共视帧上的地图点投影到当前帧上来。进行地图点融合，匹配，更新共视帧。

上面的步骤其实就是把当前帧的局部地图和闭环帧的局部地图缝合起来。

2.4 优化

接下来，就要开始优化啦。

首先基于Essential graph优化一下，然后再来一个全局BA。

90. Orbslam初始化策略

ORB-SLAM提出一种自动初始化流程，能够根据场景自动的选择模型（Homography or Fundamental），当初始化质量不好的时候则延迟初始化。

初始化流程

Step 0. 选定一个参考帧，提取ORB特征

选择标准：提取到的ORB特征数量足够多>100个

Step 1. 匹配当前帧与参考帧的ORB特征

当前帧提取的特征数量足够多>100，否则回到第0步。

利用DBOW2的词袋加速特征匹配过程。

如果匹配点数太少<100，则回到第0步。

上面的条件通过之后，进行初始化

Step 2. 同步计算两个模型Homography和Fundamental

[图片上传失败...(image-fc641e-1596547753169)]

Step 3. 模型选择：Homography or Fundamental

计算比例：

[图片上传失败...(image-9cc52f-1596547753169)]

如果大于0.45就选择Homography为模型，否则就选择Fundamental为模型。

Step 4. 计算位姿和地图点

根据选择的模型恢复出相对位姿和3D地图点。

Step 5. Bundle Adjustment.

最后在来一个BA。

这里有几个关键点：1. 如何估计单应矩阵、基础矩阵。2. 如何从单应矩阵和基础矩阵中分解出旋转R和平移t。

91. 由F分解R与T

[图片上传失败...(image-407a9c-1596547753169)] 下面根据Essential Matrix分解出R和t。我们知道E的成分有一个反对称矩阵S和一个正交矩阵R，外加一个scale组成。

[图片上传失败...(image-918f2e-1596547753169)]

实际上只有5个自由度。s可以放到反对称矩阵里面。

先给出两个矩阵

[图片上传失败...(image-ab1550-1596547753169)]

W为正价矩阵，Z为反对称矩阵。

对E进行SVD分解为

[图片上传失败...(image-35bb2-1596547753169)]

然后根据：

点在相机的前面，重投影误差足够小，恢复3D点。
根据恢复出3D点的多少来找一个最优解。
如果有多个最优解则放弃这次计算。
如果只有一个最优解，且恢复出了足够的3D点，并且有足够的视差（这里用的是地图点指向两个帧的夹角）就接收。

92. 由单应矩阵H恢复出R和t

按照ORB-SLAM的做法，可以恢复8个解，然后从8个解中选择一个最优解。

然后根据恢复出的3D点个数，视差等信息筛选出最优解，要求

最优个数 > 0.7 次优个数
最优的视差，大于最小要求的视差
最优的个数，大于最小设置的个数
最优个数，大于匹配点个数*0.9

93. EPNP算法

https://www.zybuluo.com/snuffles/note/1454799

94. DLT算法

https://zhuanlan.zhihu.com/p/58648937

95. NLS 问题之鲁棒代价函数(robust cost function)处理外点

96. 实现一个计时类，可以用来为程序运行时间计时

#include<iostream>
#include<chrono>
using namespace std;
using namespace std::chrono;

class Timer{
public:
    void start(){ _startpoint = high_resolution_clock::now();}
    void end(){_stoppoint = high_resolution_clock::now();}
    template<typename span>
    auto delta() const{return duration_cast<span> (_stoppoint-_startpoint).count();}
private:
    time_point<high_resolution_clock> _startpoint;
    time_point<high_resolution_clock> _stoppoint;
}