柠檬微趣一面凉经

秋招的第一个面试，被狠狠拷打了。菜鸡哭泣

笔试题是四道编程

1.求解格雷码

2.单链表两两交换

3.二叉树闭合空间数量

4.protocol buffer序列化与反序列化

a了三道半

面试先拷问没a出来的第四题的思路与细节。（一定要复盘笔试尤其是没做出来的情况下

1.补码的作用

避免零在二进制中的歧义。另一个好处就是方便运算，所有运算都能用加法运算器来实现，不再需要减法运算器。

2.逻辑位移和算数位移

逻辑位移是无脑移位空出来补0，算术移位就需要分有符号型值和无符号型值，对于无符号型值，算术移位等同于逻辑移位。而对于有符号型值，算术左移等同于逻辑左移，算术右移补的是符号位，正数补0，负数补1。

3.浮点数表示形式

对于定点整数而言由于小数点固定，那么在字长一定的情况下就限制了可以表示数的范围和精度，所以就引出了浮点数据表示。

浮点数表示法是指以适当的形式将比例因子表示在数据中，让小数点的位置根据需要而浮动。这样，在位数有限的情况下，既扩大了数的表示范围，又保持了数的有效精度。

参考：https://zhuanlan.zhihu.com/p/400006735

5. const static inline

三个关键字的作用

https://www.cnblogs.com/cpsmile/p/9032397.html

6.C++面向对象的多态性是如何实现的

多态是同一个行为具有多个不同表现形式或形态的能力。多态就是同一个接口，使用不同的实例而执行不同操作.多态性是允许你将父对象设置成为和一个或更多的他的子对象相等的技术，赋值之后，父对象就可以根据当前赋值给它的子对象的特性以不同的方式运作。简单一句话：允许将子类类型的指针赋值给父类类型的指针实现多态有二种方式：覆盖（override），重载（overload）。

**覆盖：**是指子类重新定义父类的虚函数的做法。**重载：**是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同）

多态的优点

消除类型之间的耦合关系
可替换性
可扩充性
接口性
灵活性
简化性

多态存在的三个必要条件1.继承2.重写3.父类引用指向子类对象当使用多态方式调用方法时，首先检查父类中是否有该方法，如果没有，则编译错误；如果有，再去调用子类的同名方法。

多态的好处：可以使程序有良好的扩展，并可以对所有类的对象进行通用处理。

OO开发范式大致为：划分对象→抽象类→将类组织成为层次化结构(继承和合成) →用类与实例进行设计和实现几个阶段。

7.构造函数、析构函数、static成员函数能否被设置为虚函数

构造函数不能为虚函数，而析构函数可以是虚函数并且在实现多态特性是应该被设置为虚函数。

static成员函数不能是虚函数。

虚函数：

那些被virtual关键字修饰的成员函数，就是虚函数。虚函数的作用：用专业术语来解释就是实现多态性（Polymorphism），多态性是将接口与实现进行分离；用形象的语言来解释就是实现以共同的方法，但因个体差异，而采用不同的策略。

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

具有构造函数的类对象被创建时，编译系统为该对象分配内存空间，并自动调用该构造函：即由构造函数完成数据成员的初始化工作。

从存储空间角度来看虚函数的调用需要，而该指针存放在对象的内存空间中，在构造函数中进行初始化工作，即初始化vptr，让它指向正确的虚函数表。所以需要调用构造函数才可以创建或初始化它的值，否则即使开辟了空间，该指针也为随机值；若构造函数声明为虚函数，那么由于对象还未创建，还没有内存空间，更没有虚函数表地址用来调用虚函数——构造函数了。
从多态角度来看构造一个对象的时候，必须知道对象的实际类型；而虚函数主要是实现多态，在运行时才可以明确调用对象，根据传入的对象类型来调用函数，例如通过父类的指针或者引用来调用它的时候可以变成调用子类的那个成员函数。而　在调用构造函数时，由于对象还未构造成功。编译器无法知道对象的实际类型，是该类本身，还是该类的一个派生类，或是更深层次的派生类。

构造函数不能是虚函数，因为虚函数是基于对象的，构造函数是用来产生对象的，若构造函数是虚函数，则需要对象来调用，但是此时构造函数没有执行，就没有对象存在，产生矛盾，所以构造函数不能是虚函数。

析构函数函数为什么最好是虚函数？

析构函数可以为虚函数，而且当要使用基类指针或引用调用子类时，最好将基类的析构函数声明为虚函数，否则会存在内存泄露的问题。【内存泄漏：析构函数是虚函数，因为若有父类指针指向子类对象存在，需要析构的是子类对象，但父类析构函数不是虚函数，则只析构了父类，造成子类对象没有及时释放，引起内存泄漏。】

静态成员函数为什么不能是虚函数？

静态成员函数不属于类中的任何一个对象和实例，属于类共有的一个函数。也就是说，它不能用this指针来访问，因为this指针指向的是每一个对象和实例。

对于virtual虚函数，它的调用恰恰使用this指针。在有虚函数的类实例中，this指针调用vptr指针，指向的是vtable(虚函数列表)，通过虚函数列表找到需要调用的虚函数的地址。总体来说虚函数的调用关系是：this指针->vptr(4字节）->vtable ->virtual虚函数。

所以说，static静态函数没有this指针，也就无法找到虚函数了。所以静态成员函数不能是虚函数。他们的关键区别就是this指针。

构造函数不能为const函数，构造函数的目的就是为了给成员变量赋初值，不能为const函数

8.简单描述一下快排

快速排序是对冒泡排序算法的一种改进，同冒泡排序一样，快速排序也属于，通过元素之间的比较和交换位置来达到排序的目的。不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序，这种思路就叫做分治法。

快速排序是基于“分治法”原理实现，所谓分治法就是不断的将原数组序列按照一定规律进行拆分，拆分后各自实现排序直到拆分到序列只剩下一个关键字为止。快速排序首先选取一个关键字为标志位（关键字的选取影响排序效率），然后将序列中小于标志位的关键字移动至标志位左侧，大于标志位的关键字移动至右侧。一趟比较完成后，整个序列以选取的标志位为界，左侧均小于标志位，右侧均大于关键字。但左右两侧内部并不是有序的(左右两侧关键字个数也不一定相同)。进而继续将左右两侧分别再以这种方式进行排序，直到将序列拆分的剩余一个关键字为止，整个序列即变成有序。