字节跳动客户端三面面经（带答案噢！！！）

后台回复进群加入刷题群~点击下方卡片可搜索关键词~

### 主题一：C++

#### t1.vector的扩容机制？

1) vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；

2) 对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了；

3) 初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1；

4) 不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

#### t2. 虚函数的定义及用法？

虚函数虚就虚在所谓“推迟联编”或者“动态联编”上，一个类函数的调用并不是在编译时刻被确定的，而是在运行时刻被确定的。由于编写代码的时候并不能确定被调用的是基类的函数还是哪个派生类的函数，所以被成为“虚”函数。

```c++

class A

{

public:

virtual void foo()

{

cout<<"A::foo() is called"<

}

};

class B:public A

{

public:

void foo()

{

cout<<"B::foo() is called"<

}

};

int main(void)

{

A *a = new B();

a->foo(); // 在这里，a虽然是指向A的指针，但是被调用的函数(foo)却是B的!

return 0;

}

```

#### t3. 构造函数和析构函数一般都定义为虚函数嘛？

构造函数不能为虚函数，而析构函数可以且常常是虚函数。

### 主题二：操作系统

#### t1.说一下虚拟内存？

在程序执行过程中，当所访问的信息不在内存时，由操作系统将**所需要的部分**调入内存,然后继续执行程序。另一方面，操作系统将内存中**暂时不使用的内容**换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

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

#### t1.MSL、TTL和RTT的区别

- MSL 是Maximum Segment Lifetime英文的缩写，是“报文最大生存时间”，他是任何报文在网络上存在的**最长时间**，超过这个时间报文将被丢弃。

- ip头中有一个TTL域，TTL是 time to live的缩写，中文可以译为“生存时间”，这个生存时间是由源主机设置初始值但不是存的具体时间，而是存储了一个ip数据报可以经过的**最大路由数**，每经过一个处理他的路由器此值就减1，当此值为0则数据报将被丢弃，同时发送ICMP报文通知源主机。

- RTT是客户到服务器**往返**所花时间（round-trip time，简称RTT），表示从发送端发送数据开始，到发送端收到来自接收端的确认（接收端收到数据后便立即发送确认），总共经历的时延。TCP含有动态估算RTT的算法。TCP还持续估算一个给定连接的RTT，这是因为RTT受网络传输拥塞程序的变化而变化。

#### t2.TCP四次挥手中客户端的最后一次挥手为什么要等待两个MSL？

等待两个MSL时间主要目的是怕最后一个 ACK包服务器没收到，那么服务器在超时后将重发第三次握手的FIN包，客户端接到重发的FIN包后可以再发一个ACK应答包。

#### t3.套接字（Socket）的具体用法？

Socket是应用层与TCP/IP协议族通信的中间软件抽象层，它是一组**接口**。在设计模式中，Socket其实就是一个门面模式，它把复杂的TCP/IP协议族隐藏在Socket接口后面，对用户来说，一组简单的接口就是全部，让Socket去组织数据，以符合指定的协议。

Socket实现服务器端和客户端通信：

| 客户端 | 服务器 |

| --------------------------------- | ------------------------------------------------ |

| ① 创建套接字 | ① 创建用于监听的套接字（socket） |

| ② 向服务器发送连接请求（connect） | ② 将套接字绑定到本地地址和端口上（bind） |

| ③ 通信（send/recv) | ③ 将套接字设为监听模式（listen） |

| ④ 关闭套接字 | ④ 等待客户请求（accept），此处要不断的调用accept |

| | ⑤ 通信（send/receive），完成后返回4 |

| | ⑥ 关闭套接字（closesocket） |

### 主题四：算法题

#### t1. 给定两个链表，找到其相交节点

#### 思路：

首先我们会想到遍历其中一个链表，并使用额外空间记录所有已经走过的节点，然后遍历另一个链表遇到的第一个被记录过的节点即为所求。但是这样不符合空间复杂度的要求，我们还是要从相交链表本身的性质进行解题。我们最大的困难就是不知道相交节点前两个链表各有多少个节点，因为若相交节点前有同样多的节点，我们就可以通过两个链表一起遍历来找到相交节点了。那么，为了分别从前方相同数量的节点出发，我们可以先遍历获得两个链表的长度，然后用一个指针从较长的链表先走两者长度差值个节点，同时用另一个指向短链表的指针与该指针一起向前遍历，直到相同节点。进一步地，这道题还有更好的解法，即两个指针分别从两个链表头节点出发，若中途相遇则为相交节点，若未相遇，则遍历完成后分别从另一个链表头节点继续出发，此时若有相交节点则一定会相遇。这种解法，也是用到了遍历x+public+y和遍历y+public+x的长度一定是相同的这种思想。

#### 代码：

```c++

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

ListNode *tmp1 = headA;

ListNode *tmp2 = headB;

while(tmp1 != tmp2) {

if(!tmp1) {

tmp1 = headB;

} else {

tmp1 = tmp1->next;

}

if(!tmp2) {

tmp2 = headA;

} else {

tmp2 = tmp2->next;

}

}

return tmp1;

}

```

#### 复杂度分析：

时间复杂度：$O(A+B)$ ，遍历了两个链表。

空间复杂度：$O(1)$ ，没有使用额外空间。

#### t2.两个玩家先后手掷硬币，先投出正面的获胜，问先手获胜概率

#### 思路：

假设 $A$ 为先手，$B$ 为后手，$A$ 第一轮投出正面获胜的概率为 $1/2$ ；第一轮未投出正面、且 $B$ 也未投出正面，第二轮投出正面获胜的概率为 $1/8$，以此类推，故 $A$ 获胜概率为 $1/2 + 1/8 + 1/32 + ... = 2/3$

另一种思路，假设先手获胜概率为 $x$ ，则第一轮 $A$ 投出正面获胜概率为 $1/2$，若投出反面，则 $B$ 成为先手，获胜概率也为 $x$ 。由于 $A,B$ 获胜概率之和为 $1$，故有 $x + 1/2x = 1$，解得 $x = 2/3$

---

关注**GTAlgorithm**，专注周赛、面经题解分享，陪大家一起攻克算法难关~

[字节跳动客户端二面面经（附答案）](https://mp.weixin.qq.com/s?__biz=Mzg3NzMzNzU1MA==&mid=2247486827&idx=1&sn=1f4c04a29baa73fbdd5d9999818e6203&chksm=cf25c3caf8524adc72c071ce7bfdecc699056c37566b904387d91cee1177071c0fedec5937c3#rd)

[层序遍历？套模板就够了](https://mp.weixin.qq.com/s?__biz=Mzg3NzMzNzU1MA==&mid=2247486641&idx=1&sn=a8d67161fd808c98a53ea532f0dc74c6&chksm=cf25c210f8524b06d9abc40a2314d81cf114e027caeb0a7a5182f0ffc9b997fa144512cb7316&token=1954703230&lang=zh_CN#rd)

后台回复“20210107”获取PDF版二面面经~~~