【面经】深信服C++

问题来自

https://leetcode-cn.com/circle/discuss/wKrAfK/

语言

1. strcpy 函数有什么缺陷，如何优化

   • 函数原型：char *strcpy(char *dest,const char *src);
   • 函数说明：strcpy 函数会将参数 src 字符串拷贝至参数 dest 所指的地址。
   • 如果参数dest所指的内存空间不够大，可能会造成缓冲溢出的错误情况
   • 优化：使用strncpy
   • 函数原型：char *strncpy(char *dest,const char *src ,size_t n);
   • 函数说明：strncpy会将参数src字符串拷贝前n个字符至参数dest所指的地址。
   • 需要手工末尾填’\0’，当dest长度远大于src时，由于strncpy会对多余的每个字节填0，会有很大的性能损失。

2. 指针和引用区别

   • 定义：指针是变量，存储地址，引用是原变量的一个别名，实际上是一个东西
   • 指针可以是多级，引用只能是一级
   • 指针在定义的时候可以不初始化，引用必须初始化
   • 指针可以指向NULL，引用不行

3. c++ 内存分区

   • 栈：编译器在需要的时候分配，不需要就自动清除的变量所在区域，栈是向低地址生长的连续区域
   • 堆：堆的分配由程序员控制，是不连续的，地址向高地址生长
   • 静态存储区：存放全局变量和静态变量的区域
   • 常量存储区：存放常量字符串的存储区，只能读不能写。const修饰的局部变量存储在常量区，const修饰的局部变量在栈区
   • 程序代码区：存放源程序二进制代码

4. 结构体字节对齐

   • 与结构体中定义的数据类型的顺序有关
   • 先取结构体中占用最长的数据类型的字节长度记为 m
   • 所有成员在分配内存时都是紧接在前一个变量后面依次填充的
   • 如果一行中剩下的空间不足以填充某成员变量，就另起一行，未被利用的空间随机填充

5. 未初始化的全局变量放在哪里，编译后在二进制文件中有它的位置吗

   • 已初始化的全局变量和局部静态变量都在__data段中
   • 未初始化的全局变量在__common段中
   • 未初始化的局部静态变量在__bss段中
   • 初始化为 0 也算未初始化
   • 一个程序本质上都是由 bss段、data段、text段三个组成的
   • bss段（bss segment）通常是指用来存放程序中未初始化的全局变量的一块内存区域
   • 数据段（data segment）通常是指用来存放程序中已初始化的全局变量的一块内存区域
   • 代码段（code segment/text segment）通常是指用来存放程序执行代码的一块内存区域
   • text和data段都在可执行文件中，由系统从可执行文件中加载
   • bss段不在可执行文件中，由系统初始化

6. 什么是野指针，怎么检测

   • 野指针主要是指对象释放后，指针未置空导致的野指针
   • 规避：初始化指针的时候将其置为nullptr，之后对其操作，释放指针的时候将其置为nullptr。
   • 检测：通过NSZombieEnabled

7. 智能指针有哪些，实现原理，如何防止循环引用

   • shared_ptr
   • unique_ptr
   • weak_ptr
   • 循环引用

     class B; // 前置声明
     class A {
     public:
         shared_ptr<B> ptr;
     };
     
     class B {
     public:
         shared_ptr<A> ptr;
     };
     
     int main(){
         while(true) {
             shared_ptr<A> pa(new A());
             shared_ptr<B> pb(new B());
             pa -> ptr = pb;
             pb -> ptr = pa;
         }
         return 0;
     }

   • class A和class B的对象各自被两个智能指针管理，也就是A object和B object引用计数都为2,在main函数中一个while循环结束的时候，pa和pb的析构函数被调用，但是class A对象和class B对象仍然被一个智能指针管理，A object和B object引用计数变成1，于是这两个对象的内存无法被释放，造成内存泄漏。
   • 用weak_ptr可以解决循环引用问题

8. 能够使用 memcmp 判断两个结构体存的东西是一样的吗

   • memcmp就是将两个变量在底层按字节进行比较，相等返回0
   • 有些能有些不能，和字节对齐有关
   • 字节对齐后没有被随机填充的字节就可以memcpy

9. sizeof 和 strlen 的区别

   • sizeof是一个操作符，而strlen是库函数
   • sizeof的参数可以是数据的类型，也可以是变量，而strlen只能以结尾为’\0’的字符串作参数
   • 编译器在编译时就计算出了sizeof的结果，而strlen必须在运行时才能计算出来
   • sizeof计算数据类型占内存的大小，strlen计算字符串实际长度

10. 用宏实现比较大小

    #define MAX(a,b) (((a)-(b)<=0)?(b):(a))
    #define MIN(a,b) (((a)-(b)<=0)?(a):(b))
    // 负数是用补码表示的，最高位是符号位，所以判断a-b的最高位是不是1就可以知道a-b是不是负数
    #define MAX(a,b) ( (((a)-(b)) & (1<<31) )>>31 ? (b):(a) ) 

11. new 和 malloc 区别，如何判断是否申请到内存

    • 申请的内存位置：new从自由存储区上申请，malloc从堆上申请
    • 返回类型安全：new 返回对象类型的指针，malloc 返回是 void*，需要强制转换
    • 内存分配失败的返回值：new会抛出bad_alloc异常，需要try_catch，malloc失败会返回NULL

      // C
      int * a = new int();if(NULL == a){ ...}else{ ...}

      // C++
      try{ 
          int *a = new int();
      }catch (bad_alloc){ 
          //...
      }

    • 指定内存大小：new无需指定内存大小，malloc需要指定

      class A{
          //...
      }
      A * ptr = new A;
      A * ptr = (A *)malloc(sizeof(A));

    • 是否调用构造函数/析构函数：new会经历分配空间，构造函数，返回对象的指针，delete的时候会调用析构函数，释放内存。malloc则不会。
    • 是否可以相互调用：new和delete的实现基于malloc和free，malloc和free的实现不可以调用new和delete
    • 是否可以被重载：new和delete可以，malloc和free不行
    • 是否能重新分配内存：malloc可以通过realloc来重新扩容，如果有连续的空间就原地扩容，否则另找一片复制过去。new则不行。

12. 函数模板与类模板的区别

    • 类模板没有自动类型推导的使用方式
    • 类模板的函数声明和实现都得在头文件中实现，不能像普通类一样.h中定义，在.cpp中实现
    • 函数模板允许隐式调用和显式调用而类模板只能显示调用

