西加加后台开发面试总结

C++后台开发的一些知识点,尽可能补全一点,无限更新中。

C/C++语言基础

extern关键字作用

  1. extern可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中,提示编译器遇到此变量和函数时在其他模块中寻找其定义。
  2. 可以进行连接指定。

static关键字作用

  1. static修饰局部变量,使得其成为静态变量,存储在静态区,静态区的数据生命周期和程序相同,main函数之前初始化,程序退出时销毁。
  2. static修饰全局变量,全局变量本来就在静态区,所以并没有改变其存储位置,但是,static会限制其链接属性,被static修饰的全局变量智能被该包含该定义的文件访问。
  3. static修饰函数,使得函数只能在半酣该函数定义的文件中被调用。如果static函数定义在头文件中,则每一个包含该头文件的文件都实现了一个fun函数,因此static实现了不同文件中定义同名的函数而不发生冲突。
  4. 在C++中,对于静态成员变量和静态成员函数,所有的对象都只维持一个同一个实例,因此,采用static可以实现不同对象之间数据共享。

volatile关键字

用这个关键字声明的变量,每次访问,都会去相应的内存单元取值,也就是说,即使寄存器中有备份,也不会访问,部分编译器会对代码进行优化,频繁访问的变量会自动去寄存器中访问,毕竟访问寄存器的速度要比内存快得多。

const的作用

  1. 限定变量为不可修改
  2. 限定成员函数不可以修改任何数据成员
  3. const与指针:const char *p 表示指向的内容不能改变;char* const p,将p声明为常指针,地址不能改变,是固定的,但内容可以改变。

new/delete和malloc/free的区别

  1. malloc和free是库函数,而new和delete是C++操作符。
  2. new可以自定计算需要的空间大小,而malloc需要指定。
  3. new在动态分配时自动调用构造函数,delete释放内存时调用析构函数,而malloc只管分配,不会初始化。
  4. new是C++操作符,是关键字,而operate new是C++库函数。
  5. operator new / operator delete可以重载,而malloc不行。
  6. new可以调用malloc来实现,反过来不行。
  7. malloc可以直观地重新分配内存。

C++多态性和虚函数表

  1. 封装可以使得代码模块化,继承可以扩展已经存在的代码,这两者都是为了代码重用,而多态的目的则是为了接口重用,也就是说,不论传递过来的究竟是哪个类的对象,函数都能够通过同一个接口调用到适应各自对象的实现方法。常见用法是声明一个基类的指针,利用该指针指向任意一个子类对象,调用相应的虚函数,可以根据指向的子类的不同而实现不同的方法。如果没有使用虚函数的话,即没有利用C++多态性。
  2. 虚函数在设计上还具有封装和抽象的作用,比如抽象工厂模式。
  3. 动态多态的设计思想:对于相关的对象类型,确定它们之间的一个共同功能集,然后在基类中,把这些共同的功能声明为多个公共的虚函数接口。各个子类重写这些虚函数,以完成具体的功能。客户端的代码通过指向基类的引用或指针来操作这些对象,对虚函数的调用会自动绑定到实际提供的子类对象上去。优点:实现与接口分离,可以复用;处理同一继承体系下异质对象集合的强大威力。缺点:运行期绑定,导致一定程度的运行时开销。编译器无法对虚函数进行优化。笨重的类继承体系,对接口的修改影响整个类层次。
  4. 静态多态的设计思想:对于相关的对象类型,直接实现它们各自的定义,不需要共有基类,甚至可以没有任何关系。只需要各个具体类的实现中要求相同的接口声明。客户端把操作这些对象的函数定义为模板,当需要操作什么类型的对象时,直接对模板置顶该类型实参即可。优点:静态多态在编译时完成,因此效率较高,编译器也可以进行优化。有很强的适配性和松耦合性,可以通过偏特化、全特化来处理特殊类型。最重要的一点是静态多态通过模板编程为C++带来了泛型设计的概念,比如强大的STL库。缺点:由于是模板来实现的静态多态,由此模板的不足也就是静态多态的劣势,比如调试困难、编译耗时、代码膨胀、编译器支持的兼容性,不能够处理异质对象集合。

动态绑定

