# 前言  这篇面经来自一位粉丝的投稿，他在前天也就是6月9号通过了字节跳动的一面，分享了一些面试遇到的问题，然后我整理了出来，希望对即将参加面试的你们有一些帮助。 **我们先来看一下他被问了哪些问题** * 自我介绍 * 看你简历上写了死锁，简单介绍一下？ 更改你的代码，使死锁解除？ * 讲讲系统调用？ * 进程线程区别？ * 进程通信几种方式？哪种方式最快？为什么？ * 进程怎么分配的？PCB里面都有什么？为什么进程上下文切换消耗大量资源？ * 进程调度算法？ * 刚刚你说到零拷贝，简单说一下过程？ * 谈谈你常用的数据结构 * 你都知道哪些树结构？说说他们特性？（搜索树、平衡树、红黑树、B树、B+、霍夫曼） * 细讲红黑树 * 霍夫曼树算法贪心策略证明。 * 刚刚你说到栈和队列可以互相转换，写出代码。 * 说说常见的排序算法 * 快排缺点？怎么避免？手撕上面3个算法？ **除此之外还有两个反问：** * 我还有什么需要增强的？ * 如果可以参加项目开发，我还需要学习什么新技术？ 除了这些之外我还整理了一些别的大厂面试真题 可以分享给大家，需要的朋友可以直接点击[**一线大厂面试题合集传送门**](https://jq.qq.com/?_wv=1027&k=PjEVS3qt)即可领取 # 题解 好，现在我们一道一道的来看问的这些问题 ## 1、自我介绍  面试自我介绍虽然人人都准备，但是做到让人印象深刻可不容易啊，甚至有的人压根都不重视，只想靠技术折服面试官，当然了，如果真的是很牛的技术大牛，那应该是没问题。 **面试是什么？** 它是个机会，让面试官更进一步确认你是他们需要的人，你进一步展现你的交际沟通能力。 So **一定一定要记住，自己是在跟人打交道，而不是对机器答问题！** 首先，为啥面试官要提这个问题呢？简历里面不是写得好清楚好详细了吗？ 其实呢，这个问题，据很多做面试官的朋友所说，要是**给面试官一个缓冲的时间来重新熟悉你的简历**。 所以，我们要通过自我介绍提醒面试官，**你的特点和你为什么特别合适这个职位**。当然了，语言尽量简练，咨询了一些资深面试官后我总结了面试的3个要点，给大家参考一下。 **时间控制在1分钟，写在纸上就是120－160个字：** * 我是谁 * 我的三个亮点，最近最相关的经历？ * 我为什么想要这份工作？ 这三个点用精炼的语言表达清楚自我介绍这一块基本就没什么问题了。 ## 2、死锁怎么解决 解决死锁一般有四个阶段，即 * 死锁预防 * 死锁避免 * 死锁检测 * 死锁解除 死锁预防： 破坏导致死锁必要条件中的任意一个就可以预防死锁。 例如： **（1）破坏占有且等待条件：** 一次性申请所有资源，之后不再申请资源，如果不满足资源条件则得不到资源分配。 **（2）破坏不可剥夺条件：** 当一个进程获得某个不可剥夺的资源时，提出新的资源申请，若不满足，则释放所有资源。 **（3）破坏循环等待条件：** 对资源进行排号，按照序号递增的顺序对资源进行申请。若获得高序号的资源想要申请低序号的资源，需要先释放高序号的资源。 死锁避免： 进程在每次申请资源时判断这些操作是否安全。 **例如：** 使用银行家算法：指在分配资源之前先看清楚，资源分配后是否会导致系统死锁。如果会死锁，则不分配，否则就分配。 死锁检测： 判断系统是否属于死锁的状态，如果是，则执行死锁解除策略。 死锁解除： 将某进程所占资源进行强制回收，然后分配给其他进程。（与死锁检测结合使用的） ## 3、系统调用 在我们运行的用户程序中，凡是与系统级别的资源有关的操作（例如文件管理、进程控制、内存管理等）都必须通过系统调用方式向OS提出服务请求，并由OS代为完成 平常我们的进程几乎都是用户态，读取用户数据，当涉及到系统操作，计算机资源的时候就要用到系统调用了 **系统调用的功能大致分为** > 系统调用的功能与其作用一样——涉及计算机资源的操作 * 设备管理：完成设备的请求/释放以及设备的启动 * 文件管理：完成文件的读写、删除、创建等功能 * 进程控制：完成进程的创建、撤销、阻塞以及唤醒等功能 * 内存管理：完成内存的分配、回收以及获取作业占用内存区大小和地址等功能 ## 4、进程线程的区别 进程是一个在内存中运行的应用程序。每个进程都有自己独立的一块内存空间，一个进程可以有多个线程，比如在Windows系统中，一个运行的xx.exe就是一个进程。 线程是进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据。 与进程不同的是同类的多个线程共享进程的堆和方法区资源，但每个线程有自己的程序计数器、虚拟机栈和本地方法栈，所以系统在产生一个线程，或是在各个线程之间作切换工作时，负担要比进程小得多，也正因为如此，线程也被称为轻量级进程。 ## 5、进程通信的几种方式 * **无名管道( pipe )**：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。 * **高级管道(popen)**：将另一个程序当做一个新的进程在当前程序进程中启动，则它算是当前程序的子进程，这种方式我们成为高级管道方式。 * **有名管道 (named pipe)**： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。 * **消息队列( message queue )**： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。 * **信号量( semophore )**： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。 * **信号 ( sinal )**： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。 * **共享内存( shared memory )** ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。 * **套接字( socket )** ： 套接口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。 ## 6、进程调度算法 基于进程调度的两种方式的调度算法如下： * 先来先服务（FCFS）调度算法 * 短作业优先（SJF）调度算法 * 时间片轮转（RR）调度算法 * 最高优先级优先调度算法 * 多级反馈队列(MFQ)调度算法 这里篇幅所限，就只讲一下前面两种吧，其余的如果感兴趣可以自己找资料看看 **先来先服务(FCFS)调度算法** 1、简介：先来先服务调度算法是一种最简单的调度算法，可用于作业调度，也可用于进程调度。 2、原理：在进程调度中采用先来先服务算法的时候，每次调度就从就绪队列中选一个最先进入该队列的进程，为之分配处理机，即谁第一排队谁就先被执行。 3、优点： 有利于长作业（进程） 有利于CPU繁忙型的作业（进程） 4、缺点： 不利于短作业（进程） 不利于I/O繁忙型的作业（进程） **短作业优先(SJF)调度算法** 1、简介：短作业（进程）优先调度算法是指短作业或者短进程的优先调度算法，它们分别作用于作业调度和进程调度，它是先来先服务调度算法的一种优化版本。 2、原理：短进程优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，再将处理机分配给它，直到执行完成，而其他进程一般不抢先正在执行的进程。 3、优点： 算法对长作业（进程）不利（长作业（进程）长期不被调度） 未考虑进程的紧迫程度 由于是估计运行时间而定，而这个时间是由用户所提供的，所以该算法不一定能真正做到短作业优先调度 ## 7、零拷贝过程 这里给你们看张图应该就是明白了，面试的时候如果遇到这道题，用自己的话说出来即可  ## 8、常用的数据结构 这个你么根据自己的使用情况实话实说就可以了，数组，链表，队列，栈，树，Hash表这些，随便说个两三个就行。 ## 9、霍夫曼树算法贪心策略证明 **如何理解贪心算法？** 假设我们有一个可以容纳 100kg 物品的背包，可以装以下 5 种豆子，每种豆子的总量和总价值各不相同，为了使背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？  实际上，我们只要先算一算每个物品的单价，按照单价由高到低来装就好了。依次是黑豆、绿豆、红豆、青豆、黄豆，所以我们可以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆。 这个问题的解决思路本质上借助的就是贪心算法。结合这个例子，总结了一下贪心算法解决问题的步骤： 第一步、 当我们看到这类问题的时候，首先应该联想到贪心算法：针对一组数据，我们定义了限制值和期望值，希望从中选出几个数据，在满足限制的情况下，期望值最大。类比刚才的例子，限制值就是总量不能超过 100kg，期望值就是物品的总价值，这组数据就是 5 种豆子。 第二步、 我们尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况，对期望值贡献最大的数据。类比刚才的例子，就是每次从剩下的豆子里面，选择单价最高的，也就是重量相同的情况下，对价值贡献最大的豆子。 第三步、 实际上，贪心算法解决问题的思路，并不总能给出最优解。 举个例子，在一个有权图中，我们从顶点 S 出发，找一条到顶点 T 的最短路径（路径中边的权值总和最小）。贪心算法的结局思路是，每次选择都选择一条跟当前顶点相连的圈最小的边，直到找到顶点 T，按照这种思路，找出最短路径：S->A->E->T ，路径长度是 1 + 4 + 4 = 9。显然不是最短的，因为最短的是：S->B->D->T，总长度是 2 + 2 + 2 = 6  为什么贪心算法在这个问题上不工作了呢，主要原因是，前面的选择会影响后面的选择。所以即便我们第一步选择最优的走法，但有可能因为这一步选择，导致后面每一次的选择都很糟糕，最终也自然和最优解无缘了。 **霍夫曼编码** 接下来看看霍夫曼编码是如何利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的 假设我有一个包含 1000 个字符的文件，每个字符占 1 个 byte (1 byte = 8 bits)，存储这 1000 个字符就一共需要 8000 bits，那么有没有更加节省空间的存储方式呢？ 假设我们统计发现，这 1000 个字符只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制 bit 就可以表示8 个不同的字符，所以为了尽量减少存储空间的存储空间，每个字符我们用 3 个二进制位来表示，比如：a（000）、b（001）、c（010）、d（011）、e（100）、f（101），那么存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储节省了很多空间，那么还有没有更加节省空间的存储方式呢？ 这个时候就要用到霍夫曼编码了。霍夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。 霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。 如何给不同频率的字符选择不同长度的编码呢，根据贪心的思想，我们可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。 对于等长的编码来说，压缩起来很简单。比如刚才那个例子，用 3 个 bit 表示一个字符。在解压缩的时候，每次从文本中读取 3 位二进制，然后翻译成对应的字符，但是，霍夫曼编码是不等长的，每次应该读取 1 位，还是 2 位还是 3 位等等来解压缩呢，这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间不会出现某个编码是另一个编码前缀的情况。 假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f ，我们把它们分别编码成下面这样子，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会有歧义。经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。  尽管霍夫曼编码的思想并不难理解，但是如何根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？这里的处理稍微有些技巧。 * 我们把每个字符看作一个节点，并且附带着把频率放到优先级队列中。 * 我们从队列中取出频率最小的两个节点 f（20）、e（30） * 然后新建一个节点 x（50），把频率设置为两个节点的频率之和，并把这个新节点 x（50）作为 f（20）和 e（30）的父节点。 * 最后再把 x（50）放入到优先级队列中。重复这个过程，直到队列中没有数据。  * 现在我们统一给每一条边画一个权值，指向左子节点的边我们通通标记为 0，指向右子节点的边，我们通通标记为 1，那么从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。  ## 10、栈和队列转换代码 **用栈实现队列** ``` #pragma once #include "SqStack.h" class CQueue { public: CQueue(void); ~CQueue(void); CQueue(int size); void AppendTail(int e); int DeleteHead(); private: SqStack stack1; SqStack stack2; }; #include "StdAfx.h" #include "Queue.h" #include "SqStack.h" #include using namespace std; CQueue::CQueue(void) { } CQueue::~CQueue(void) { } CQueue::CQueue(int size) { stack1.stacksize = stack2.stacksize = size; stack1.top = stack1.base = new int[size]; stack2.top = stack2.base = new int[size]; } void CQueue::AppendTail(int e) { stack1.Push(e); } int CQueue::DeleteHead() { int a, b; if(stack2.GetSize() == 0) { while(stack1.GetSize() != 0) { a = stack1.Pop(); stack2.Push(a); } } if(stack2.GetSize() == 0) { cout<<"queue is empty"<<endl; return -1;//当队列元素全部删除时，返回-1 } else { b = stack2.Pop(); return b; } } #pragma once class SqStack { public: SqStack(void); ~SqStack(void); SqStack(int size); void Push(int e); int Pop(); int GetSize(); public: int stacksize; int* base; int* top; }; #include "StdAfx.h" #include "SqStack.h" #include using namespace std; SqStack::SqStack(void) { } SqStack::~SqStack(void) { } SqStack::SqStack(int size) { stacksize = size; base = top = new int[size]; } void SqStack::Push(int e) { *top = e; top++; } int SqStack::Pop() { int e; if(top == base) { cout<<"栈空"<<endl; } e = *--top; return e; } int SqStack::GetSize() { if(top == base) return 0; else return 1; } #include "stdafx.h" #include "Queue.h" #include "SqStack.h" #include using namespace std; int main() { int a, b, n; CQueue c(10); cout<<"请输入队列元素个数"<<endl; cin>>n; cout<<"请输入队列元素"<<endl; for(int i = 0; i < n; ++i) { cin>>a; c.AppendTail(a); } b = c.DeleteHead(); cin>>a; c.AppendTail(a); b = c.DeleteHead(); b = c.DeleteHead(); b = c.DeleteHead(); cout<<b<<endl; system("pause"); return 0; } ``` **用队列实现栈** ``` #pragma once class CQueue { public: CQueue(void); ~CQueue(void); void InitCQueue(); int QueueLength(); void EnQueue(int e); int DeQueue(); public: int* base; int front; int rear; }; #include "StdAfx.h" #include "Queue.h" #include using namespace std; #define MAXQSIZE 10 CQueue::CQueue(void) { } CQueue::~CQueue(void) { } void CQueue::InitCQueue() { base = new int[MAXQSIZE]; front = rear = 0; } int CQueue::QueueLength() { return (rear - front + MAXQSIZE) % MAXQSIZE; } void CQueue::EnQueue(int e) { if((rear + 1) % MAXQSIZE == front) { cout<<"队列满"<<endl; return; } base[rear] = e; rear = (rear + 1) % MAXQSIZE; return; } int CQueue::DeQueue() { int e; if(front == rear) { cout<<"队列空"<<endl; //return; } e = base[front]; front = (front + 1) % MAXQSIZE; return e; } #pragma once #include "Queue.h" class SqStack { public: SqStack(void); ~SqStack(void); SqStack(int size); void Push(int e); int Pop(); private: CQueue cqueue1; CQueue cqueue2; }; #include "StdAfx.h" #include "SqStack.h" #include "Queue.h" #include using namespace std; SqStack::SqStack(void) { } SqStack::~SqStack(void) { } SqStack::SqStack(int size) { cqueue1.InitCQueue(); cqueue2.InitCQueue(); } void SqStack::Push(int e) { cqueue1.EnQueue(e); } int SqStack::Pop() { int a; if(cqueue1.QueueLength() == 0 && cqueue2.QueueLength() == 0) { cout<<"栈空"<<endl; //return ; } else if(cqueue1.QueueLength() != 0) { while(cqueue1.QueueLength() != 1) { a = cqueue1.DeQueue(); cqueue2.EnQueue(a); } a = cqueue1.DeQueue(); return a; } else if(cqueue1.QueueLength() == 0 && cqueue2.QueueLength() != 0) { while(cqueue2.QueueLength() != 1) { a = cqueue2.DeQueue(); cqueue1.EnQueue(a); } a = cqueue2.DeQueue(); return a; } } #include "stdafx.h" #include "SqStack.h" #include "Queue.h" #include using namespace std; int main() { int r; SqStack s(10); s.Push(1); s.Push(2); r = s.Pop(); cout<<r<<endl; s.Push(3); r = s.Pop(); cout<<r<<endl; r = s.Pop(); cout<<r<<endl; system("pause"); return 0; } ``` # 小结 篇幅所限，我这里就只讲这十个题吧，毕竟面试题实在是太多了，除了这些之外，我还整理了一些别的大厂面试题，如果需要，可以直接点击[**一线大厂面试题合集传送门**](https://jq.qq.com/?_wv=1027&k=PjEVS3qt)领取 自己在面试中遇到的难题也可以发在评论区跟大伙讨论，那我们下篇文章见