13. c++ 如何使用c实现的函数

    • 比如有这样的目录结构

      .
      |-- calc
      | |-- calc.c
      | `-- calc.h
      `-- main.cpp

    • 方案一：把calc.c改成calc.cpp
    • 方案二：

      #ifdef __cplusplus 
      extern "C" {
      #endif
      
      void fun1(int arg1); 
      void fun2(int arg1, int arg2); 
      void fun3(int arg1, int arg2, int arg3);
      
      #ifdef __cplusplus 
      }
      #endif

    • 方案三：若别人已经写好的头文件，我们无法修改，怎么办？重写一个专门被c++用的头文件即可
    • 编写头文件 cpp_calc.h

      extern "C" {
      #include "calc.h"; 
      }

14. 多态的原理

    • 当类中存在虚函数时，编译器会生成一个虚函数表，用于存储类中虚函数指针
    • 当父类型指针指向子类型对象的时候，在程序运行时，查找虚函数表，调用虚函数表里对应的函数，在表现上来看是多态

15. 虚函数的实现原理

    • 要点是要答出虚函数表和虚函数表指针的作用。C++中虚函数使用虚函数表和 虚函数表指针实现，虚函数表是一个类的虚函数的地址表，用于索引类本身以及父类的虚函数的地 址，假如子类的虚函数重写了父类的虚函数，则对应在虚函数表中会把对应的虚函数替换为子类的 虚函数的地址；虚函数表指针存在于每个对象中（通常出于效率考虑，会放在对象的开始地址处）， 它指向对象所在类的虚函数表的地址；在多继承环境下，会存在多个虚函数表指针，分别指向对应 不同基类的虚函数表。

16. 纯虚函数

    • 在函数原型后面加上 “= 0”
    • 含有纯虚拟函数的类称为抽象类，它不能生成对象，目的在于，使派生类仅仅只是继承函数的接口

17. 析构函数可以是虚函数吗，构造函数呢

    • 构造函数不能是虚函数，析构函数可以是虚函数且推荐最好设置为虚函数

18. 拷贝构造函数取引用的原因

    • 拷贝构造函数的const date d会对传入的d1进行实例化，调用自身，但被调用后又实例化，再次调用拷贝构造函数，形成无限递归，所以只能引用

19. 如何减少构造函数的开销

    • 成员初始化列表：在类构造函数中，不在函数体内对变量赋值，而在参数列表后，跟一个冒号和初始化列表。
    • 问：为什么成员初始化列表效率更高？
    • 答：因为对于非内置类型，少了一次调用默认构造函数的过程。
    • 利用std::move()转为右值

      class Student {
      public:
          explicit Student(std::string name)
                  : _name(std::move(name)) {}
      private:
          std::string _name;
      };

20. static、const的作用

    • static关键字的作用
      • 函数体内static变量的作用范围为该函数体，不同于auto变量，该变量的内存只被分配一次，因此其值在下次调用时仍维持上次的值
      • 在模块内的static全局变量可以被模块内所用函数访问，但不能被模块外其它函数访问
      • 在模块内的static函数只可被这一模块内的其它函数调用，这个函数的使用范围被限制在声明它的模块内
      • 在类中的static成员变量属于整个类所拥有，对类的所有对象只有一份拷贝
      • 在类中的static成员函数属于整个类所拥有，这个函数不接收this指针，因而只能访问类的static成员变量
    • const关键字至少有下列n个作用
      • 欲阻止一个变量被改变，可以使用const关键字。在定义该const变量时，通常需要对它进行初始化，因为以后就没有机会再去改变它了
      • 对指针来说，可以指定指针本身为const，也可以指定指针所指的数据为const，或二者同时指定为const
      • 在一个函数声明中，const可以修饰形参，表明它是一个输入参数，在函数内部不能改变其值
      • 对于类的成员函数，若指定其为const类型，则表明其是一个常函数，不能修改类的 成员变量
      • 对于类的成员函数，有时候必须指定其返回值为const类型，以使得其返回值不为“左值”

21. 静态局部变量和局部变量的区别

    • 静态局部变量在静态存储区分配空间，在程序整个运行期间都不释放，局部变量占用动态存储区的空间，函数调用结束后自动释放
    • 静态局部变量在编译的时候赋初值，并且只赋值一次，每次运行函数使用的是上一次调用结束的值，局部变量在每次调用的时候重新赋值
    • 虽然静态局部变量在函数调用后仍然存在，但是作用范围以外的区域不能使用

22. auto 类型推导的实现原理

    • auto变量的规则是”做函数模板需要做的事情”
    • auto被一个虚构的模板类型参数T替代，然后进行推断，即相当于把变量设为一个函数参数，将其传递给模板并推断为实参，auto相当于利用了其中进行的实参推断，承担了模板参数T的作用
    • auto在编译的时候确定

23. 如何判断结构体是否相等

    • 重载运算符 “==”

24. C++11 特性

    • auto/decltype
    • 右值引用和转移语义
    • 智能指针
    • 基于范围的for循环
    • 委托构造函数：允许在同一个类中一个构造函数调用另外一个构造函数

      struct A {
          A(){}
          A(int a) { a_ = a; }
      
          A(int a, int b) : A(a) { b_ = b; }
      
          A(int a, int b, int c) : A(a, b) { c_ = c; }
      
          int a_;
          int b_;
          int c_;
      };

    • 继承构造函数：可以让派生类直接使用基类的构造函数，如果有一个派生类，我们希望派生类采用和基类一样的构造方式，可以直接使用基类的构造函数，而不是再重新写一遍构造函数

      struct Base {
          Base() {}
          Base(int a) { a_ = a; }
      
          Base(int a, int b) : Base(a) { b_ = b; }
      
          Base(int a, int b, int c) : Base(a, b) { c_ = c; }
      
          int a_;
          int b_;
          int c_;
      };
      
      struct Derived : Base {
          using Base::Base;
      };
      
      int main() {
          Derived a(1, 2, 3);
          return 0;
      }

    • nullptr：nullptr是c++11用来表示空指针新引入的常量值，在c++中如果表示空指针语义时建议使用nullptr而不要使用NULL，因为NULL本质上是个int型的0，其实不是个指针。
    • final：用于修饰一个类，表示禁止该类进一步派生和虚函数的进一步重载

      struct Base final {
          virtual void func() {
              cout << "base" << endl;
          }
      };
      
      struct Derived : public Base{ // 编译失败，final修饰的类不可以被继承
          void func() override {
              cout << "derived" << endl;
          }
      
      };

    • override：用于修饰派生类中的成员函数，标明该函数重写了基类函数，如果一个函数声明了override但父类却没有这个虚函数，编译报错，使用override关键字可以避免开发者在重写基类函数时无意产生的错误

      struct Base {
          virtual void func() {
              cout << "base" << endl;
          }
      };
      
      struct Derived : public Base{
          void func() override { // 确保func被重写
              cout << "derived" << endl;
          }
      
          void fu() override { // error，基类没有fu()，不可以被重写
              
          }
      };

    • 内存对齐
    • 正则表达式：c++11引入了regex库更好的支持正则表达式