虚函数表是属于类的,而不是属于某个具体的对象,虚表的指针属于对象。动态绑定的实现依赖着虚表和虚函数,执行函数的动态绑定需要以下三个条件:

  1. 通过指针来调用函数
  2. 指针upcast向上转型(继承类向基类的转换成为upcast)
  3. 调用的是虚函数

虚函数和纯虚函数的选择

  1. 当基类中的某个成员方法,在大多数情形下都应该由子类提供个性化实现,但基类也可以提供缺省备选方案的时候,该方法应该设计成虚函数。
  2. 当基类中的某个成员方法,必须由子类提供个性化实现的时候,应该设计为纯虚函数。

指针和引用的区别

  1. 指针是一个变量,只不过变量存储的是一个地址,指向内存的一个存储单元;而引用跟原来的变量实质上是同一个东西,只不过是原变量的一个别名。
  2. 可以有const指针,但是没有const引用。
  3. 指针可以有多级,但引用只能是一级。
  4. 指针的值可以是空,但引用不能。
  5. 指针的值可以改变,而引用在进行初始化之后就不会再改变了。

内联函数

  1. 用inline关键字即可将函数定义为内联函数,当调用该函数时,编译器直接将函数的定义体来替换函数,而不是按照常规的函数调用那样压栈保存返回地址等一系列操作,这是建立在函数体十分短小简洁的前提下,相对于调用函数的时间来讲执行时间很短,如果函数体本身十分庞大复杂、执行时间较长,编译器将忽略内联定义作为普通函数处理。
  2. 虚函数不允许内联。
  3. 与宏不同,宏是强制的内联展开,可能会污染命名空间和代码,为程序的调试带来困难。

Map和Set

Map和Set都是关联容器,Map基于红黑树的结构实现,以键值对的形式进行存储,方便进行查找,关键字起到索引的作用;Set基于红黑树的平衡二叉检索树结构实现,支持高效插入删除,插入元素的时候会自动调整二叉树的结构,维持平衡。

数据结构与算法

Hash表

  1. 常见的解决冲突的方法有:开放定址法,链地址法,建立公共溢出区等。

  1. 二叉树的性质:第i层结点数最多为2^(i - 1);高度为k的二叉树其结点总数最多为2^k-1;对于任意非空二叉树T,如果叶结点个数为n0,其度为2的结点数为n2,则:n0 = n2 + 1。
  2. 满二叉树:深度为k且有2^k - 1个结点的二叉树成为满二叉树。
  3. 完全二叉树:深度为k的,有n个结点的二叉树,当且仅当其每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应,称之为完全二叉树。
  4. 具有n个结点的完全二叉树的深度为log2n + 1。
  5. 仅有前序和后序遍历,不能确定一个二叉树,必须有中序遍历的结果。
  6. 二叉排序树:左子树结点的值小于根结点的值,右子树结点的值大于根结点的值,没有键值相等的结点,平均时间复杂度是O(long(n)),最坏是O(n)。
  7. 平衡二叉树:又称为AVL树,左子树和右子树都是平衡二叉树,左子树和右子树的深度之差的绝对值不超过1。
  8. 红黑树:结点为红色或者黑色;根结点为黑色;从根结点到每个叶结点经过的黑色结点个数完全相同;父结点为红色的花子结点不能为红色。 红黑树是在平衡二叉树的严格平衡基础上,采取一定的方法,不追求“完全平衡”——它只要求部分地达到平衡要求,降低了对旋转的要求,从而能够提高性能。只是查找代价略逊色于AVL树,插入和删除的效率都将提升。
  9. B~树:是一种非二叉的查找树,满足以下结构特性:一颗m阶的B~树;树的根或者是一片叶子(一个结点的树),或者其儿子数在2和m之间;除根外,所有的非叶子结点的孩子数在m/2和m之间;所有的叶子结点都在相同的深度。平均深度为logm/2(N),执行查找的平均时间为O(logm)。
  10. 字典树(Trie):又称为单词查找树或者键树,是一种树型结构,哈希树的变种,典型应用是用于统计和排序大量的字符串(但不仅限于字符串),经常被搜索引擎系统用于文本词频统计。优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表还要高,插入和查询的时间复杂度均为O(k),核心思想是以空间换时间。

