字节跳动客户端二面面经（附答案）

### 主题一：C++

#### t1. 内存分配方式一般有哪些？堆和栈的差别？

1. 一般来说，程序运行时有三种内存分配方式：静态的、栈式的、堆式的：

（1）静态存储：是在程序编译时就已经分配好的，在整个运行期间都存在，如全局变量、常量。

（2）栈式存储：由编译器自动分配释放 ，存放函数参数、局部变量等。

（3）堆式存储：一般由程序员分配释放，若程序员不释放，程序结束时可由 OS 自动回收。如我们用 new，malloc 分配内存，用 delete，free来释放内存。

2. 堆和栈的区别主要有以下几点：

（1）申请方式

栈：由系统自动分配；

堆：需要程序员自己申请，并指明大小。

（2）申请后系统的响应

栈：只要剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出；

堆：操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。

（3）申请效率的比较

栈：由系统自动分配，速度较快。但程序员是无法控制的。

堆：是由 new 分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。

（4）申请大小的限制

栈：栈是向低地址扩展的数据结构，是一块连续的内存的区域。即栈顶的地址和栈的最大容量是系统预先规定好的，能从栈获得的空间较小。

堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

（5）堆和栈中的存储内容

栈：在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令的地址，然后是函数的各个参数，然后是函数中的局部变量。 当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令，程序由该点继续运行。

堆：一般是在堆的头部用一个字节存放堆的大小，堆中的具体内容有程序员安排。

#### t2. 宏和内联函数有什么区别？

1. 宏不能访问对象的私有成员，宏的定义很容易产生二意性。

2. 内联函数相比较于宏而言，内联函数要做参数类型检查，从而内联函数相比宏而言更加安全。

3. 内联函数在运行时可调试，而宏定义不可以。

#### t3. 可以有多继承嘛？如果有一个类C继承了类A和类B，A和B内有一个相同的变量a，那如何去区分呢？访问的是哪一个呢，能允许这种方式嘛？

1. C++ 支持多继承，即一个派生类可以有两个或多个基类。语法如下：

```c++

class C: public A, public B{

//类C新增加的成员

}

```

2. 在派生类中对基类成员的访问应该是唯一的。但是，在多继承情况下，可能造成对基类中某个成员的访问出现了不唯一的情况，这时就称对基类成员的访问产生了二义性，也称作命名冲突。

解决方法是，通过作用域运算符（::）明确指出访问的是基类 A 的变量 a，还是基类 B 的变量 a。可以在使用时候指明 A::a 还是 B::a，也可以直接在类中用该运算符直接定义同名成员。

### 主题二：操作系统

#### t1. 为什么要区分线程和进程的概念？一个进程里一定要有线程嘛？

1. 进程：进程是对运行时程序的封装，是操作系统进行资源分配和调度的最小单位

2. 线程：线程是进程的子任务，是CPU调度和分派（程序执行流）的最小单位

3. 一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程而存在

4. 进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存

5. 在早期的操作系统中并没有线程的概念，进程是拥有资源和独立运行的最小单位，也是程序执行的最小单位，任务调度采用的是时间片轮转的抢占式调度方式。后来，随着计算机的发展，对CPU的要求越来越高，进程之间的切换开销较大，已经无法满足越来越复杂的程序的要求了，于是就发明了线程。

#### t2. 线程共享进程的资源，具体是指什么资源？线程之间的资源是如何通信的？

1. 线程共享的资源有：全局堆，全局变量，静态变量，进程的各种文件等公用资源

2. 线程独享的资源有：栈，局部堆，寄存器组的值，线程ID、错误返回码、信号屏蔽码等

3. 线程通信常见的两种方式：

（1）使用 volatile 关键字：基于共享内存的思想。大致意思就是多个线程同时监听一个变量，当这个变量发生变化的时候 ，线程能够感知并执行相应的业务。

（2）使用 Object 类的 wait() 和 notify() 方法：基于等待唤醒机制。 当执行 notify 方法时，会唤醒一个处于等待该对象锁的线程，然后继续往下执行，直到执行完退出对象锁锁住的区域（synchronized修饰的代码块）后再释放锁。

