↓Skip to main content
A cup of beer
  1. Posts/

字节客户端+后端八股文☝️

·884 words·5 mins
杂谈
Table of Contents
Abstract purple artwork
Photo by Jr Korpa on Unsplash

排序算法 #

  • 快排、归并、堆排序是三种最快的方法，选择、希尔、堆、快排不稳定
  • 选择排序：（有序区间，无序区间）
    • 数组原地分为已排序区间和未排序区间，分别位于前部和后部；每次从未排序的区间内取最小的，放到已排序区间的尾部。是原地排序，但是n^2。
    • 不稳定，因为需要交换
  • 插入排序：（有序区间，无序区间）
    • 类似于选择排序，也是被分为排好序和没排好序的区间，但是插入排序是直接拿取未排序区间的首个元素插入到已排好序区间的合适位置。
    • 与选择排序的区别是：插入排序是稳定的，n^2
  • 冒泡排序：（无序区间，有序区间）
    • 数组原地分为未排序区间和已排序区间。每次泡泡从未排序区间上升到已排序区间。一直在扫描，每次都两两比较相邻元素，如果逆序就正过来
    • 稳定，n^2
  • 希尔排序
    • 因为插入排序只对快排好序的序列很快，但是如果无序就会很慢，因为每趟只能消除一个逆序对，于是希尔排序进行改进
    • 每次确定一个增量，初始增量一般是数组长度/2；然后每次以这个增量为间隔，分出很多子序列，把每个子序列看做一个子数组分别进行插入排序。每次都排完了就让增量/=2.直到增量为1.
    • 最好情况可以到nlogn，平均nlog^2n.
  • ![[Pasted image 20220311100923.png]]
  • 堆排序：（堆）
    • 是原地排序，而且nlogn
  • 快速排序：（小于枢轴的，枢轴，大于枢轴的）
    • 对几乎有序的序列很慢
  • 计数排序：（桶，桶，…，桶）
    • 额外的桶，每个桶是一个数字，这个桶可以是任意大的，然后遍历数组，以数组的元素值作为桶号放入桶中。都放了以后，再从桶中按桶号有序取出。
    • 序列的关键字比较集中，已知边界，且边界较小（因为空间复杂度也是n+k）
    • 稳定（如果保证反向填充），n+k（当输入n个0到k之间的整数）
  • 桶排序：（桶，桶，…，桶）
    • 对计数排序进行升级。每个桶不再是单值，而是对应范围值，例如值为10-20的在桶1，20-30的在桶2，然后每个桶分别排序，最后有序输出。
    • 要求数据均匀分布，是n的
  • 基数排序：（桶，桶，…，桶）
    • 被比较的对象只能是整数（但是可以用于映射其他类型的数据）
    • 例如比较十进制数，则只需要10个桶，分别是0-9，然后第一趟排序先进行对个位的计数排序，然后输出；第二趟排序再进行对十位的计数排序，然后输出，以此类推，直到各位完毕。是kn的。

AVL树旋转 #

  • AVL树的旋转图解和简单实现_喵了个呜的博客-CSDN博客_avl树
  • 注意，再哪棵树上插入，取决于插入的值与树上结点的关系，也就是必须满足查找树的关系。
  • 大旋转的意思是，以下述“某结点”的直接孩子结点为旋转轴；小旋转的意思是，以下述“某结点”的孩子的孩子（或者说是插入了新节点导致构成新子树的那个树根）结点为旋转轴。
  • LL：在某结点的左孩子的左子树上插入了新节点，需要大右旋
  • RR：在某结点的右孩子的右子树上插入了新结点，需要大左旋
  • LR：在某结点的左孩子的右子树上插入了新节点，需要对低层进行小左旋，然后对高层进行大右旋
  • RL：在某结点的右孩子的左子树上插入了新节点，需要对低层进行小右旋，然后对高层进行大左旋 五层和七层模型，分别说说每一层做的事儿；

软件架构模式 #

  • 软件架构模式比设计模式的概念更广，更加通用。表示在给定的业务情境下，软件体系结构可能会出现的常见问题
  • 分层模式
    • 表示层，服务层，业务逻辑层，数据访问层
  • 客户机-服务器模式
    • 一个服务端和多个客户端。
    • 服务端持续监听用户请求。
  • 主从设备模式
    • 主设备在相同的从设备中分配工作（有一个主和多个从）。
    • 例如mysql主从复制
  • 管道-过滤器模式（类似于CG里面的流水线）
    • 生成和处理数据流的系统。每个步骤都相当于一个过滤器。处理的数据通过管道传递。
    • 例如编译器的实现
  • 代理模式
    • 可以构造解耦的分布式系统，他们之间可以通过网络连接进行交互。服务器将其功能发布给代理，客户端可以与代理进行交互，需要实际功能时代理可以重定向该请求到服务器
  • 点对点模式（p2p）
    • 每个端可以充当服务器或客户端，并且可以随时转换角色
  • 事件总线模式
    • 包括事件源、通道、事件总线、监听器。
    • 事件源产生事件，把它发布到总线的某事件通道内。对应的监听器可以监听到。
  • MVC模式（模型-视图-控制器）
    • 模型：包含核心功能和数据；视图：展示给用户的信息；控制器：处理用户输入
    • 可以理解为CPU和IO。模型就是CPU，控制器和视图分别是IO。
  • 黑板模式
    • 由知识源、黑板、控制器构成
    • 知识源和控制器都可访问黑板。知识源可以在黑板上添加新的数据对象，控制器可以根据知识源的情况，在黑板上进行匹配查找
    • 例如语音识别的应用
  • 解释器模式
    • 定义语言的文法，然后建立一个解释器来解释其中的句子
    • 例如sql语言的实现 银行家算法实现