25. 函数指针和指针函数的区别

    • 指针函数是指带指针的函数，即本质是一个函数，函数返回类型是某一类型的指针

      float *fun();
      float *p;
      p = fun(a);

    • 函数指针是指向函数的指针变量，即本质是一个指针变量

      #include <iostream>
      
      void (*funcp1)(int a, int b);
      void FileFunc(int a, int b);
      void (*funcp2)();
      void EditFunc();
      
      int main(){
          funcp1 = FileFunc;
          (*funcp1)(2, 3);
          funcp2 = EditFunc;
          (*funcp2)();
      }
      
      void FileFunc(int a, int b){
          printf("FileFunc\n");
          printf("a + b = %d\n", a + b);
      }
      
      void EditFunc(){
          printf("EditFunc\n");
      }

26. 隐藏、重载、重写的区别

    • 重载：是指同一可访问区内被声明的几个具有不同参数列（参数的类型，个数，顺序不同）的同名函数，根据参数列表确定调用哪个函数，重载不关心函数返回类型。
    • 隐藏：是指派生类的函数屏蔽了与其同名的基类函数，注意只要同名函数，不管参数列表是否相同，基类函数都会被隐藏。
    • 重写(覆盖)：是指派生类中存在重新定义的函数。其函数名，参数列表，返回值类型，所有都必须同基类中被重写的函数一致。只有函数体不同（花括号内），派生类调用时会调用派生类的重写函数，不会调用被重写函数。重写的基类中被重写的函数必须有virtual修饰。

27. C++ 的程序编译过程

    • 预处理->编译->汇编->链接
    • 源代码（source coprede）→预处理器（processor）→编译器（compiler）→汇编程序（assembler）→目标程序（object code）→链接器（Linker）→可执行程序（executables）
    • 编译预处理：处理以 # 开头的指令；
    • 编译优化：将源码.cpp翻译为.s汇编代码
    • 汇编：将.s翻译成机器指令.o文件
    • 链接：汇编程序生成的目标文件，即.o文件，并不会立即执行，因为可能会出现：.cpp 文件中的函数引用了另一个.cpp
      文件中定义的符号或者调用了某个库文件中的函数。那链接的目的就是将这些文件对应的目标文件连接成一个整体，从而生成可执行的程序 .exe 文件。

计算机网络

1. OSI 七层模型

   • 应用层：协议有：HTTP FTP TFTP SMTP SNMP DNS TELNET HTTPS POP3 DHCP
   • 表示层：数据的表示、安全、压缩。格式有，JPEG、ASCll、DECOIC、加密格式等
   • 会话层：建立、管理、终止会话。对应主机进程，指本地主机与远程主机正在进行的会话
   • 传输层：定义传输数据的协议端口号，以及流控和差错校验。协议有：TCP UDP，数据包一旦离开网卡即进入网络传输层
   • 网络层：进行逻辑地址寻址，实现不同网络之间的路径选择。协议有：ICMP IGMP IP（IPV4 IPV6） ARP RARP
   • 数据链路层：建立逻辑连接、进行硬件地址寻址、差错校验等功能。将比特组合成字节进而组合成帧，用MAC地址访问介质，错误发现但不能纠正。
   • 物理层：建立、维护、断开物理连接。

2. 三次握手和四次挥手

   • https://www.cnblogs.com/zzjdbk/p/13028290.html

3. 三次握手中的 time_wait 的作用

   • 保证客户端发送的最后一个ack报文段能够到达服务器
   • 经过2msl的时间足以让本次连接产生的所有报文段都从网络中消失，这样下一次新的连接中就肯定不会出现旧连接的报文段了

4. TCP 与 UDP 的区别

   • 基于连接与无连接
   • 对系统资源的要求（TCP较多，UDP少）
   • UDP程序结构较简单
   • 流模式与数据报模式
   • TCP保证数据正确性，UDP可能丢包
   • TCP保证数据顺序，UDP不保证

5. TCP 如何保证可靠传输

   • 校验和
   • 确认应答和序列号
   • 超时重传
   • 连接管理（三握四挥）
   • 流量控制（根据接收端对数据的处理能力，决定发送端的发送速度）
   • 拥塞控制（慢开始、拥塞避免、快重传、快恢复。）

6. TCP 超时重传的原理

   • 原理是在发送某一个数据以后就开启一个计时器，在一定时间内如果没有得到发送的数据报的ACK报文，那么就重新发送数据，直到发送成功为止。超过次数会直接resetTCP连接。

7. 如何基于 udp 实现可靠原理

   • UDP本身不可靠，所以得在它上层实现可靠
   • 对UDP报文进行封装，增加TAG，SEQ，ACK等字段
   • 面向连接，模仿三次握手，通过设定TAG的值来实现
   • 确认应答，通过SEQ，ACK的值来实现
   • 滑动窗口，服务端和客户端共同维护一个缓冲区
   • 超时重传，双方设定计时器
   • 差错检测，通过校验和实现
   • 拥塞控制，Reno算法（慢启动，拥塞避免，快重传，快恢复）

8. NAT 的原理

   • NAT英文全称是“Network Address Translation”，中文意思是“网络地址转换”
   • NAT就是在局域网中使用内部地址，而当内部节点要与外部网络进行通讯时，就在网关处，将内部地址替换成公用地址，从而在外部公网（internet）上正常使用
   • 静态NAT：内部地址和外部地址一对一
   • 动态NAT：是指不建立内部地址和全局地址的一对一的固定对应关系。而通过共享NAT地址池的IP地址动态建立NAT的映射关系。当内网主机需要进行NAT地址转换时，路由器会在NAT地址池中选择空闲的全局地址进行映射，每条映射记录是动态建立的，在连接终止时也被收回。
   • 网络地址端口转换NAPT：网络地址端口转换NAPT（Network Address Port Translation）则是把内部地址映射到外部网络的一个IP地址的不同端口上。它可以将中小型的网络隐藏在一个合法的IP地址后面。NAPT与 动态地址NAT不同，它将内部连接映射到外部网络中的一个单独的IP地址上，同时在该地址上加上一个由NAT设备选定的端口号。