链表

  1. 链表的插入和删除,单向和双向都要会。
  2. 反向打印链表(递归)。
  3. 打印倒数第K个结点(前后指针)。
  4. 链表是否有环(快慢指针)。

栈和队列

  1. 栈和队列的区别:栈是先进后出,队列是先进先出,栈应该注意栈是否已满和为空的特殊情况,队列一般只要判空,栈一般应用于回文判断、迷宫问题,表达式的求值,函数调用和递归实现等场景,而队列大多应用于计算机系统中各种资源的管理,消息缓冲器的管理和广度优先搜索遍历等等。

海量数据问题

  1. 分而治之/hash映射+hash统计+堆/快排/归并排序。
  2. Trie树/数据库/倒排索引。
  3. 外排序。
  4. 分布式处理Hadoop/Mapresuce。

网络与TCP/IP

TCP与UDP的区别

  1. TCP基于有连接,UDP基于无连接。有连接即TCP在传输前会先发送连接请求和应答包,保证能够正常通信后,才会进行数据传输。无连接就是在发送数据之前,并不考虑对方能否收到。
  2. TCP能保证可靠传输,UDP不能保证可靠传输。
  3. TCP结构复杂,消耗资源多,建立过程相对要慢要复杂。UDP结构简单,消耗资源少,建立过程比较快。
  4. TCP基于流模式,UDP是数据报模式。TCP把数据堪称一连串无结构的字节流,没有边界,一段段传输构成整个数据块。通过发送缓冲区和接受缓冲区来存储数据流。而UDP数据报模式,每一个数据包都是一个独立的对象,有着指定的大小。
  5. TCP有确认,重传,拥塞控制机制,UDP在没有建立连接或者对方已经推出的情况下依然会继续发送数据,导致通信流量的浪费。

TCP的三次握手和四次挥手

建立连接——三次握手

  1. 客户端发送一个SYN来创建连接,随机序号为A。
  2. 服务端收到消息后,发送确认号ACK=A+1,并发回给客户端一个SYN,随机序号为B。
  3. 客户端收到后,再发送一个ACK,确认号为A+1,响应为B+1。

断开连接——四次挥手

  1. 客户端发送一个FIN=1的数据分段,进入FIN-WAIT状态,不再发送数据,只接受数据。
  2. 服务端收到FIN=1的数据分段后,发送一个带有ACK=1的剩余数据分段,告诉客户端,我收到了你的FIN=1的数据分段。
  3. 等到服务端将剩余数据全部发送完毕,即发送FIN=1的数据分段,进入CLOSE-WAIT状态,等待客户端的确认。
  4. 客户端收到服务端的FIN=1数据分段后,返回ACK=1报文进行确认,为了防止服务器没有收到,暂时进入TIME-WAIT状态。服务器收到报文后即关闭连接,客户端等待2MSL没收到回复即默认服务端已经关闭,于是客户端关闭。

TCP拥塞控制

判断拥塞出现的条件:网络中出现分组丢失。

用到的拥塞避免算法:慢启动、快速重传、快速恢复。

需要维持的两个变量:拥塞窗口和慢启动阈值。

HTTP

http2.0的特点

  1. 采用二进制格式而不是文本格式。
  2. 是完全多路复用的,而非有序并阻塞的。
  3. 报头进行了亚索,降低了开销。
  4. 服务器可以将响应主动“推送”到客户端缓存中。

###get/post区别

  1. 实质上来说,可以没有区别,都是TCP包,所谓的区别都是因为大家的约定俗称的使用规则以及服务器和浏览器的限定跟HTTP的规定而确定下来的。
  2. GET会把http header和data一并发送出去,服务器直接返回200.而POST,浏览器会先发送header,服务器相应100后继续,浏览器再发送data,服务器响应200ok返回数据。
  3. GET请求参数会被完整保留在浏览器历史记录里,而POST中的参数不会被保留。
  4. GET请求在URL中传送的参数是有长度限制的,而POST没有。
  5. GET参数通过URL传递,POST放在Request body中。

