美团后台开发一面二面总结帖（C++）

对方是分布式存储相关的部门。

一面：

算法题
食堂排队打饭问题：
有n个不同的窗口，每个窗口打饭的时间不一样，现在有m个人去打饭，如果安排打饭次序，确保所有人的打饭时间最短，求所有人打完饭的最短时间。

贪心算法，我当时用的一个优先级队列，每次选择等待时间最短的队列，具体代码忘记保留了。

CS问题：

TCP/IP三次握手和四次挥手
讲一下IO多路复用
select、poll、epoll的区别
数据库事务隔离机制
B-树和B+树的区别
grep命令
可以实现一个线程池吗？

剩下时间都是在聊项目，主要聊了最近的一个实习和实验室的项目。

二面：

算法题
给定字符串，求最长不重复子串。

#include <iostream>
#include <string>

using namespace std;

string findMax(string str) {
    if (str.size() <= 1) return str;
    int start = 0, end = 0;
    int maxLen = 1, maxStart = 0;

    for (int i = 1; i < str.size(); i++) {
        for (int j = start; j <= end; j++) {
            if (str[i] == str[j]) {
                start = j+1;
                break;
            }
        }
        end = i;
        if (maxLen < (end - start + 1)) {
            maxLen = (end - start + 1);
            maxStart = start;
        }
    }

    return str.substr(maxStart, maxLen);
}
int main() {
    string str = "zxcvbsdfghjfghbnm";
    cout << findMax(str) << endl;

    return 0;
}

使用unordered_set优化之后的代码：

#include <iostream>
#include <unordered_set>

using namespace std;

string findMax(string str) {
    if(str.size() <= 1) return 0;
        unordered_set<char> lookup;
        int maxLen = 0, start = 0;
        int left = 0;
        for(int i = 0; i < str.size(); i++){
            while (lookup.find(str[i]) != lookup.end()){
                lookup.erase(str[left]);
                left ++;
            }
            int len = (i - left + 1);
            if (maxLen < len) {
                maxLen = len;
                start = left;
            }

            lookup.insert(str[i]);
    }
    return str.substr(start, maxLen);
}

int main()
{
    string str = "zxcvbsdfghjfghbnm";
    cout << findMax(str) << endl;

    return 0;
}

CS问题：

1.解释DNS域名解析的过程：
网络客户端就是我们平常使用的电脑，打开浏览器，输入一个域名。比如输入www.baidu.com，这时，你使用的电脑会发出一个DNS请求到本地DNS服务器。本地DNS服务器一般都是你的网络接入服务器商提供，比如中国电信，中国移动。
查询www.baidu.com的DNS请求到达本地DNS服务器之后，本地DNS服务器会首先查询它的缓存记录，如果缓存中有此条记录，就可以直接返回结果。如果没有，本地DNS服务器还要向DNS根服务器进行查询。
根DNS服务器没有记录具体的域名和IP地址的对应关系，而是告诉本地DNS服务器，你可以到域服务器上去继续查询，并给出域服务器的地址。
本地DNS服务器继续向域服务器发出请求，在这个例子中，请求的对象是.com域服务器。.com域服务器收到请求之后，也不会直接返回域名和IP地址的对应关系，而是告诉本地DNS服务器，你的域名的解析服务器的地址。
最后，本地DNS服务器向域名的解析服务器发出请求，这时就能收到一个域名和IP地址对应关系，本地DNS服务器不仅要把IP地址返回给用户电脑，还要把这个对应关系保存在缓存中，以备下次别的用户查询时，可以直接返回结果，加快网络访问。
2.路由器查询目标主机的过程
https://www.jianshu.com/p/bc2e44417a7f

美团后台开发一面二面总结帖（C++）

全站热榜