9. get/post 区别

   • get提交的数据大小有限制，因为不同浏览器对URL的长度有不同的限制
   • get只允许ASCII字符，post没有这样的限制
   • get会保存在浏览器历史记录中，post不会。这点也能感受到
   • post有可能分开发请求头和请求体，也不是必然的

10. IP 协议的作用

    • 设定报文生存时间
    • 分段与重组： IP数据报通过不同类型的通信网络发送，IP数据报的大小会受到这些网络所规定的最大传输单元(MTU)的限制。将IP数据报拆分成一个个能够适合下层技术传输的小数据报，被分段后的IP数据报可以独立地在网络中进行转发，在到达目的主机后被重组，恢复成原来的IP数据报。

11. 路由器和二层交换机的区别

    • 在OSI七层网络结构中，交换机工作在第二层数据链路层，路由器工作在第三层网络层，也就导致了二层交换机利用我们的MAC地址即每个设备唯一的物理地址来寻址，路由器则通过IP地址来寻址。
    • 交换机是将不同IP地址的电脑连在一起，共享一根网线；路由器是将同一个IP给不同的电脑使用，就像一条大路分成很多条小路。也就是路由器是接外网的，交换机是接内网的，也可以说是交换机是用来构建局域网的，路由器是用来上网的。
    • 交换机是根据MAC地址转发数据帧，而路由器则是根据IP地址来转发IP数据报/分组。
    • 交换机分割冲突域，但是不分割广播域，而路由器分割冲突域还分割广播域。
    • 路由器具有防火墙的功能，能够对一些网络数据包选择性过滤防止广播风暴，而交换机就没有这个功能。

12. arp 协议的功能

    • 地址解析协议，根据IP地址获取物理地址的一个TCP/IP协议
    • 主机发送信息时将包含目标IP地址的ARP请求广播到局域网络上的所有主机，并接收返回消息，以此确定目标的物理地址；收到返回消息后将该IP地址和物理地址存入本机ARP缓存中并保留一定时间，下次请求时直接查询ARP缓存以节约资源。
    • 地址解析协议是建立在网络中各个主机互相信任的基础上的，局域网络上的主机可以自主发送ARP应答消息，其他主机收到应答报文时不会检测该报文的真实性就会将其记入本机ARP缓存；由此攻击者就可以向某一主机发送伪ARP应答报文，使其发送的信息无法到达预期的主机或到达错误的主机，这就构成了一个ARP欺骗。

13. http 连接的全过程

    • 建立TCP连接
    • 浏览器向服务器发送请求命令 get/post
    • 浏览器向服务器发送请求头信息 user-agent, host
    • 服务器应答 版本号和状态码
    • 服务器发送应答头信息 发送被请求的文档 最后发送一个空行表示结束
    • 服务器发送和Content-type应答头信息相符的格式数据
    • 关闭连接

14. dns 为什么用 udp

    • 为了让响应时间越短越好，体验更好，TCP得话还需要加上建立连接的时间，相比之下UDP有时间上的优势
    • 若客户端事先知道 DNS 响应报文的长度会大于 512 字节，则应当直接使用 TCP 建立连接
    • 若客户端事先不知道 DNS 响应报文的长度，一般会先使用 UDP 协议发送 DNS 查询报文，若 DNS 服务器发现 DNS 响应报文的长度大于 512 字节，则多出来的部分会被 UDP 抛弃（截断 TrunCation），那么服务器会把这个部分被抛弃的 DNS 报文首部中的 TC 标志位置为 1，以通知客户端该 DNS 报文已经被截断。客户端收到之后会重新发起一次 TCP 请求，从而使得它将来能够从 DNS 服务器收到完整的响应报文。
    • DNS 在域名解析的过程中，会根据 DNS 响应报文的大小选择使用 TCP 还是 UDP。但是一般情况下，返回的 DNS 响应报文都不会超过 512 字节，所以事实上，很多 DNS 服务器进行配置的时候，也仅支持 UDP 查询包

15. 浏览器输入 url 到显示网页的过程

    • DNS解析——解析域名，获取对应的ip地址
    • TCP连接——TCP三次握手
    • 浏览器发送http请求
    • 服务器处理请求并返回http报文
    • 浏览器解析返回的数据并渲染页面
    • 断开连接：TCP四次挥手

16. ping 的过程

    • 首先假设A ping B
    • ping通知系统建立一个固定格式的ICMP请求数据包。
    • ICMP协议打包这个数据包和B的IP地址转交给IP协议层
    • IP层协议将机器B的IP地址为目的地址，本机的IP地址为源地址，加上一些头部必要的控制信息，构建一个IP数据包
    • 获取B的MAC地址，做这个操作首先机器A会判断B是否在同一网段内，若IP层协议通过B的IP地址和自己的子网掩码，发现它跟自己属于同一网络，就直接在本网络查找这台机器的MAC，否则则通过路由器进行类似查找。
    • 接下来是ARP协议根据IP地址查找MAC地址的过程:
      • 若两台机器之前有过通信，在机器A的ARP缓存表里应该存有B的IP与其MAC地址的映射关系。
      • 若没有，则通过发送ARP请求广播，得到回应的B机器MAC地址，并交给数据链路层
    • 数据链路层构建一个数据帧，目的地址是IP层传过来的MAC地址，源地址是本机的MAC地址，再附加一些必要的控制信息，依据以太网的介质访问规则将他们传送出去
    • 机器B收到这个数据帧后，先检查目的地址，和本机MAC地址对比：
      • 符合，接受。接收后检查该数据帧。将IP数据包从帧中提取出来，交给本机的的IP地址协议层协议，IP协议层检查之后，将有用的信息提取给ICMP协议，后者处理，马上构建一个ICMP应答包，发送给A，其过程和主机A发送ICMP请求包到B的过程类似，但不用ARP广播收取A的信息，因为请求包中已经有足够的信息用于B回应A。
      • 若不符合，丢弃。

