美团后台开发一面二面总结帖(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
- 说一下CPU中是如何管理缓存的
- LRU、LFU的实现
- 讲一下零拷贝。
继续深聊项目。
许愿HR面!
#美团点评实习##美团##面经##C++工程师#