1 面试信息
面试形式:视频面试
面试时间:-03-05 16:00:00GMT+08:00
面试时长:约两小时
面试职位:客户端开发工程师-产品研发和工程架构部
2 考察内容
1.我们主要考察通用型的业务问题和过往的项目经历
2.价值观和软性技能也是我们选择人才的重要因素
3 面试问题
1.三次握手和四次握手的原理(为什么是四次?)
2.TCP和UDP的区别
3.TCP的可靠性依靠什么实现
4.滑动窗口的作用
5.磁盘调度算法(进程调度算法)
6.虚拟内存
7.内存溢出时如何判断是虚拟内存溢出还是物理内存溢出
面试官解答:可以查看数据结构的地址,如果存在空闲地址段,则是虚拟内存溢出,如果地址段满则是物理内存溢出。
8.LRU算法怎么实现
9.结合实际问题,定义缓冲池结构,使用HashMap如何尽可能高效地实现LRU算法进行页面淘汰(需要明白HashMap的基本原理)
面试官解答:利用队列先进先出的性质,淘汰时删除队首节点。同时,在定义HashMap的<key,value>键值对时,value直接存储节点。
4 机试问题
选择了中等难度(easy,mid,hard),问题如下:
一个数据结构中保存了若干航班飞机的起飞和降落时间,当在飞行中的飞机数量小于K时,处于安全状态,判断输入的数据结构中飞机的时间安排是否安全。
* 面试问题答案整理
1.答:
三次握手:
(1)客户端主动请求建立连接,发送SYN包(同步位SYN=1,序列号seq=x)到服务器端,并进入SYN-SENT状态,等待服务器确认;
(2)服务器端收到客户端发来的SYN包后必须对其进行确认,同时自己也发送SYN包请求连接,即发送ACK+SYN包(确认位ACK=1,同步位SYN=1,确认号ack=x+1,序列号seq=y)到客户端,此时服务器进入SYN-RECEIVED状态;
(3)客户端收到服务器端发来的ACK+SYN包后,向服务器发送确认包(确认位ACK=1,确认号ack=y+1,序列号seq=x+1),此包发送完毕,客户端和服务器端进入ESTABLISHED状态,三次握手完成。
四次挥手:
(1)客户端发送连接释放报文(终止位FIN=1,序列号seq=u)到服务器端,并进入FIN-WAIT-1状态;
(2)服务器端收到连接释放报文,发送确认报文(确认位ACK=1,确认号ack=u+1,序列号seq=v)给客户端,并进入CLOSE-WAIT状态。此时,客户端到服务器方向的传输释放,处于半关闭状态,但服务器端依旧可以向客户端发送数据。客户端收到服务器端的确认报文后,进入FIN-WAIT-2状态,等待服务器端发送连接释放报文;
(3)服务器端将最后的数据发送完毕后,向客户端发送连接释放报文(终止位FIN=1,确认位ACK=1,确认号ack=u+1,序列号seq=w),并进入LAST-ACK状态;
(4)客户端收到服务器端的连接释放报文后,发送确认报文(确认位ACK=1,确认号ack=w+1,序列号seq=u+1)给服务器端,并进入TIME-WAIT状态,在经过2MSL时间后,撤销TCB,进入CLOSED状态。
2.答:
3.答:TCP的可靠性依靠以下7种机制实现:
(1)校验和:检验范围包括TCP首部和数据部分,发送方将整个报文段以字(16位)为单位分开,并将所有段进行反码相加,结果存放在校验和字段中,接收方用同样的方法计算,若最终结果全为1则正确,否则存在错误。
(2)序列号:TCP对每个字节的数据都进行编号。序列号作用有:
a.保证数据不丢失
b.保证数据按序到达
c.提高效率,累计确认
d.去除重复数据
(3)确认应答机制(ACK):TCP首部有标志位ACK,当ACK=1时表示确认号有效。接收方对于按序到达的数据会进行确认,发送方如果收到已发送数据的确认报文,则继续传输下一部分数据,否则等待一段时间后启动重传机制。
(4)超时重传机制:当数据在发送后一定时间内未收到接收方的确认,发送方就会进行重传。报文段发出到收到应答中间有一个报文段的往返时间RTT,超时重传时间RTO会略大于RTT,TCP会根据网络情况动态计算RTT,因此RTO也是不断变化的,Liunx中RTO呈指数递增,重传一定次数后关闭连接。
(5)连接管理机制:即上面提到的三次握手和四次挥手。
(6)流量控制:根据接收端的处理能力,来决定发送端的发送速度。TCP报文段首部有一个16位的窗口大小字段,该字段大小随着传输情况而变化,如果缓冲区满,就将窗口置为0,发送方收到后就不在发送数据,但定期会发送一个窗口探测报文,使接收方把窗口大小告诉发送方。
(7)拥塞控制:为了防止过多数据注入网络中造成网络拥堵。主要有四种算法:慢开始、拥塞避免、快重传、快恢复。
a.慢开始和拥塞避免
发送方维护一个拥塞窗口cwnd,大小等于发送窗口,慢开始的思想是一开始发送方发送一个字节,在收到接收方的确认后,将拥塞窗口大小翻倍,直到拥塞窗口大小达到慢开始门限ssthresh,停止慢开始算法,采用拥塞避免算法,拥塞窗口由指数增长变为线性增长,当网络拥塞,发生超时重传时,慢开始门限变为当前拥塞窗口大小的一半,拥塞窗口大小置1,重新开始慢启动算法。
b.快重传和快恢复
当发送方收到3个连续的重复确认,可能不是拥塞而是报文丢失,发送方执行快重传算法,对相应报文立即重传而不是等待超时重传,同时执行快恢复算法,发送方将慢开始门限和拥塞窗口调整为当前拥塞窗口大小的一半,然后执行拥塞避免算法。
4.答:滑动窗口分为三类:停止等待、后退N帧、选择重传。滑动窗口保证了传输可靠,提高了传输效率和稳定性。
5.答:
磁盘调度算法:
(1)先来先服务算法(FCFS)
(2)最短寻道时间优先算法(SSTF)
(3)扫描算法(SCAN)电梯算法
(4)循环扫描算法(CSAN)
进程调度算法:
(1)先来先服务算法(FCFS)
(2)短作业优先调度算法(SJF)
(3)优先权调度算法(分非抢占和抢占式)
(4)高相应比优先调度算法
(5)时间片轮转法
(6)多级反馈队列调度算法
6.答:存放在磁盘上的文件,会以固定大小的页进行划分,在使用CPU处理磁盘文件时,只加载需要使用的数据,当需要的数据不在内存时,发出缺页信号,再从外存中把相应的页调入内存。
7.如上
8.答:LRU(最近最少使用)算法是一种页面置换算法。其实现可以使用HashMap结合双向链表的方法,把k值相同的节点用双向链表连接起来,当新节点加入时,放入表头,当节点被访问时,把该节点移动到表头,当需要选择删除节点时,直接删除表尾节点即可。
9.如上
如果觉得《【校招】面试_字节跳动_客户端开发工程师_一面》对你有帮助,请点赞、收藏,并留下你的观点哦!