状态码

  1. 100 (继续) 请求者应当继续提出请求。 服务器返回此代码表示已收到请求的第一部分,正在等待其余部分。

    101 (切换协议) 请求者已要求服务器切换协议,服务器已确认并准备切换。

  2. 200 (成功) 服务器已成功处理了请求。 通常,这表示服务器提供了请求的网页。

    201 (已创建) 请求成功并且服务器创建了新的资源。

    202 (已接受) 服务器已接受请求,但尚未处理。

    203 (非授权信息) 服务器已成功处理了请求,但返回的信息可能来自另一来源。

    204 (无内容) 服务器成功处理了请求,但没有返回任何内容。

  3. 300 (多种选择) 针对请求,服务器可执行多种操作。 服务器可根据请求者 (user agent) 选择一项操作,或提供操作列表供请求者选择。

    302 (临时移动) 服务器目前从不同位置的网页响应请求,但请求者应继续使用原有位置来进行以后的请求。

    303 (查看其他位置) 请求者应当对不同的位置使用单独的 GET 请求来检索响应时,服务器返回此代码。

    304 (未修改) 自从上次请求后,请求的网页未修改过。 服务器返回此响应时,不会返回网页内容。

  4. 400 (错误请求) 服务器不理解请求的语法。

    401 (未授权) 请求要求身份验证。 对于需要登录的网页,服务器可能返回此响应。

    403 (禁止) 服务器拒绝请求。

    404 (未找到) 服务器找不到请求的网页。

    406 (不接受) 无法使用请求的内容特性响应请求的网页。

    407 (需要代理授权) 此状态代码与 401(未授权)类似,但指定请求者应当授权使用代理。

    408 (请求超时) 服务器等候请求时发生超时。

  5. 500 (服务器内部错误) 服务器遇到错误,无法完成请求。

    501 (尚未实施) 服务器不具备完成请求的功能。 例如,服务器无法识别请求方法时可能会返回此代码。

    502 (错误网关) 服务器作为网关或代理,从上游服务器收到无效响应。

    503 (服务不可用) 服务器目前无法使用(由于超载或停机维护)。 通常,这只是暂时状态。

    505 (HTTP 版本不受支持) 服务器不支持请求中所用的 HTTP 协议版本。

浏览器中输入一个URL用到哪些协议

DNS协议,UDP协议(DNS服务器基于UDP),http协议,TCP协议,IP协议,ARP协议。

安全相关

SQL注入

SQL注入发生在应用程序与数据库之间,由于输入的字符串没有进行严格的检查和过滤,别有用心的人会在其中注入SQL指令,使得数据库服务器将其误认为正常的SQL指令而运行,造成破坏或者入侵。一般发生原因都是权限过高和SQL指令组合不当。

XSS

跨站脚本攻击,攻击者在王页可以输入的地方通过巧妙的方法注入恶意指令,使永无加载并执行攻击者恶意知道的网页程序,一般这些程序都是JavaScript,攻击成功后,攻击者可以得到更高的权限,拿到会话和cookie等内容。这里利用的是用户对指定网站的信任。

CSRF

跨站请求伪造,挟持用户在纪录当前已登陆的Web应用程序上执行非本意的操作的攻击方法,这里利用的是网站对用户网页浏览器的信任。

SYN洪水攻击

这个顾名思义,光发SYN不给ACK,典型的Dos攻击。

ARP欺骗攻击

在ARP协议中有一个缺陷,请求主机在收到ARP应答包之后,不会去验证自己是否向对方主机发送锅ARP请求包,就直接把这个返回包中的IP地址与MAC地址的对应关系保存进ARP缓存表中,如果存在原有对应关系将会被替换。所以C只要假装是某主机给A发包,让A相信这是B的地址,就能达到欺骗A的目的了。

数据库

​ 学完一遍再总结吧。

Linux

进程与线程

进程和线程的区别

进程和线程是不同的CPU时间段,进程更大,线程要小一点。进程包括了上下文的切换,而线程之间是共享一个程序的上下文的。

线程跟进程比有什么优势

fork代价昂贵,要把所有父进程的内存映像拷贝到子进程,并在子进程中复制所有描述字等等,线程的创建要比进程快的多,且易于共享内存。