17. 如何解决 tcp 粘包问题

    • 固定包长的数据包：格式简单但灵活性差。如果包内容不足指定的字节数，剩余的空间需要填充特殊的信息，如 \0；如果包内容超过指定字节数，又得分包分片，需要增加额外处理逻辑——在发送端进行分包分片，在接收端重新组装包片。
    • 以指定字符（串）为包的结束标志：例如，我们熟悉的 FTP协议，发邮件的 SMTP 协议，一个命令或者一段数据后面加上”\r\n”表示一个包的结束。对端收到后，每遇到一个”\r\n“就把之前的数据当做一个数据包。
    • 包头 + 包体格式：报头中注明每次发送的数据包大小。接收方每次接收时先以报头的size进行数据读取，这必然只能读到一个报头的数据，从报头中得到该数据包的数据大小，然后再按照此大小进行再次读取，就能读到数据的内容了。

18. 流量控制和拥塞控制的区别

    • 流量控制解决的是发送方和接收方速率不匹配的问题，发送方发送过快接收方就来不及接收和处理。采用的机制是滑动窗口的机制。
    • 拥塞控制解决的是避免网络资源被耗尽的问题，通过大家自律的采取避让的措施，来避免网络有限资源被耗尽。当出现丢包时，控制发送的速率达到降低网络负载的目的。

数据结构

1. stl 有哪些容器

   • vector
     • vector是一段连续的内存地址，基于数组实现，其提供了自动内存管理功能，可以动态改变对象长度，提供随机访问。
     • 关于大小的函数
       • size()：返回容器的大小
       • capacity()：返回容器当前能够容纳的元素数量
     • vector内存扩展方式
       • 另觅更大空间
       • 将原数据复制过去
       • 释放原空间
   • list
     • list是非连续的内存，基于链表实现，属于循环双向链表，目的是实现快速插入和删除，但是随即访问却是比较慢。
   • deque
     • 双端队列，支持随机访问，与vector类似，主要区别在于，从deque对象的开始位置插入和删除元素的时间也是常数的，所以若多数操作发生在序列的起始和结尾处，则应考虑使用deque。为实现在deque两端执行插入和删除操作的时间为常数时间这一目的，deque对象的设计比vector更为复杂，因此，尽管二者都提供对元素的随机访问和在序列中部执行线性时间的插入和删除操作，但vector容器执行这些操作时速度更快些。
   • queue
     • queue是一个适配器类。queue模板让底层类（默认是deque）展示典型的队列接口。queue模板的限制比deque更多，它不仅不允许随机访问队列元素，甚至不允许遍历队列。与队列相同，只能将元素添加到队尾、从队首删除元素、查看队首和队尾的值、检查元素数目和测试队列是否为空。
   • priority_queue
     • priority_queue是另一个适配器类，支持的操作与queue相同。两者之间的主要区别在于，在priority_queue中，最大的元素被移到队首。内部区别在于，默认的底层类是vector。可以修改用于确定哪个元素放到队首的比较方式，方法是提供一个可选的构造函数参数：

       priority_queue<int> pq1; // default version
       priority_queue<int> pg2(greater<int>); // use greater<int> to order， greater<>函数是一个预定义的函数对象。

   • stack
     • 与queue相似，stack也是一个适配器类，它给底层类（默认情况下为vector）提供了典型的栈接口。
   • map/multimap
     • map容器提供一个键值对(key-value)容器，map与multimap差别仅仅在于multimap允许一个键对应多个值。对于迭代器来说，可以修改实值，而不能修改key。map会根据key自动排序。

       #include <iostream>
       #include <map>      // map
       #include <string>       // string
       using namespace std;
       int main() {
           //创建空 map 容器，默认根据个键值对中键的值，对键值对做降序排序
           std::map<std::string, std::string, std::greater<std::string>>myMap;
           //调用 emplace() 方法，直接向 myMap 容器中指定位置构造新键值对
           myMap.emplace("C语言教程","http://c.biancheng.net/c/");
           myMap.emplace("Python教程", "http://c.biancheng.net/python/");
           myMap.emplace("STL教程", "http://c.biancheng.net/stl/");
           //输出当前 myMap 容器存储键值对的个数
           cout << "myMap size==" << myMap.size() << endl;
           //判断当前 myMap 容器是否为空
           if (!myMap.empty()) {
               //借助 myMap 容器迭代器，将该容器的键值对逐个输出
               for (auto i = myMap.begin(); i != myMap.end(); ++i) {
                   cout << i->first << " " << i->second << endl;
               }
           }  
           return 0;
       }

       myMap size==3
       STL教程 http://c.biancheng.net/stl/
       Python教程 http://c.biancheng.net/python/
       C语言教程 http://c.biancheng.net/c/

       #include <iostream>
       #include <map>  //map
       using namespace std;   
       int main()
       {
           //创建并初始化 multimap 容器
           multimap<char, int>mymultimap{ {'a',10},{'b',20},{'b',15}, {'c',30} };
           //输出 mymultimap 容器存储键值对的数量
           cout << mymultimap.size() << endl;
           //输出 mymultimap 容器中存储键为 'b' 的键值对的数量
           cout << mymultimap.count('b') << endl;
           for (auto iter = mymultimap.begin(); iter != mymultimap.end(); ++iter) {
               cout << iter->first << " " << iter->second << endl;
           }
           return 0;
       }

       4
       2
       a 10
       b 20
       b 15
       c 30

   • set/multiset
     • set的含义是集合，它是一个有序的容器，里面的元素都是排序好的支持插入、删除、查找等操作，就像一个集合一样，所有的操作都是严格在logn时间内完成，效率非常高。set和multiset的区别是,set插入的元素不能相同，但是multiset可以相同，set默认是自动排序的，使用方法类似list。

       #include <iostream>
       #include <set>
       #include <string>
       using namespace std;
       int main()
       {
           //创建空set容器
           std::set<std::string> myset;
           //空set容器不存储任何元素
           cout << "1、myset size = " << myset.size() << endl;
           //向myset容器中插入新元素
           myset.insert("http://c.biancheng.net/java/");
           myset.insert("http://c.biancheng.net/stl/");
           myset.insert("http://c.biancheng.net/python/");
           cout << "2、myset size = " << myset.size() << endl;
           //利用双向迭代器，遍历myset
           for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
               cout << *iter << endl;
           }
           return 0;
       }

       1、myset size = 0
       2、myset size = 3
       http://c.biancheng.net/java/
       http://c.biancheng.net/python/
       http://c.biancheng.net/stl/

       #include <iostream>
       #include <set>  //使用multiset须包含此头文件
       using namespace std;
       template <class T>
       void Print(T first, T last)
       {
           for (; first != last; ++first)
               cout << *first << " ";
           cout << endl;
       }
       class A
       {
       private:
           int n;
       public:
           A(int n_) { n = n_; }
           friend bool operator < (const A & a1, const A & a2)
           { return a1.n < a2.n; }
           friend ostream & operator << (ostream & o, const A & a2)
           { o << a2.n; return o; }
           friend class MyLess;
       };
       class MyLess
       {
       public:
           bool operator() (const A & a1, const A & a2)  //按个位数比较大小
           { return (a1.n % 10) < (a2.n % 10); }
       };
       typedef multiset <A> MSET1;  //MSET1 用“<”运算符比较大小
       typedef multiset <A, MyLess> MSET2;  //MSET2 用 MyLess::operator() 比较大小
       int main()
       {
           const int SIZE = 6;
           A a[SIZE] = { 4, 22, 19, 8, 33, 40 };
           MSET1 m1;
           m1.insert(a, a + SIZE);
           m1.insert(22);
           cout << "1)" << m1.count(22) << endl;  //输出 1)2
           cout << "2)"; Print(m1.begin(), m1.end());  //输出 2)4 8 19 22 22 33 40
           MSET1::iterator pp = m1.find(19);
           if (pp != m1.end())  //条件为真说明找到
               cout << "found" << endl;  //本行会被执行，输出 found
           cout << "3)"; cout << *m1.lower_bound(22)
               << "," << *m1.upper_bound(22) << endl; //输出 3)22,33
           pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));
           //pp指向被删元素的下一个元素
           cout << "4)"; Print(m1.begin(), m1.end());  //输出 4)4 8 19 33 40
           cout << "5)"; cout << *pp << endl;  //输出 5)33
           MSET2 m2;  //m2中的元素按n的个位数从小到大排序
           m2.insert(a, a + SIZE);
           cout << "6)"; Print(m2.begin(), m2.end());  //输出 6)40 22 33 4 8 19
           return 0;
       }

