虾皮shopee新加坡提前批后端开发一二面面经

一面 73min

面试官介绍面试考什么（算法题+问答题，应届所以偏向课本知识）和自己的情况（负责的业务），准备好纸、笔、水杯。
自我介绍
acm参加了两届，那写算法题对你应该没多大问题吧？经常听到这个话，每次一听到就很紧张，预感要翻车。
算法题一：给定n（奇数），输出所有n个结点的满二叉树（每个结点要么两个儿子，要么没儿子）。为了验证每个树的正确性，输出每个树的前序遍历序列来验证（普通结点输出0，遍历到NULL结点输出-1并返回）。

这题难度一般但不太常规，一开始想着递归，从上到下，但是一直觉得递归下去的话下层结点会复用到上层结点，最后无法输出所有的根节点，一直犹豫怀疑着边写边乱想。这个面试官算法水平不错，思路清晰，慢慢引导把我提示到左右集合两两组合了，然后就会做了，好评。一共用了40分钟。

核心代码如下：其实是可以记忆化复用结点的。
```
struct Node {
    int val;
    Node *l, *r;
    Node():val(0),l(NULL),r(NULL){}
    Node(Node *L,Node *R):val(0),l(L),r(R){}
};

vector<Node *> build(int n)
{
    vector<Node *> ans;
    if(n==1)
    {
        ans.push_back(new Node());
        return ans;
    }
    for(int i=1;i<n;i+=2)
    {
        vector<Node *> l_list=build(i);
        vector<Node *> r_list=build(n-i-1);
        for(Node *l:l_list)
            for(Node *r:r_list)
                ans.push_back(new Node(l,r));
    }
    return ans;
}
```
后面查到原来是力扣894，mid难度。
有序链表删除所有重复出现的节点 leetcode82 写了10分钟。
项目：rpc框架简易轮子，注册中心实现，太过简单，传递信息直接http，存储没有持久化，没什么可问的。
设计隔离级别解决的问题？通常应用的隔离级别？mvcc原理？
实习经历中的分布式锁实现方式？
反问：这次校招提前批不分部门，最后如果通过，根据什么选部门？
闲聊：国内其他公司提前批

二面 50min

面试官介绍团队业务。
今天不写代码，聊聊计算机科学的一些基础还有系统设计。
假设我们现在有一个机房，很多台服务器，每台服务器上安装两个程序，其中一个程序是基于tcp的，另一个是基于udp的，让这两个程序去处理大量的任务，就需要传输大量的数据，随着传输量越来越大，网络的带宽逐渐达到极限，就会产生丢包、拥塞，假设你来到这个房间，以上帝视角，就是可以看到一切事物，你拿起一根网线，在你的视角中，tcp和udp流量你是可以区分开的，tcp流量是红色，udp是蓝色，那么你能看到更多的红色还是蓝色？

说的更详细一点，如果tcp应用单独运行在网络，会占用90%的带宽，如果是单独运行udp，也是占用90%带宽，现在一起使用，只有100%的带宽，那我们会看到更多的tcp流量还是udp流量？

那么拥堵的情况下，100%的带宽多大比例会被tcp所占用，多大比例会被udp所占用？
tcp流量控制
tcp拥塞控制
流量控制和拥塞控制区别
拥塞窗口具体会怎么根据网络质量调整
https解决了哪些问题？
具体怎么加密的？
随机数怎么生成最后加密的密钥
DH算法解决什么问题？为什么不直接用公钥加密发过去？这两种方法哪种更安全？
怎么验证证书？证书链？数字签名怎么产生、怎么验证？
https数据篡改怎么被检测出来？
认证用户是通过账号和密码，在数据库里为了用户密码安全不被用户本人以外的任何人知道，怎么存储用户密码？加密算法举例？salt做什么用的？
假设现在账号系统建好了，假设我们现在要做一个钱包，有维护余额、充值、支付功能，支付时需要短信验证码，怎么设计实现短信验证码模块？

为什么要回调？还有其他方案吗？

支付服务拿到验证码放到哪？内存。放在内存会有什么问题吗？感觉没什么问题。如果支付服务有多台服务器呢，数据存在一台请求了另一台？

key和value是什么？

需要过期时间吗？
假设现在发短信的模块按刚刚的设计也做好了，可能团队里其他业务也需要发短信，这是一个共享的服务，服务器能支撑的流量是有上限的，这时需要按重要程度给每个服务分配额度，比如每秒钟发多少次短信。这时需要实现限流的能力，限流的能力你要怎么实现？

大概逻辑听懂了，具体怎么实现？数据结构，怎么实现？

这种实现能够保证每秒钟请求数不会超过一定值吗？

那假如我们想保证任意一个1s的时间窗口都不会超过，怎么实现？

现在我们说的都是单机层面的实现，如果有多台服务器呢？

具体怎么实现，锁什么？

你觉得呢？

那坏了怎么办？
OK 那我们回头再看这个实现哈。我们电商的场景有可能有整点时刻，流量尖峰，如果用刚刚的限流，很多都会超出限制，但实际上我们的服务器处理能力是允许的，这一秒不行，过几秒就可以了可以消化掉。那这种限流要怎么做？
反问：团队。