#### t3. volatile关键字，如果有两个线程同时增加变量 i，为什么各执行了100次，结果不是 i = 200？

1. 原因：volatile 不保证原子性。

2. 原子性的含义：一个操作是不可中断的，要么全部执行成功要么全部执行失败。即多个线程一起执行的时候，一个操作一旦开始，就不会被其他线程所干扰。。

3. 具体解释：因为当线程 A 对 i++ 操作从自己的工作内存刷新到主内存时，还未通知到其他线程主内存变量有更新的瞬间，其他线程对 i 变量的操作结果也对主内存进行了刷新，从而导致了写值丢失的情况。（从汇编指令分析得，i++ 被拆成了三个步骤，读、写、改）

4. 解决办法：加 sync，锁住增加变量 i 的功能函数。

### 主题三：计算机网络

#### t1.传统网络分几层？HTTP是哪一层的？

1. 传统网络如果是OSI参考模型的话一共分为7层。如果是TCP/IP模型的话是4层。

2. HTTP是属于应用层的。

#### t2. HTTP常见状态码？更细的有了解嘛？

1. HTTP状态码是当浏览者访问一个网页时，浏览者的浏览器会向网页所在服务器发出请求。当浏览器接收并显示网页前，此网页所在的服务器会返回一个包含HTTP状态码的信息头（server header）用以响应浏览器的请求。常见的状态码有以下几种：

200 - 请求成功

301 - 资源（网页等）被永久转移到其它URL

404 - 请求的资源（网页等）不存在

500 - 内部服务器错误

2. HTTP状态码由三个十进制数字组成，第一个十进制数字定义了状态码的类型，后两个数字没有分类的作用。HTTP状态码共分为5种类型：

1**：信息，服务器收到请求，需要请求者继续执行操作

2**：成功，操作被成功接收并处理

3**：重定向，需要进一步的操作以完成请求

4**：客户端错误，请求包含语法错误或无法完成请求

5**：服务器错误，服务器在处理请求的过程中发生了错误

#### t3. HTTPS与HTTP有何区别？HTTPS加密的过程？

1. 区别：

1）HTTP 明文传输，数据都是未加密的，安全性较差，HTTPS（SSL+HTTP） 数据传输过程是加密的，安全性较好。

2）使用 HTTPS 协议需要到 CA（Certificate Authority，数字证书认证机构） 申请证书，一般免费证书较少，因而需要一定费用。证书颁发机构如：Symantec、Comodo、GoDaddy 和 GlobalSign 等。

3）HTTP 页面响应速度比 HTTPS 快，主要是因为 HTTP 使用 TCP 三次握手建立连接，客户端和服务器需要交换 3 个包，而 HTTPS除了 TCP 的三个包，还要加上 ssl 握手需要的 9 个包，所以一共是 12 个包。

4）http 和 https 使用的是完全不同的连接方式，用的端口也不一样，前者是 80，后者是 443。

5）HTTPS 其实就是建构在 SSL/TLS 之上的 HTTP 协议，所以，要比较 HTTPS 比 HTTP 要更耗费服务器资源。

2. HTTPS加密过程

**1）客户端发起 HTTPS 请求**

这个没什么好说的，就是用户在浏览器里输入一个 https 网址，然后连接到 server 的 443 端口。

**2）服务端的配置**

采用 HTTPS 协议的服务器必须要有一套数字证书，可以自己制作，也可以向组织申请，区别就是自己颁发的证书需要客户端验证通过，才可以继续访问，而使用受信任的公司申请的证书则不会弹出提示页面(startssl 就是个不错的选择，有 1 年的免费服务)。

这套证书其实就是一对公钥和私钥，如果对公钥和私钥不太理解，可以想象成一把钥匙和一个锁头，只是全世界只有你一个人有这把钥匙，你可以把锁头给别人，别人可以用这个锁把重要的东西锁起来，然后发给你，因为只有你一个人有这把钥匙，所以只有你才能看到被这把锁锁起来的东西。

**3）传送证书**

这个证书其实就是公钥，只是包含了很多信息，如证书的颁发机构，过期时间等等。

**4）客户端解析证书**