2. set 与 map 底层实现

   • C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树。
   • https://cloud.tencent.com/developer/article/1688431

3. 二叉搜索树，平衡二叉树，红黑树的区别

   • 二叉查找树就是左结点小于根节点，右结点大于根节点的一种排序树，也叫二叉搜索树。也叫BST，英文Binary Sort Tree。二叉查找树比普通树查找更快，查找、插入、删除的时间复杂度为O（logN）。但是二叉查找树有一种极端的情况，就是会变成一种线性链表似的结构。此时时间复杂度就变成了O（N），为了解决这种情况，出现了二叉平衡树。
   • 平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。AVL树也规定了左结点小于根节点，右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN），但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。
   • 红黑树也叫RBT，RB-Tree。是一种自平衡的二叉查找树，它的节点的颜色为红色和黑色。它不严格控制左、右子树高度或节点数之差小于等于1。红黑树是保持“黑平衡”的二叉树。对于黑平衡是指，从根节点开始搜索，一直搜索到叶子节点，所经历的黑色节点的个数是一样的。红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。
   • https://blog.csdn.net/qq_44918090/article/details/119966525

4. 什么是哈希表，怎么解决冲突

   • 用某函数可以使得元素的存储位置与自身值之间的一种一一对应的映射关系，在查找时，通过该函数就可以很快找到元素，这种对应关系就称之为哈希，元素所存放的空间就称之为哈希表。
   • 开放定址法（闭散列）：从发生哈希冲突的位置开始，找下一个空位置，找空位置又分为两种方法：线性探测和非线性探测。
     • 线性探测：从当前位置依次往后找空位置，找到末尾时，地址下标置0， 从头开始查找。
     • 非线性探测：二次探测：从当前位置，不采用依次往后查找，而通过公式来寻找下一个空位置。公式获取：H(i+1)=H(i)+2*i+1；i=1,2,3,4…代表查找次数。
   • 链地址法（开散列）：将发生哈希冲突的元素放在同一个链表中。

5. 一个哈希表只有 32 个槽如何存放几千个数据

   • 如果只有 30 个槽，说明存在大量的冲突，平均每个槽会产生上百的冲突，此时第一级的哈希函数已经没有多大的优化的空间了，要么进行再 hash。我觉得采用开链法也是可取的，可以在每个槽后接上树结构冲突发生时，往树中添加即可。

6. vector 和 list 区别

   • vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。
   • 因此能高效的进行随机存取，时间复杂度为o(1);
   • 但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。
   • 另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。
   • list是由双向链表实现的，因此内存空间是不连续的。
   • 只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);
   • 但由于链表的特点，能高效地进行插入和删除。

7. vector 的扩容机制

   • 整体的一个扩容流程为：申请新的内存空间（空间大小为原空间的两倍或一点五倍）—> 把原空间的元素拷贝到新的空间里 —> 释放原空间 —> 数组指针指向新空间。

操作系统

1. select，poll，epoll 的区别

   • https://zhuanlan.zhihu.com/p/272891398
   • select，poll，epoll都是IO多路复用机制，即可以监视多个描述符，一旦某个描述符就绪（读或写就绪），能够通知程序进行相应读写操作。 但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。
   • select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll其实也需要调用epoll_wait不断轮询就绪链表，期间也可能多次睡眠和唤醒交替，但是它是设备就绪时，调用回调函数，把就绪fd放入就绪链表中，并唤醒在epoll_wait中进入睡眠的进程。虽然都要睡眠和交替，但是select和poll在“醒着”的时候要遍历整个fd集合，而epoll在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。这就是回调机制带来的性能提升。

2. epoll 高效的原因

3. 水平触发和边缘触发的应用场景

4. 同步和异步 IO 的区别

   • 同步：所谓同步，就是在发出一个功能调用时，在没有得到结果之前，该调用就不返回。也就是必须一件一件事做,等前一件做完了才能做下一件事。
     • 例如普通B/S模式（同步）：提交请求->等待服务器处理->处理完毕返回 这个期间客户端浏览器不能干任何事
   • 异步：异步的概念和同步相对。当一个异步过程调用发出后，调用者不能立刻得到结果。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。
     • 例如 ajax请求（异步）: 请求通过事件触发->服务器处理（这是浏览器仍然可以作其他事情）->处理完毕
   • 阻塞：阻塞调用是指调用结果返回之前，当前线程会被挂起（线程进入非可执行状态，在这个状态下，cpu不会给线程分配时间片，即线程暂停运行）。函数只有在得到结果之后才会返回。
     • 有人也许会把阻塞调用和同步调用等同起来，实际上他是不同的。对于同步调用来说，很多时候当前线程还是激活的，只是从逻辑上当前函数没有返回,它还会抢占cpu去执行其他逻辑，也会主动检测io是否准备好。
   • 非阻塞：非阻塞和阻塞的概念相对应，指在不能立刻得到结果之前，该函数不会阻塞当前线程，而会立刻返回。
   • 再简单点理解就是：
     • 1. 同步，就是我调用一个功能，该功能没有结束前，我死等结果。
     • 2. 异步，就是我调用一个功能，不需要知道该功能结果，该功能有结果后通知我（回调通知）。
     • 3. 阻塞，就是调用我（函数），我（函数）没有接收完数据或者没有得到结果之前，我不会返回。
     • 4. 非阻塞，就是调用我（函数），我（函数）立即返回，通过select通知调用者
   • 同步IO和异步IO的区别就在于： 数据拷贝的时候进程是否阻塞
   • 阻塞IO和非阻塞IO的区别就在于： 应用程序的调用是否立即返回

