拼多多服务端开发实习一面

2024-06-05

自我介绍

毕业院校、项目经历、实习工作经历,简单介绍掌握的技能。

算法题

将多个有序链表合并为一个有序链表;

询问了经典的排序算法;

改进:要求运行时间复杂度 $O(n\cdot log n)$,使用堆排序;

问答环节

什么是死锁?如何避免死锁?

死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进。

死锁的形成主要有两个原因:

  1. 系统资源不足;
  2. 进程推进顺序不当。

死锁产生的四个必要条件:

  1. 互斥条件:一个资源每次只能被一个进程使用,即在某一个时间段内仅为一个进程所占用。此时有其他进程请求该资源,则请求进程只能等待。
  2. 请求保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源 已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
  3. 资源不可剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放(只能是主动释放)。
  4. 循环等待:若干进程间形成首尾相接循环等待资源的关系。

死锁避免的基本思想:只要发生死锁,以上条件必然成立,若有一个条件不成立,则不会发生死锁。系统对进程发出每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,如果分配后系统可能发生死锁,则不予分配,否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

死锁预防:破坏死锁产生的四个必要条件之一,严格地防止死锁的出现。

死锁避免与死锁预防的区别:死锁预防严格限制产生死锁的必要条件,而死锁避免不那么严格,因为即使死锁的必要条件存在,也不一定发生死锁。

TCP和UDP的区别

TCP与UDP的基本区别,:

  1. 基于有连接和无连接;
  2. 系统占用资源多少;
  3. UDP程序结构较为简单;
  4. 字节流模式(TCP)与数据报模式(UDP);
  5. TCP保证数据正确性,UDP可能丢包;
  6. TCP保证数据顺序,UDP不保证。

UDP应用场景:实时场景,RIP路由表更新,DNS、SNMP等都是运行在UDP之上。

  1. 面向数据报方式;
  2. 网络数据大多为短消息;
  3. 拥有大量client;
  4. 对数据安全性没有特殊要求;
  5. 网络负担重,但是对响应速度要求高。

总体来说,TCP与UDP的区别如下:

  1. TCP面向连接(如打电话要先拨号建立连接);UDP是无连接的,即发送数据之前不需要建立连接。
  2. TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付。
  3. TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的。UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)。
  4. 每一条TCP连接只能是点到点的;UDP支持一对一,一对多,多对一和多对多的交互通信。
  5. TCP首部开销20字节;UDP的首部开销小,只有8个字节。
  6. TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道。

ps: UDP一般不说全双工、半双工,因为这些说法都是指面向连接才有的说法,而对于UDP这种不建立连接的传输协议,没有明确的全双工、半双工的说法。

TCP拥塞控制

TCP的四种拥塞控制算法:

  1. 慢启动

    发送端在最初建立连接后,拥塞窗口值为1,接收方收到该报文后,将拥塞窗口的值变为2,每个传输轮次依次增加(指数方式增加),直至发生拥塞。

  2. 拥塞避免

    每个传输轮次线性增加拥塞窗口值。

  3. 快重传

    接收方收到未按需到达的报文段后,要求发送方重传之前的报文段,而不是等超时重传计数器超时再重传。

  4. 快恢复

    发送方知道丢失了个别字段的报文段后,不启慢启动算法,执行快恢复算法,将拥塞窗口值修改为当前窗口的一般,开始执行拥塞避免算法。

常用的开发语言?有没有用过Java?

反问