这部分工作是有客户端的TLS来完成的，首先会验证公钥是否有效，比如颁发机构，过期时间等等，如果发现异常，则会弹出一个警告框，提示证书存在问题。

如果证书没有问题，那么就生成一个随机值，然后用证书对该随机值进行加密，就好像上面说的，把随机值用锁头锁起来，这样除非有钥匙，不然看不到被锁住的内容。

**5）传送加密信息**

这部分传送的是用证书加密后的随机值，目的就是让服务端得到这个随机值，以后客户端和服务端的通信就可以通过这个随机值来进行加密解密了。

**6）服务端解密信息**

服务端用私钥解密后，得到了客户端传过来的随机值(私钥)，然后把内容通过该值进行对称加密，所谓对称加密就是，将信息和私钥通过某种算法混合在一起，这样除非知道私钥，不然无法获取内容，而正好客户端和服务端都知道这个私钥，所以只要加密算法够彪悍，私钥够复杂，数据就够安全。

**7）传输加密后的信息**

这部分信息是服务段用私钥加密后的信息，可以在客户端被还原。

**8）客户端解密信息**

客户端用之前生成的私钥解密服务段传过来的信息，于是获取了解密后的内容，整个过程第三方即使监听到了数据，也束手无策。

#### t4. SSL安全套阶层为什么运用了对称加密和非对称加密？如果非对称加密安全性更高，为什么还要用对称加密？

1. 实现信息保密和信息完整性，防止了某些用户通过使用IP数据包嗅探工具非法窃听。尽管数据包嗅探仍能捕捉到通信的内容，但却无法破译。

2. 因为非对称加密算法强度复杂、安全性依赖于算法与密钥。但对称加密主要为位运算，而非对称加密主要为幂运算，对称加密较快。

#### t5. HTTPS会被攻击嘛？

​ 会被攻击。中间人攻击就是一个例子。

## 主题四：算法题

### t1. K 个一组翻转链表

#### 思路：

这道题的实现思路大同小异，我们需要在反转一个分组的链表后，将前面分组的尾节点连接到当前分组反转后的头节点上，将当前分组反转后的尾节点连接到下一分组的头节点上。若直接使用[技术文1](https://mp.weixin.qq.com/s/39cUEJPRbW6gGo9V3DLE0w)中的反转全部链表的模板，要求我们每次先断开组与组间的连接，同时记录组头，具体实现详见[技术文2](https://mp.weixin.qq.com/s/37DG0dODk78C8ngZXs8iLg)。本次实现我们使用加强版反转链表函数，即可以指定头尾，同时返回新的头尾。这意味着我们需要记录head的上一个节点pre，以便反转后接回pre。在实现中，我们依旧需要使用新建头节点的技巧，以防特判，同时针对于不满足k个节点的链表，这种方式也可以避免特判。

#### 代码：

```c++

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

class Solution {

public:

// 反转子链表，返回新的头尾

pair reverse(ListNode* head,ListNode* tail){

ListNode* prev = NULL; // 头节点的上个节点为NULL

ListNode* p = head; // 临时当前节点

while(prev != tail){

ListNode* tmp = p->next; //记录下一个节点的指针

p->next = prev; // 指向下一个节点的指针反转指向前一个节点

prev = p; // 后移上一个节点

p = tmp; // 后移当前节点

}

return {tail,head};

}

ListNode* reverseKGroup(ListNode* head, int k) {

ListNode* hair = new ListNode(0); // 新建头节点

hair->next = head;

ListNode* pre = hair; //上一分组的尾指针

while (head) {

ListNode* tail = pre;

// 双指针法，判断剩余链表的长度是否大于等于k

for (int i = 0; i < k; ++i) {

tail = tail->next;

if (!tail) {

// 剩下的不需要反转

return hair->next;

}

}

ListNode* tmp = tail->next; //下一分组的头指针

pair result = reverse(head, tail);

head = result.first;

tail = result.second;

// 把子链表重新接回原链表

pre->next = head;

tail->next = tmp;

pre = tail;

head = tail->next;

}

return hair->next;

}

};

```

#### 复杂度分析：

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。