5. 什么是僵尸进程，孤儿进程，怎么回收

   • 孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
   • 僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。
   • 如何查看linux系统上的僵尸进程，如何统计有多少僵尸进程？#ps -ef | grep defunct
   • 方法一：父进程通过wait或者wait_pid方式回收子进程
   • 方法二：信号处理signal

6. 什么是守护进程，如何创建

   • Linux Daemon（守护进程）是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务，不是对整个系统就是对某个用户程序提供服务。常见的守护进程包括系统日志进程syslogd、 web服务器httpd、邮件服务器sendmail和数据库服务器mysqld等。
   • 利用库函数daemon()创建守护进程

7. 什么是虚拟内存

   • 虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。

8. 物理内存和虚拟内存的区别

   • https://cloud.tencent.com/developer/news/682507

9. 1G 的物理内存可以读取 2G 的数据吗

   • malloc能够申请的空间大小与物理内存的大小没有直接关系，仅与程序的虚拟地址空间相关。程序运行时，堆空间只是程序向操作系统申请划出来的一大块虚拟地址空间。应用程序通过malloc申请空间，得到的是在虚拟地址空间中的地址，之后程序运行所提供的物理内存是由操作系统完成的。

10. 阻塞和非阻塞区别

    • 阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态.
    • 阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。
    • 非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。