数据库隔离等级 [mysql事务的实现原理 - 简书](https://www.jianshu.com/p/bcbeb58963c3 #

  • 数据库的三层结构
    • 第一层：处理客户端连接，认证
    • 第二层：处理语法解析、查询优化
    • 第三层：存储引擎
  • 三个模式，两层映像
    • 外模式：用户视图
    • 模式：数据库的一切逻辑数据模式的统称
    • 内模式：物理存储

动态代理 在构造函数中使用当前类的shared_ptr会出现什么问题

八股 #

  • 设计模式？六大原则？

    • 常见设计模式
      • 工厂模式：一个抽象的接口，多个抽象接口的实现类，一个工厂类，用来实例化抽象的接口。客户端只需知道传入工厂类静态方法的参数，而不需要关心创建对象的细节。
      • 单例模式：就是一个应用程序中，某个类的实例对象只有一个，你没有办法去new，因为构造器是被private修饰的，一般通过getInstance()的方法来获取它们的实例。
      • 装饰模式：为对象动态地增加职责。可以是有一个Food类，然后很多食材继承于它。
      • 策略模式：可以定义一个算法接口，可以有不同的几种实现。于是可以保证使它们可以互相替换。例如微信登录和手机号登录都可以用于实现login接口，然后根据实际情况进行选择。
      • 代理模式：代理可以协调调用方与被调用方，降低了系统的耦合度。
        • 虚拟(Virtual)代理：如果需要创建一个资源消耗较大的对象，先创建一个消耗相对较小的对象来表示，真实对象只在需要时才会被真正创建。
        • Copy-on-Write代理：它是虚拟代理的一种，把复制（克隆）操作延迟到只有在客户端真正需要时才执行。一般来说，对象的深克隆是一个开销较大的操作，Copy-on-Write代理可以让这个操作延迟，只有对象被用到的时候才被克隆。
      • 观察者模式：对象间一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。
        • 被观察者只是按照自己的逻辑发出消息，不用关心谁来消费消息，每个观察者只处理自己关心的内容。逻辑相互隔离带来简单清爽的代码结构。
    • 六大原则（软件设计的SOLID原则）
      • 单一职责：实现一个类，它的职责必须是单一的
        • 类只能有一个职责。当需要修改该职责时，不会导致其它问题。如果这个类有两个职责，那么修改器中一个职责时，可能导致另一个职责不能正常工作。
        • 于是可以提升代码的可维护性。
      • 接口隔离原则：实现一个接口，它的职责必须是单一的
        • 一个类对另一个类的依赖的接口应当是极小的；客户端不应当依赖它不需要的接口。
        • 前者的意思是：接口不得臃肿，应当有明确的功能。如果过于臃肿，应当进行拆分。
      • 里氏替换原则（LSP）：不要破坏继承体系
        • 只要父类出现的地方子类就可以出现，换成子类也不会有什么异常，但是反之就不行了。
        • 子类可以增加自己的方法，反正就算替换了也不会被调用到。
        • 要实现这一点，子类不要重写父类的方法；如果真的要重载，那参数的要求只能低于父亲的；如果真的要重载，那返回值的要求只能高于父亲的。否则就不能完成原地替换了。
      • 依赖倒置原则：要面向接口编程
        • 高层不应依赖低层的细节，而是依赖低层的抽象。
        • 这就要求我们每个类一定都要继承自抽象类或接口
      • 迪米特法则（LoD），又称最少知识原则：要降低耦合度
        • 如果两个软件实体无须直接通信，那么就不应当发生直接的相互调用，可以通过第三方转发该调用。
        • 因为耦合性越高，一个发生更改，对另一个的影响越强烈。
      • 开闭原则：是软件设计的总纲要
        • 软件实体类应当对扩展开放，对修改关闭。
          • 因此，要对软件功能进行升级，不要求修改写好的代码，而是利用原来的接口进行扩展。
      • 总结六大设计原则
        • 用抽象设计框架，用扩展实现细节
      • 500_请求出错 - 博客园

  • https

    • https是什么
      • .pem .key
    • SSL证书
      • 这个证书其实就是公钥+其他信息，如证书的颁发机构，过期时间等等。
    • 公钥和私钥
      • 可以想象成一把钥匙和一个锁头，只是全世界只有你一个人有这把钥匙，你可以把锁头给别人，别人可以用这个锁把重要的东西锁起来，然后发给你，因为只有你一个人有这把钥匙，所以只有你才能看到被这把锁锁起来的东西。
    • https的过程
      • 服务端发送公钥（证书），客户端进行验证，如果通过，则生成随机key，用服务端发来的公钥包一层，发给服务端。因为这个东西只有服务端可以查看，所以现在只有客户端和服务端知道随机key是多少。
      • 之后可以用随机key进行对称加密了。
    • 中间人攻击
      • 如果中间人替换了证书里面的公钥，换成自己的，那么因为自己还有配对的私钥，就可以看到随机key，然后再套上正确的公钥传回服务器。
      • 因为证书是由公钥和CA证书构成，是防止篡改的，所以可以防范中间人攻击。

  • 加密

    • 非对称加密会比对称加密来得安全。前者相当于直接告诉其他人密码是多少，后者只是告诉人应该用我这个上锁，但是具体怎么解锁只有我知道。
    • 但是非对称加密的算法比较慢，所以在https中，后续数据传输采用对称加密。
    • 对称加密DES，AES，IDEA；非对称加密常用RSA

  • RSA原理

    • ![[Pasted image 20220308105019.png]]
    • 选俩质数p、q，计算乘积，转换成二进制，记作n；计算欧拉函数(p-1)(q-1)，得到L；求与L互质的整数e；求和L，e模反的d；然后就可以封装(n,e)（n,d）为公、私钥。

  • md5原理

    • md5是不可逆的
    • MD5算法对输入任意长度的消息进行运行，产生一个128位的消息摘要(32位的数字字母混合码)。

  • SHA256

    • Secure Hash Algorithm
    • 和md5一样，都是不可逆的哈希摘要算法
    • 256位的信息摘要

  • 乐观锁悲观锁对比

    • 悲观锁即不管你是不是会出现并发错误，都给你锁上。这样会降低系统吞吐量。主要分为共享锁（读锁，S锁）和排他锁（写锁，X锁）。如果当前是共享锁，那么是只读的，且其他读锁可以继续上，但是不能上写锁。如果当前是排他锁，则不接受任何新的上锁。
    • 乐观锁即永远假设不会出现并发错误。当写回时，再考虑是否有问题。如果发生冲突，则报错，让用户自己解决。主要实现方式可以是版本控制。一般不会产生死锁，因为它不会上锁。

  • C函数和C++函数区别

    • C++多了inline，多了重载（通过编译阶段的更名实现），多了默认参数

  • TCP和UDP的区别

    • 后者是无连接的服务
    • 在需要即时性的环境下，udp是更好的选择
    • tcp可靠传输，可靠交付，udp不可靠传输，不可靠交付
    • tcp有拥塞控制，udp没有
    • 至少20字节和、8字节头部
    • 前者主要保证可靠性，后者可应用于网络负担非常重，但对响应速度要求高。
    • tcp是点对点的，udp是可以多播和组播的

  • TCP的拥塞控制

    • AIMD方法，即Additive Increase & Multiplicative Decrease，加性增，乘性减。
    • 一开始拥塞窗口大小被初始化一个MSS（最小段长度）的大小
    • Threshold被定义为上次发生Loss时，拥塞窗口大小的一半。
    • 窗口大小<Threshold，TCP处于慢启动状态，以不断乘2的方式增长；
    • 窗口大小>Threshold，CP处于拥塞避免状态，其拥塞窗口大小以AIMD方式增长；如果出现了loss，就~。

  • UTF-8中中文字符的大小，英文和数字的呢

    • 3，1

  • 宏和内联函数的区别

    • 内联函数是在编译时展开，而宏在预编译时展开；（一个是逻辑嵌入，一个是文本替换）
    • 宏不支持安全检查
    • inline函数需要给出定义，否则不知道是否应当嵌入

  • 递归函数可以内联吗

    • 一般情况下系统不会响应写成递归的内联请求
    • 可能会尝试进行有限深度的递归内联，而且可能只是作为备用；但是一定不会生成无线长度的代码

  • const和static的区别

    • static在超出其作用域后不会被释放
    • const如果是成员变量，必须给出初始值，并且是在参数表中进行

  • 索引，索引的种类？怎么生成索引？索引失效的情况？索引的底层数据结构

    • B+树索引、哈希索引、倒排索引
      • b+树是多路平衡搜索树，只有叶子上真的存数据，叶子结点是磁盘块；非叶节点上存的都是key，且每个非叶节点上可以存放多个key
      • ![[Pasted image 20220308143948.png]]
      • 哈希索引就是哈希表
        • 哈希表可以
      • 倒排索引通过分词实现
      • Hash哈希，只适合等值查询，不适合范围查询；一般二叉树，可能会特殊化为一个链表，相当于全表扫描。红黑树、B树的高度太高了。
    • 需要类型转换; where中索引列有运算; where中索引列使用了函数;
    • 频繁更新的可以不用索引

  • C++程序内存存储区

  • ddos攻击

    • ddos扫描
    • CDN

  • 构造函数和析构函数是否需要抛出异常

    • 在语法上都是可行的
    • 构造函数可以抛出异常，例如无法分配内存可以及时通知
    • 析构函数不推荐抛出异常，因为程序不会执行抛出异常点之后的代码。也就是说无法正常释放资源。

  • 没有成员变量和虚函数的对象的大小，没有成员变量但有虚函数的对象的大小

    • 如果没有成员变量、虚函数，那么size是1，否则OS无法区分这个类的不同的对象，因为无法分配不同的地址。
    • 继承后，子类的大小是父类大小+新成员；如果含有虚函数，还要加上指向父类的指针和虚表的指针
    • 虚表是指针数组，指向函数；虚表是属于类的，所以对象大小不包含虚表本身，而是只包含虚表指针；虚表在编译时生成，存储在只读数据段rdata
      • vptr指向虚表起始地址，虚表中是各虚函数（实现）函数的地址
      • 因为vptr是对象的第一个元素，所以*(int *)(&a)就是对象a的vptr了.

  • 如何才能做到只能在栈空间创建对象，如何才能做到只能在堆空间创建对象

    • 只要不用new，就可以只在栈上创建对象。
    • 如果把析构函数设为private，就能只在堆上创建对象。因为对象的内存管理是在编译阶段进行，如果发现析构函数不可用，就只能在运行时动态进行了。

  • 内存泄漏是什么，怎么检测

    • 动态开辟的空间，在使用完毕后未释放，结果导致一直占据该内存单元。直到程序结束。
    • 静态变量过多、打开的文件未关闭
    • 可用ccmalloc、Dmalloc检测。

  • 多态

    • 如果要实现多态，需要把需要重用的函数定义为虚函数

  • 不用指针引用是否能发生动态绑定

    • 不可以，因为这是静态的，在编译阶段就确定了
    • 静态绑定（前期绑定）是指在程序运行前就已经知道方法是属于哪个类的，在编译的时候就可以连接到类的中，定位到这个方法。动态绑定（后期绑定）是指在程序运行过程中，根据具体的实例对象才能具体确定是哪个方法。

  • TCP包结构

    • ![[Pasted image 20220308151624.png]]

  • 声明Base对象用Derive对象赋值，会发生什么

    • 会发生类似于强制类型转的事情。舍去了一切派生类对象新增的成员内容。

  • 拷贝初始化和直接初始化区别

    • 前者用等号（赋值表达式）或等号（等号里面是另一个同类对象），后者用括号（括号里面写构造函数的参数）
    • 复制构造函数是参数为一个const 引用的该类对象的构造函数。

  • 内存管理的问题

    • 野指针：释放了但是没删掉指针
    • 重复删除一个指针指向的空间：直接导致崩溃
    • 内存泄露：用完了空间忘了删除。如何判断是否发生内存泄露？可以通过观察，看到如果程序运行的过程中，内存占用率逐步上升，那就是有问题。

  • 构造函数中调用虚函数会怎么样

    • 对象类型变成了基类类型。所以，虚函数始终仅仅调用基类的虚函数（如果是基类调用虚函数），不能达到多态的效果，所以放在构造函数中是没有意义的，而且往往不能达到本来想要的效果

  • http2.0最大的改变

    • 多路复用
    • HTTP/2 采用二进制格式传输数据，而非 HTTP 1.x的文本格式，解析起来更高效
    • 使用报头压缩，降低开销

  • http1.0/http1.1/http2.0区别

    • 1.0 HTTP 1.0 浏览器与服务器只保持短暂的连接，每次请求都需要与服务器建立一个TCP连接
    • 在HTTP1.1中，默认支持长连接（Connection: keep-alive），HTTP 1.1还允许客户端不用等待上一次请求结果返回，就可以发出下一次请求

  • 重写基类虚函数后，怎么调用基类虚函数

    • B *p=reinterpret_cast<B*>(&a);（其中a是基类，b是派生类）

  • 连接建立以后仍然用非对称加密有什么问题

    • 速度慢：非对称加密的效率非常低，而https的请求的频率是非常高的，几乎无法接受
    • 无法解密：非对称加密需要私钥才能解密，但是只有服务器端有私钥，所以无法让双方都能读到对方的信息

  • 继续访问证书失败的网络

    • 但是，正如前文所说，浏览器只会提示安全风险，如果用户授权仍然可以继续访问网站，完成请求。因此，只要客户端是我们自己的终端，我们授权的情况下，便可以组建中间人网络，而抓包工具便是作为中间人的代理。

  • 对称加密更快吗，为什么

    • 对称加密一般使用的是对二进制的操作；非对称加密采用的是高级的运算，例如加法、乘法、取模。对于计算机而言，后者会慢很多。

  • 网络环境不好，采取什么措施来提升http请求成功率

  • 应用层有什么办法减少网络拥塞，发的包如何优化

    • nginx 七层负载均衡
    • LVS

  • TCP粘包问题

    • TCP是面向流的，所以TCP包之间没有明确界限，于是可能会两个连在一起。UDP因为是面向消息的，所以有明确的界限保护，并不会粘包
    • 发送端的nagle算法会导致出现粘包的可能性。当ack来了，才会发送，且会收集多个小分组，当ack来了就一起发出去。
    • 接收端如果缓存的速度大于应用程序读取的速度，就会发生粘包。
    • 可以在应用层解决。例如添加分界符，或是添加“包长度”字段，从而可以区分出不同的包

  • 自旋锁和互斥锁的区别，使用场景

    • 自旋锁会一直循环（轮询），占用CPU却不做事情，属于“忙等”
    • 互斥锁会进入等待
    • 如果要执行的任务并不复杂，或者等待时间并不长，使得这个等待开销要小于线程上下文切换的，那就可以使用自旋锁了。
    • 但是如果并发度过高，自旋锁就旋不起来了，轮询频率降低。

  • 快速排序是否是稳定排序

    • 不稳定

  • 递归锁

    • 递归锁允许同一个线程多次上同一个锁，只要保证他们解锁的次数一样即可。
    • 但是一定要注意的是：必须是同一个线程。
    • 考虑应用场景：如果A、B、C函数都需要上同一个锁，在某线程中嵌套调用这三个函数，如果没有使用递归锁，就会死锁。

  • app启动时有很多线程同时启动来请求资源，如何限制最大并发数

    • 可以用信号量

  • 线程池

    • 因为服务器来一个请求就创建一个线程，结束了就销毁，这对短任务来说，创建和销毁过程花费的时间非常浪费。
    • 线程池可以限制线程的数量，因为它可以在请求过多时选择不创建新的线程。
    • 对于实时性要求的任务，因为线程池免去了进程创建的时间，所以更加合适。
    • 任务构成一个队列，闲置线程是阻塞状态。现在可以任意唤醒一个阻塞的空闲线程，从而响应任务队列的一个任务。当某短时间任务过多，可以创建更多的线程，且用完了也不销毁；当某短时间任务较少，才会逐渐销毁。

  • 静态多态和动态多态

    • 静态多态：编译阶段的多态。函数重载和函数模板
    • 动态多态：例如调用虚函数。程序运行的行为只有运行时才可确定。
    • 编译时操纵栈，运行时操纵堆。

  • 静态类型和动态类型

    • 静态类型：编译时就可以明确的类型。
    • 动态类型：运行时才可明确的类型，例如基类的指针。

  • 绑定

    • 所依赖的函数和属性。在继承体系中只有虚函数使用的是动态绑定，其他的全部是静态绑定。
    • 因此，千万不要重新定义非虚函数，因为这样完全是静态绑定，并不能实现多态，没有任何重写的意义。

  • 4种智能指针

    • auto，shared，weak，unique

  • 进程间的通信方式，每种方式的特点优缺点

    • 管道：字节流（半双工）
    • 消息队列：链表
    • 信号量
    • 共享内存

  • 什么是平衡二叉树

    • 任意结点的两颗子树的高度相差<=1。

  • 指针和引用有什么区别

    • 引用只能单级
    • 引用不是地址，而是别名
    • 引用不能为空
    • 引用初始化后不能改变指向的目标
    • 引用sizeof后返回真实的大小，而不是地址大小

  • 继承和多态的区别

    • 多态按字面的意思就是多种形态。当类之间存在层次结构，并且类之间是通过继承关联时，就会用到多态。
    • C++ 多态意味着调用成员函数时，会根据调用函数的对象的类型来执行不同的函数。

  • C++11新特性？C++17新特性？

    • volatile
      • 例如volatile int x=1；声明后，每次访问它，都只会直接找到存储地址去访问，而不会放到寄存器中，从而避免了多线程情况下，两者不一致的问题。防止了编译器优化带来的帮倒忙问题。
    • final：类不可继承；
    • override：声明重写了父类的虚函数。（用于检查是否真的有这个虚函数）
    • delete：禁止调用某个构造函数
    • default：自动生成默认构造函数 例如A()=default;

  • unique_ptr，shared_ptr与weak_ptr

    • 不同的 shared_ptr指向同一个内存对象，shared有引用计数器，如果这个对象有新的shared_ptr指向他，计数器++；当计数器=0，内存空间才会被销毁；（具体来讲，就是只要离开了指针的作用域，指针指向的内存空间也跟着销毁了）
    • 不同的unique_ptr不能指向同一个内存对象。unique相当于一个计数器恒为1的。
    • waek_ptr相当于观察者。并不会影响其指向的内存的存亡情况。

  • vector扩容

    • 要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素。

  • TCP可靠传输

    • 序号（第一个字节的序号），超时，重传

  • mysql 查询优化  高频读写优化  高并发优化等等

    • 高并发优化
      • 缓存
      • 主从复制
      • 分区、分表
        • 大表的定义是存储的数据条数过多，导致查询起来比较慢
        • MySQL在创建表的时候可以通过使用PARTITION BY子句定义每个分区存放的数据。将一大表，根据条件分割成若干个小表。
        • 分区是把一张大表虽然存储上不在一起了，但用户角度还是一张大表；分表是指物理上分成独立的表格，逻辑上根本就不是一张表了
        • 可以按range划分，比如值在哪个范围的分到哪个表。另外还有哈希。

  • get和post

    • POST比GET 安全，因为数据在地址栏上不可见
    • 对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok
    • 然而，从传输的角度来说，他们都是不安全的，因为HTTP 在网络上是明文传输的

  • 对称锁和非对称锁

  • DNS污染，如何解决？

    • 对DNS服务器进行一些操作，导致即便是域名正确，也故意返回错误的IP地址，导致网站无法访问
    • 更换DNS服务器；使用第三方DNS解析服务

  • DNS劫持，如何解决？

    • 对DNS服务器进行一些操作，导致篡改域名解析本应得到的IP地址反馈

  • 什么是事务，事务的实现原理

    • 原子性——事务回滚：
      • undo log实现对操作的记录，当需要回滚的时候执行相反操作。它是逻辑日志，以update为例，会记录行的主键，哪些属性被修改了，修改前后的信息变化等。每做一次修改，undo log里面都记录了和这次修改可以完全抵消的操作。
      • undo log一定是先于真正的修改被持久化到磁盘上
    • 一致性——事务前后，必须从一个一致性状态变换到另一个一致性状态：由原子性、隔离性、持久性提供了保障；此外，应用层也应当避免向数据库输入错误的逻辑。
    • 隔离性：锁、几种隔离等级。
      • 三种读取失败
        • 脏读：读取到别的事务未提交的老数据
        • 不可重复读：第一次读，别的事务未提交；第二次读，别的事务已提交；即第一次是脏读数据，后一次是新数据，称为不可重复读
          • B执行c+=100; A查询c；B提交；A查询c;
        • 幻读：按照完全相同的where条件查询两次，获得的结果数量却不同
          • 例：A读取工资<2000的人，共5个；B给某员工降低薪资到2000以下并提交；A又读一遍工资<2000的人，共6个。
      • 对应了四种隔离级别
        • 读未提交：gg
        • 读已提交：无脏读
        • 可重复读：无重复读
        • 可串行化：无幻读
      • MVCC
        • 可同时解决脏读、不可重复读、幻读等问题，且读不需要加锁，称为多版本并发控制协议
    • 持久性：redo log与binlog。
      • 数据库有缓冲池。当大批量修改请求来临，直接对磁盘进行大量IO会导致效率大打折扣。于是会先写入缓冲池，然后IO会对缓冲池进行轮询，慢慢地写入磁盘中。
      • 如果断电，缓冲池就丢失了。此时redo log就派上用场了，每次更新数据后，都会紧接着写入redo log缓冲区，然后redo log写入磁盘，这个过程比执行更改后的写入要快得多，因为它写入的都是有效数据，而且是顺序存放的，效率高（但是查询后的修改是随机访问，且就算写入一个块，其中有用的更改也很少）
      • binlog实际上并不负责持久性的维持。binlog是用于mysql主从复制的。它只在事务提交时写入，而且是存储的二进制文件，相当于磁盘快照。但是redo log存储的是逻辑操作，具有可恢复的逻辑性。
start transaction;
……  #一条或多条sql语句
commit
  • DNS是TCP还是UDP，为什么
    • DNS会通过浏览器缓存-操作系统缓存-路由器缓存-ISP缓存走一波，如果都没有，就到根域名服务器开始查询，最后逐级存入缓存。
    • 在一个区中主DNS服务器从自己本机的数据文件中读取该区的DNS数据信息，而辅助DNS服务器则从区的主DNS服务器中读取该区的DNS数据信息。当一个辅助DNS服务器启动时，它需要与主DNS服务器通信，并加载数据信息，这就叫做区传送（zone transfer）。辅DNS服务器不能离开主DNS服务器而存在。
    • DNS区域传输的时候使用TCP
      • 辅域名服务器会定时（一般3小时）向主域名服务器进行查询以便了解数据是否有变动。如有变动，会执行一次区域传送。
    • 域名解析时采用UDP。
      • 快，且性能负担小。
  • SOCket位于哪一层；
    • 传输层
  • 字节对齐
struct my
{
    char a;
    short b;
    char c;
    int d;
    char arr[3];

	单字节对齐占多少字节？1+2+1+4+3=11

4字节对齐：1（1）+2+1（3）+4+3+（1）=16（按小的补齐）
};
  • 页面置换算法
  • 栈里面存了啥？
  • C++让进程进入等待
    • sleep以毫秒为单位，例如可以1000*5。
  • malloc/free和区别new/delete
    • malloc需要手动计算空间，而且返回void*。如果创建失败，返回NULL，还得自己判空。
  • tcp 保活
    • 好处
      • 长连接可以避免创建连接的等待。短连接和长连接的优势，分别是对方的劣势。
      • 可以检测挂掉了的连接。
    • TCP会在空闲了一定时间后发送数据给对方，如果对方ACK了，就保活了。如果没有任何应答，就重发，如果2小时内一直是这样，就自动关闭连接。
    • 如果对面程序已经正常退出，就发RST，如果对面程序已经崩溃，就发FIN，从而断开TCP连接。
  • http 长连接
    • 完成请求后，不立即关闭依赖的TCP连接。这个可以是服务器和浏览器协商，决定是否在传输完成后保持TCP连接不断开。
    • 在http1.1上，虽然长连接，但是只支持串行发送，且是文本传输，于是只支持一问一答的形式。于是就需要阻塞等待。
  • http 2.0的帧和流
      • http2.0支持长连接上的并发发送请求。同一个域名下只需要一个TCP连接。同一 Tcp可以同时承载双向的并发数据流。
    • 帧代表着最小的数据单位，每个帧会标识出该帧属于哪个流，流也就是多个帧组成的数据流
    • 因为是二进制，所以不再要求一问一答，可以乱序，于是不需要阻塞等待。因为上面有帧编号，可以标志它属于哪个流。 ![[Pasted image 20220310222944.png]]
  • extern “c"
    • 这样就可以让C++的编译器用处理C函数的方式来处理C代码
  • 四次挥手完会立马关闭吗（会监听一段时间 这个时间具体是多少？）
    • 要等待2MSL（MSL是报文段最大寿命），这是为了实现服务器端传输完成后表示可关闭连接的信息的重传。根本原因是害怕客户端没收到这个信息，导致不给自己发ACK，自己就得等待。因为客户端那个ACK来了，自己才可以真正关闭连接。
  • 协程
    • 一个线程可以有多个协程。
    • 协程比线程更加轻量化，只在用户态运行
    • 是一个特殊的函数，可以被挂起，可以继续开始执行
    • 但是协程不支持并发，即只能串行执行，一个线程中在一小段时间内只能有一个协程跑，其他的都被挂起。
    • 协程的切换只涉及寄存器和栈。
char* strs = (char*) malloc(sizeof(char)*10);  
sizeof(strs);
  • sizeof如果是数组名，则给出整个数组的空间大小；如果是指针，则只给出指针变量的大小。可以使用sizeof数组名除以sizeof数组内数据类型的方式来计算长度。
  • 64位下，指针是拉满的（8字节），int是兼容32位的（4字节），long是拉满的（8字节），float是兼容32位的（4字节），double是拉满的（8字节）：
    • char ：1个字节
      char*(即指针变量): 8个字节
      short int : 2个字节
      int：  4个字节
      unsigned int : 4个字节
      float:  4个字节
      double:   8个字节
      long:   8个字节
      long long:  8个字节

算法 #

  • 各大排序算法的时间复杂度和空间复杂度？稳定性？
  • 每k个元素翻转单向链表
  • 二叉树节点之间的最大距离
  • 手写个快排
  • 乱序数组求第k大的元素
  • 最长不重复子串
  • 不相交路径，往东南西北四个方向走，判断路径是否有相交
  • 高精度再看一遍
  • 数组最大子序和
  • 给一个数组（正负数都有），让你找最大子数组的和
  • 100亿个数，最大的1000个，说说复杂度
  • 回文子串个数
  • 无序数组的中位数 
  • 螺旋矩阵
  • 股票最大盈利 一次买卖
  • 二叉树Z遍历
  • 最少硬币数组成指定金额
  • 一棵树是否是镜像树
  • 找出表student里所有score大于等于80小于90的记录并按score降序输出
  • 二进制位倒序
  • 恢复IP地址

智力 #

  • 10000个人同时抛硬币，如果正面就停止，如果反面就一直继续抛直到正面为止，求最后正反面比例？

    • 一样。同下一题。

  • 一个村庄重男轻女，生不到男的就会一直生下去，求最后男女比例

    • 一样。P{X=n}=1/(2^n)，则生孩子数量的期望是n/(2^n)的求和，从1到无穷。可以算出这个期望是2，所以必然是1男1女，所以男女比例1：1.

  • 1000个苹果放10个箱子，怎样才能给出任意的数字，都能在O（1）的复杂度下取出？

    • 二进制。编号0-9箱子，分别放1，2，4，8，16…个苹果。

  • 有8瓶液体，其中一瓶是毒药，毒性可使小白鼠饮用后在20小时内阵亡，需要几只小白鼠才能在20小时内判断哪一瓶是毒药？

    • 给八个瓶子编号000-111，让三只小老鼠分别喝对应位上是1的药。最后根据死的情况即可。

  • 给8个小球，7个质量相同，一个重一点，给你一个天平，称几次可以称出来。

    • 两次。第一次取6个，各3个放在两边：
      • 一边重：取重的中的2个，再称一次；
      • 一样重：重的在剩下的2个里。然后再称一次。

  • 有n个点，都落在圆周上，问所有点都落在直径一侧的概率是多少

    • 先画一条直径，然后任取n个点里面的一个作为第一个点（n种取法），然后要保证剩下的n-1个点都落在直径的和第一个点相同的半边，每个点都是1/2的几率，所以是1/2^(n-1)，所以答案是$\frac{n}{2^{n-1}}$.

  • 64匹马8个赛带，找出最快四匹的次数

  • 有25匹马，速度都不同，但每匹马的速度都是定值。现在只有5条赛道，无法计时，即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名？（百度2008年面试题）

  • 先进行5场比赛，分别随机把25匹马分成5组进行。

    取这5组的第一名，再进行第6场比赛，可以确定25匹马中最快的那一匹了。

    然后按第6场比赛的马的名次，对其前五场比赛所在的组分别编号ABCDE。

    例如第6场比赛的第一名所在组为A组，第6场比赛的第三名所在组为C组，……。

    可以从这5组中寻找可能成为25匹马中前三名的马。即：对于一只马，如果只可能有1匹或2匹马比他快，则把这只马拎出来。可见，对于A组的2，3、B组的1，2、C组的1是可以的。（因为以C组为例，已经有A的1和B的1比他快了，所以只有这里的1是有可能的。）

    再进行一场包含上述这5匹马的比赛。其前2名就是25匹马的第2、3名。

  • 地上有20枚硬币，一次只能捡一个或两个，两个人轮番减，谁最后拿硬币谁输。你怎么能确保赢？如果地上是18枚硬币呢？21枚呢？

    • 倒推思想：2(拿1必赢),3(拿2必赢),4(不可能赢，因为拿了之后，对面会变成1或2)，5(拿1可变成4，让对面不可能赢)，6(拿2可变成4，让对面不可能赢)，7(拿1变6，拿2变5，于是不可能赢)，8(拿1变7，对面不可能赢)，9(拿2变7，于是对面不可能赢)，也就是：23x56x89x，3个一组进行循环，于是18、20、21都可以赢。

  • 16个硬币，A和B轮流拿走一些，每次拿走的个数只能是1，2，4中的一个数。谁最后拿硬币谁输。
    问：A或B有无策略保证自己赢？
    答案：剩2个时，取1个必胜；
    剩3个时，取2个必胜；
    剩4个时，如果对手足够聪明则必败；
    剩5个时，去1个必胜…
    记作2（1） 3（2） 4（x） 5（1） 6（2） 7（x） 8（1）…
    从中找出规律：
    当剩余个数K=3N-2,N为自然数时，只要对手足够聪明则必败。
    当K=3N-1时，有必胜策略：取1个；
    当K=3N时，有必胜策略：取2个；
    所以，当16个时，后取者有必胜策略

  • 两人拿球，给定规则，如何使自己赢

    • 题目：100个球，两人拿，一次1-5个，甲必胜的策略

      思路：100/6=16余4,

      那么策略为 甲先拿4个球，然后当乙拿了x个球，甲拿6-x即可，最后不管乙拿了多少个，甲都能保证一次性拿完。 （因为以后每一局对垒必然双方共拿走6球，这样最后必然剩下4，我必然能拿走。除数是6就是为了掌握主动权，因为对方最多5个）

      题目：100个球，两人拿，一次不超过4个，第一回0~4个，后面的人必须最少拿一个，甲必胜策略

      思路：100/5=25余0

      那么策略为甲先拿0个…

      题目：1001个球，两人拿，一次只能拿1,2,4次，甲先拿，最后一个拿球的人输，甲必胜策略。

      思路：1001-4=997，不能被3整除，所以甲先拿4个，后面不管乙拿多少个，甲可以保证和乙的和能被3整除（3或6），这样最后剩下的一个球肯定就是乙的。

其他知识 #

  • AVL树
    • AVL树的定义是：对所有根节点，其两颗子树的高度相差不超过1的二叉搜索树。
  • 版本控制工具的作用
    • 可以滚回到任意时间点
    • 可以记录任意时刻的开发历史
    • 支持并发
    • SVN，CVS，git
  • git的理解？
    • git可以把仓库的所有内容都克隆下来，在一定程度上避免了单点故障，最初是为了更好地管理Linux内核而发明。
    • git通过计算散列（SHA-1）来判断任意的文件是否被修改
    • 本地add后，到暂存区，可以把需要跟踪的文件index下来；在commit时，会提交到本地仓库（版本库）。当版本库有更新，就可以push到远程仓库。
    • 远程仓库fetch或clone可以到本地版本库；本地checkout可以到工作区。远程仓库直接pull可以覆盖本地工作区，pull相当于先fetch/clone再checkout。
    • fork是创建了仓库的一个拷贝，包含了源仓库的任何内容，包括分支，提交记录等。这样可以开发你的模块。当想要把开发的模块汇入源仓库，可以发送pull request请求，请求把自己的贡献合并到大的产品里面。
    • clone会把远程仓库的每个版本的每个源码都拉下来，所以可能会非常大
    • 通过branch可以创建新分支，这样可以再不影响其他开发的情况下开发自己的东西，然后可以通过checkout切换分支。branch和fork挺像的，只是前者是在当前代码仓库基础上操作，而后者直接复制了一个。
    • head、索引、工作树？
      • head指针是永远指向所在分支的最新提交的。
      • git add就是添加到索引。凭借索引，可以只提交一部分文件，只提交自己修改的部分。这就是中间加一层的好处。例如.gitignore就可以实现自动过滤。
      • 工作树就是我们的工作区。我们敲代码的地方。
    • pull和fetch的区别？
      • fetch只是取到本地仓库，然后由用户决定是否要merge。而pull会取回并与当前branch合并（强行执行merge，必然要让用户进行处理），相当于fetch+merge。后者更加简单粗暴，在工作中常用。
      • 他们的作用是，当协作时远程仓库的代码更新时，用它来保证我们和远程新版本代码的同步。远程代码因为在我们上一次提交之后才提交，所以会有更加新的commit编号，这就导致我们fetch或者pull就需要进行diff修改。
    • git的快速合并机制、在什么情况
      • 如果A已经提交完成了，B才创建分支，这时候B的分支里包含了所有A提交过的记录，如果B修改了并提交，A一直没有新的修改，A如果fetch，不会有任何问题，因为这符合快速合并机制。
      • 如果上述场景下，A在B提交后又有新的修改，那么就导致B的分支不包含所有A的commit，当A要合并时，就会要求手动消除冲突。
    • git merge是创建新的commit，从而合并，然后两个分支的HEAD还分别在两个分支上；git rebase是粗暴地把一个分支嫁接到另一个分支上，并让其中一个分支不再可用（原地消失），而且不会修改另一分支的HEAD，因此还需要再merge一下。
    • git reset是直接删除一些commit达到回滚的目的，head向后走；git revert是创建新的commit，达到抵消的目的，使新的commit是回滚了的。
  • 而对线程而言，除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源

字节对齐 #

  • 因为访问内存并不是按字节访问，而是常用2，4，8这样的整数倍进行访问（数据总线宽度决定），所以为了高效，会进行字节对齐 - 结构体首地址应当对齐（可被对齐的字节数所整除） - 结构体每个成员相对于结构体开始的位置偏移应当是其大小的整数倍 - 结构体大小应当是其最大成员大小的整数倍
  • 例如程序
struct test
{
    int a;
    char b;
    int c;
    short d; //注意short是2B。
};
  • 实际上test的sizeof是16B，但是a是4B，b是1B，c是4B，d是2B，本来应该是11B。
  • 结构体起始位置对齐：应当从2，4，8这样的整数处开始
  • 成员相对于结构体的偏移对齐：a从0开始，ok；b从4开始，ok（5/1可以整除）；c从5开始，不ok，应该从8ok，所以填充3到7；d从12开始，ok，此时整个大小是11+3=14B；
  • 结构体大小对齐：这个14B却不是最大成员（4B）的整数倍，所以再填充2个字节到尾部，即可。
  • 关于字节对齐的优化：因为结构体变量的空间排布是由上到下的，如果适当调整结构体内变量的排布顺序，可以优化存储空间。例如先short再int，就可以让d从6开始即可，于是只需要填充1个B，然后c可以从8开始，没问题。因此整个存储空间压缩到了12B，而且还是最大成员（4B）的整数倍！
  • 跨平台时，如果双方约定的对齐方式不同，就会出现问题。此时可用#pragma pack(1)预处理指令强制按1B对齐。
  • 32位默认按4字节对齐（因为4*8=32，这样是字长的存取长度），64位显然就是按64bit对齐，也就是按8B对齐咯。

大小端存储 #

  • 小端存储：低地址存放低字节数据。x86、ARM都是小端。
  • 判断大端或小端的程序：可以使用共用体，因为int是4B，所以拆成4元素的char数组。
union un {
    int i;
    char c[4];
}un1 = { 134480385 };

int main() {
    printf("%c\n", un1.c[0] + '0');
    printf("%c\n", un1.c[1] + '0');
    printf("%c\n", un1.c[2] + '0');
    printf("%c\n", un1.c[3] + '0');
    system("pause");
    return 0;
}

数据库优化（除索引外） #

  • 最左前缀匹配原则：让更有价值的索引字段先被匹配
  • 尽量把子查询换成连接：因为子查询需要在内存中存储临时表
  • 避免全表扫描：考虑在范围限定相关的字段上建立索引
  • 尽量使用数字型字段，若只含数值信息的字段尽量不要设计为字符型。因为字符串比较的复杂度（逐字符比较）要高于数字比较
  • 尽量避免使用游标，因为游标的效率较差
  • 尽量避免大事务操作，提高系统并发能力
  • 用union（联合查询）来替代多次查询MySQL必知必会：组合查询（Union） - SegmentFault 思否，这样不会产生过多的临时表
  • 合理的数据库设计：尽量避免冗余（例如一个表包含了过多字段），要使用范式
  • 负载均衡：类似于主从复制
  • 使用缓存：key-value
    • 可用hashmap，也可用redis
    • 缓存穿透：如果key对应的value是一定不存在的，并且对该key并发请求量很大，就会对后端系统造成很大的压力。这就叫做缓存穿透
    • 缓存雪崩：如果很多缓存几乎同时超过了TTL，就会需要集中更新，导致后端压力

游标 #

  • 游标的作用就是用于对查询数据库所返回的记录进行遍历，以便进行相应的操作。
  • 但是它是只读的，且移动只能是单向的，且只能顺序读取。这就好比一个单链表的操作。
DECLARE cursor_name CURSOR FOR select_statement;
  • 这里声明了一个基于select_statement的游标，它可以对这个select_statement返回的查询结果进行遍历操作。
  • 使用FETCH时游标属性%ROWCOUNT会不断累加。也就是说，游标是随着fetch指令的调用自动向前遍历的。

智能指针 #

  • 为什么引入智能指针？ 1）使用裸指针分配内存后，没有对指针释放资源会导致内存泄漏；2）多个裸指针指向同一资源时，多次释放资源时，对空悬指针进行释放会导致不可预知的错误。
  • C++11之前，auto_ptr被废弃，因为一直保证指针属主的唯一性。那么比如说我要传递一个参数，或者我要赋值给其他的一个同类型的智能指针变量，那么原智能指针的所有权就到了传过去的参数或是被赋值的指针变量上了，原来那个的就成了null了。这个时候如果再拿他去访问就会出现问题。
  • auto_ptr的继任者是C++11后的unique_ptr。因为他们都保证了“独占”。为了避免函数调用的时候因为所有权变更而导致的内存释放，可以使用 fun (move (uptr));。unique_ptr不支持拷贝构造和赋值构造，但是可以move。
  • weak_ptr只能和shared_ptr配合使用，可以用shared_ptr来初始化weak_ptr。否则单独使用没有任何实际意义。weak_ptr可以被shared_ptr赋值，但是不会增加引用计数；同样的，weak_ptr在被销毁时不会影响到引用计数和实际内存空间。
    • weak_ptr可以通过调用lock函数来获得shared_ptr。因为weak_ptr没有重载“->”和“*”，所以如果要通过weak_ptr访问对象，只能先用lock转换成shared_ptr.
    • 如果使用lock，返回了nullptr，就说明观察的资源已被释放。因为shared_ptr释放资源是完全不管不顾weak_ptr的感受的。
  • shared_ptr成环引用（死锁问题）：如果两个shared_ptr相互引用，那么引用计数值不可能降为0.这是因为在fun结束时，虽然pa和pb的声明周期结束，引用数分别都从2减到了1，但是pa指向的对象和pb指向的对象并没有到结束条件，因为他们各自被对方持有的指针指向了。除非一方不再指了，让对方的计数器减到0，才可能达到释放条件。
    • shared_ptr的计数器在堆上面。众所周知栈是静态的，是编译器预定好的，而堆是动态的，所以 shared_ptr的计数器是动态的。
include <iostream>
#include <memory>
#include <string>
using namespace std;

class B;
class A
{
public:
    shared_ptr<B> pb_;
    ~A()
    {
        cout << "A delete\n";
    }
};
class B
{
public:
    shared_ptr<A> pa_;
    ~B()
    {
        cout << "B delete\n";
    }
};

void fun() {
    shared_ptr<B> pb(new B());
    cout << "pb.use_count " << pb.use_count() << endl;//1
    shared_ptr<A> pa(new A());
    cout << "pa.use_count " << pa.use_count() << endl;//1

    pb->pa_ = pa;
    cout << "pb.use_count " << pb.use_count() << endl;//1
    cout << "pa.use_count " << pa.use_count() << endl;//2
    pa->pb_ = pb;
    //由于share_ptr是共享资源，所以pb所指向的资源的引用计数也会加1
    cout << "pb.use_count " << pb.use_count() << endl;//2
    cout << "pa.use_count " << pa.use_count() << endl;//2
}//程序结束时，没有调用A和B的析构函数
//如果把其中一个类的shared_ptr改成weak_ptr，程序结束的时候，两个对象的析构函数就都被调用了。

int main()
{
    fun();
    system("pause");
    return 0;
}

这个时候，只要把其中一个类的shared_ptr改成weak_ptr即可解决问题。但是注意，如果还要打印，就要先lock一下。

  • make_shared()、make_unique()和直接调用构造函数以构造智能指针的区别
    • 前者是一次性把需要的内存分配完成；后者需要先分配new的内存，再分配智能指针的内存。
  • 如果把一个原生指针交给多个智能指针（除weak外）管理，就会导致内存被释放多次！程序崩溃。

explicit关键字 #

  • C++的构造函数默认是implicit关键字修饰，表示在构造时可以发生隐式类型转换，从而自动适配构造函数的参数类型。
  • 如果给一个构造函数前加explicit声明，则例如把一个string类型的变量塞给char*的构造函数参数都会报错。

左值和右值 #

  • 左值（Location value）：可以根据他寻址，可以给他赋值（除了const），表达式结束后依然存在的持久对象，可以取地址，有名字
  • 右值（Read-only value）：只能读其值，达式结束后就不再存在的临时对象，不可以取地址，没有名字

僵尸进程的危害 #

如果子进程在父亲进程结束前结束，父亲进程还不wait，就是僵尸进程

  • 如果父亲进程还在跑，但是子进程退出，父进程还不wait它，子进程就是僵尸进程。子进程的返回值在PCB里面，没人去收取。僵尸进程是不负责的父亲导致的。
  • 虽然进程的退出状态未被父进程取出前，除了PCB以外，其他所有资源都可以释放。但由于PCB不释放，它原本的pid也会继续被占用，当僵尸进程数量很大时，系统将无可用pid分配给新进程，从而加载进程失败。
  • 可以通过kill -9它父亲进程的方式kill僵尸进程

孤儿进程和僵尸进程的区别 #

如果子进程在父亲进程结束后结束，就是孤儿进程

  • 如果父亲进程在子进程结束前提前退出，子进程还没有结束呢，此时子进程的父亲提前离世，子进程变成了孤儿，于是只能让init进程（0号）当后爸。
  • 与僵尸进程不同，init进程能很好地进行善后。因此孤儿进程没有什么危害。

STL中快速排序的优化方法 #

  1. 优化一，在选择哨兵的时候使用三数取中法，即取序列第一个元素、中间元素以及最后一个元素，再取这三个元素的中位数作为哨兵，这样可以避免取到边缘值而导致每次分割不均匀的情况；
  2. 优化二，因为在递归分割序列时，序列的长度会越来越短，又因为短序列排序中插入排序效率最高，所以可以设置一个阈值，当序列长度分割到阈值时切换到插入排序，提高效率；
  3. 优化三，当序列中存在大量相同元素，或者全是相同元素时，使用快排仍然会得到最低的效率，这时可以采用聚集相等元素的方法，每次选择哨兵后，将与哨兵相同的元素放到序列中间，下次分割时中间这些值不参与分割；
  4. 优化四，当递归层数过深的时候改用堆排序，虽然第一个优化方法避免了取到边缘哨兵，但还是有可能取到较边缘的哨兵，最坏的情况会导致递归层数过深，从而降低快排效率，所以每次递归要判断递归层数，达到一定深度就改用堆排序。之所以要用堆排序，我猜想可能是因为快排和归并都是基于递归的排序，此时递归深度已经太深，肯定不能再用了，而对于较长的序列使用插入排序效率也不是太高，所以选择了堆排序。
↑