小米一面

一份来自小米的面试题

• 查看淘宝的购物车，转到登陆页面的过程

  在访问淘宝的购物车时，查看请求头中携带的cookie或token，如果没有携带，则没有权限，返回401（Unauthorized）。然后跳转到登陆页面，然后输入账号密码，再次发起请求的时候就会携带在cookie中，后端收到cookie中的数据，在数据库中查找，存在时登陆成功。

• 后端发送过来数据，前端接受但数据无法渲染的过程

  这不知道。。

• TCP和UDP

  TCP是面向连接的可靠传输，UDP是面向不连接的不可靠传输。TCP安全稳定，用于文件传输、网络通信等；UDP实时性高，用于直播、游戏等。

• 三次握手和四次挥手

  A为客户端，B为服务端。

  三次握手：1、A发送SYN到B，2、B收到SYN+ACK确认，3、A收到以后发送ACK。

  四次挥手：1、A发送FIN到B，2、B收到FIN后，向A发送ACK，防止A重传FIN，3、B向A发送FIN，4、A收到FIN后，向B发送ACK释放连接。

• 为什么要等待2MSL时间

  MSL是从客户端到服务端所需要的时间，2MSL为一来回的时间，也就是报文在网络中的存活时间。如果A发出报文后，超过2MSLB没有收到，报文就会被丢弃，B不能正常关闭。在2MSL时间内，如果A没有收到B的重复请求就会在进入关闭状态。

• 快排的时间复杂度，思路，数据交换的过程

  快速排序是选取一个数，将所有比它小的数放在左边，将所有比它大的数放在右边，然后再对左右两侧再分别进行相同的操作。

• 链表倒数第k个节点

  快慢指针，时间复杂度O(n)，快指针先走n步，然后快慢指针一起走，当快指针走完时，慢指针指向倒数第k个节点。

  也可以将链表中的元素去全都提取到一个数组中，然后访问倒数第k个元素。需要额外的空间。

• 从上到下，从左到右输出一个二叉树

  二叉树的层次遍历，维护一个队列，弹出一个元素的同时插入它的左右子节点。在插入的时候记录。