11. Linux 进程调度算法主要有哪些

    • 先来先服务调度算法
    • 短作业(进程)优先调度算法
    • 高优先权优先调度算法（非抢占式/抢占式）
    • 高响应比优先调度算法：在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。如果我们能为每个作业引入前面所述的动态优先权，并使作业的优先级随着等待时间的增加而以速率a 提高，则长作业在等待一定的时间后，必然有机会分配到处理机。
    • 时间片轮转法
    • 多级反馈队列调度算法:
      • (1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
      • (2)当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。
      • (3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

12. 进程与线程区别

    • 线程是处理器调度的基本单位，进程是资源调度的基本单位。
    • 地址空间：线程共享本进程的地址空间，而进程之间是独立的地址空间。
    • 资源：线程共享本进程的资源如内存、I/O、cpu等，不利于资源的管理和保护，而进程之间的资源是独立的，能很好的进行资源管理和保护。
    • 切换时：进程切换时，消耗的资源大，效率高。所以涉及到频繁的切换时，使用线程要好于进程。同样如果要求同时进行并且又要共享某些变量的并发操作，只能用线程不能用进程。

13. 内核线程了解吗，它和用户线程什么区别

    • 用户线程
    • 不需要内核支持而在用户程序中实现的线程，其不依赖于操作系统核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。不需要用户态/核心态切换，速度快，操作系统内核不知道多线程的存在，因此一个线程阻塞将使得整个进程（包括它的所有线程）阻塞。由于这里的处理器时间片分配是以进程为基本单位，所以每个线程执行的时间相对减少。
    • 系统线程
    • 由操作系统内核创建和撤销。内核维护进程及线程的上下文信息以及线程切换。一个内核线程由于I/O操作而阻塞，不会影响其它线程的运行。

14. 进程间的通讯方式

    • 管道，通常指无名管道，是 UNIX 系统IPC最古老的形式。
      • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
      • 它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。
      • 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。
    • FIFO，也称为命名管道，它是一种文件类型。
      • FIFO可以在无关的进程之间交换数据，与无名管道不同。
      • FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。
    • 消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。
      • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
      • 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
      • 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。
    • 信号量（semaphore），它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
      • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。
      • 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
      • 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
      • 支持信号量组。
    • 共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区。
      • 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
      • 因为多个进程可以同时操作，所以需要进行同步。
      • 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。
    • 总结
      • 1.管道：速度慢，容量有限，只有父子进程能通讯
      • 2.FIFO：任何进程间都能通讯，但速度慢
      • 3.消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题
      • 4.信号量：不能传递复杂消息，只能用来同步
      • 5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

15. 互斥锁和自旋锁

    • 互斥锁加锁失败后，线程会释放 CPU ，给其他线程；
    • 自旋锁加锁失败后，线程会忙等待，直到它拿到锁；

16. 大小端的区别

    • 32bit宽的数0x12345678在Little-endian模式CPU内存中的存放方式（假设从地址0x4000开始存放）为：

      内存地址    0x4000  0x4001  0x4002  0x4003
      存放内容    0x78    0x56    0x34    0x12

    • 而在Big-endian模式CPU内存中的存放方式则为：

      内存地址    0x4000  0x4001  0x4002  0x4003
      存放内容    0x12    0x34    0x56    0x78

    • 如何测试编译器是大端还是小端

      #include "stdafx.h"
      #include "stdlib.h"
      #include<stdio.h>
      int main()
      {
          int  x;
      char x0, x1,x2,x3;
      x = 0x12345678;
      x0 = ((char *)&x)[0];  //低地址单元
      x1 = ((char *)&x)[1];  //高地址单元
      x2 = ((char *)&x)[2];
      x3 = ((char *)&x)[3];
      printf("x0=0x%x,x1=0x%x,x2=0x%x,x3=0x%x", x0, x1 ,x2, x3); 
      system("pause");
      return 0;
      }

17. 软链接，硬链接

    • 硬链接是指通过索引节点来进行链接。在Linux的文件系统中，保存在磁盘分区中的文件不管是什么类型都会给它分配一个编号，这个编号被称为索引节点编号Inode，它是文件或者目录在一个文件系统中的唯一标识，文件的实际数据放置在数据区域（data block），它存储着文件重要参数信息，也就是元数据 （metadata），比如创建时间、修改时间、文件大小、属主、归属的用户组、读写权限、数据所在block号等。在Linux系统中，多个文件名指向同一索引节点(Inode)是正常且允许的。一般这种链接就称为硬链接。硬链接的作用之一是允许一个文件拥有多个有效路径名，这样用户就可以建立硬链接到重要的文件，以防止“误删”源数据(很多硬件，如netapp存储中的快照功能就应用了这个原理，增加一个快照就多了一个硬链接》。不过硬链接只能在同一文件系统中的文件之间进行链接，不能对目录进行创建。之所以文件建立了硬链接就会防止数据误删，是因为文件系统的原理是，只要文件的索引节点还有一个以上的链接（仅删除了该文件的指向），只删除其中一个链接并不影响索引节点本身和其他的链接（数据的实体并未删除），只有当最后一个链接被删除后，此时如果有新数据要存储到磁盘上，被删除的文件的数据块及目录的链接才会被释放，空间被新数据暂用覆盖。
    • 软链接（也叫符号链接），类似于windows系统中的快捷方式，与硬链接不同，软链接就是一个普通文件，只是数据块内容有点特殊，文件用户数据块中存放的内容是另一文件的路径名的指向，通过这个方式可以快速定位到软连接所指向的源文件实体。软链接可对文件或目录创建。删除软链接并不影响被指向的文件，但若被指向的原文件被删除，则相关软连接就变成了死链接。
    • linux系统可以用ln命令来创建链接文件。ln命令格式：ln [参数] [源文件或目录] [目标文件或目录]

18. fork 子进程继承父进程什么资源

    • 使用fork函数得到的子进程从父进程的继承了整个进程的地址空间，包括：进程上下文、进程堆栈、内存信息、打开的文件描述符、信号控制设置、进程优先级、进程组号、当前工作目录、根目录、资源限制、控制终端等。

19. 操作系统的加载过程

    • 1. BIOS加电自检，寻找显卡和执行BIOS。
    • 2. 将bootloader加载到内存中。
    • 3. bootloader找到硬盘的起始扇区，将操作系统代码和数据从硬盘读取到内存中。

20. 进程切换发生了什么

    • 进程切换
      • 进程切换指从正在运行的进程中收回处理器，让待运行进程来占有处理器运行。
      • 实质上就是被中断运行进程与待运行进程的上下文切换。
    • 模式切换
      • 进程切换必须在操作系统内核模式下完成，这就需要模式切换。
      • 模式切换又称处理器切换，即用户模式和内核模式的互相切换。
    • 进程切换的工作过程
      • 1、（中断／异常等触发）正向模式切换并压入PSW／PC 。 （Program Status Word 程序状态字。program counter 程序计数器。指向下一条要执行的指令）
      • 2、保存被中断进程的现场信息。
      • 3、处理具体中断、异常。
      • 4、把被中断进程的系统堆栈指针SP值保存到PCB。（Stack Pointer 栈指针。Process Control Block 进程控制块。）
      • 5、调整被中断进程的PCB信息，如进程状态）。
      • 6、把被中断进程的PCB加入相关队列。
      • 7、选择下一个占用CPU运行的进程。
      • 8、修改被选中进程的PCB信息，如进程状态。
      • 9、设置被选中进程的地址空间，恢复存储管理信息。
      • 10、恢复被选中进程的SP值到处理器寄存器SP。
      • 11、恢复被选中进程的现场信息进入处理器。
      • 12、（中断返回指令触发）逆向模式转换并弹出PSW／PC。
    • 进程切换何时发生
      • 1、阻塞式系统调用、虚拟地址异常。导致被中断进程进入等待态。
      • 2、时间片中断、I/O中断后发现更改优先级进程。导致被中断进程进入就绪态。
      • 3、终止用系统调用、不能继续执行的异常。导致被中断进程进入终止态。
    • 但是并不意味着所有的中断／异常都会引起进程切换
      • 有一些中断／异常不会引起进程状态转换，不会引起进程切换，只是在处理完成后把控制权交还给被中断进程。
      • 以下是处理流程：
      • 1、（中断／异常等触发）正向模式切换并压入PSW／PC 。
      • 2、保存被中断进程的现场信息。
      • 3、处理具体中断、异常。
      • 4、恢复被中断进程的现场信息。
      • 5、（中断返回指令触发）逆向模式转换并弹出PSW／PC。

算法

1. 大样本统计
   • https://leetcode-cn.com/problems/statistics-from-a-large-sample/
2. 反转链表
   • https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
3. 删除链表中的节点
   • https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
4. 二叉树的遍历方式及实现
5. 假设 4 个人过河，每个人的过桥时间为1，2，5，8。只有一个手电筒，一次最多过两个，怎么过桥速度最快
6. 快速排序的思想

   void quicksort(int p[], int l, int r) {
       if (l >= r) return;
       int val = p[l];
       int i = l;
       int j = r;
       while (i < j) {
           while (i < j && p[j] > val) --j;
           if (i < j) p[i++] = p[j];
           while (i < j && p[i] < val) ++i;
           if (i < j) p[j--] = p[i];
       }
       p[i] = val;
       quicksort(p, l, i - 1);
       quicksort(p, i + 1, r);
   }

7. 前k个高频元素
   • https://leetcode-cn.com/problems/top-k-frequent-elements/
8. 网格中的最短路径
   • https://leetcode-cn.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/
9. 二叉树的最近公共祖先
   • https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
10. 环形链表
    • https://leetcode-cn.com/problems/linked-list-cycle/
11. 环形链表II
    • https://leetcode-cn.com/problems/linked-list-cycle-ii/
12. 寻找两个正序数组的中位数
    • https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
13. 二分查找
    • https://leetcode-cn.com/problems/binary-search/
14. 实现strStr()
    • https://leetcode-cn.com/problems/implement-strstr/
15. 奇偶树
    • https://leetcode-cn.com/problems/even-odd-tree/
16. 二叉树中和为某一值的路径
    • https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
17. 二叉树的中序遍历
    • https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
18. 首个公共祖先
    • https://leetcode-cn.com/problems/first-common-ancestor-lcci/
19. 统计词频
    • https://leetcode-cn.com/problems/word-frequency/
20. 二叉树的深度
    • https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
21. 合并k个升序链表
    • https://leetcode-cn.com/problems/merge-k-sorted-lists/
22. 栈排序
    • https://leetcode-cn.com/problems/sort-of-stacks-lcci/
23. 最长公共子序列
    • https://leetcode-cn.com/problems/longest-common-subsequence/
24. 二叉搜索树的第k大节点
    • https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/