4.11美团笔试

C++：1.什么是多态？如何实现多态 （同一接口不同行为，静态（重载，通过重载，模板等），动态（重写，通过类维护虚表，对象持有虚指针指向虚表）2.C++智能指针（unique_ptr,shared_ptr,weak_ptr，讲讲特性）3.为什么需要虚析构函数(基类指针指向派生类对象的时候，析构时能正确调用派生类的构造函数)4.map,set,multi_map,multi_set的底层实现（均为红黑树，set只存值，map存键值对，自动按照键/值排序，muti允许键重复） 计算机网络（网络编程）TCP三次握手流程，对应的socketAPI（// 服务端int listen_fd = socke...

T1 大分讨,不过没太讨论清楚T2 不会ML，oh noT3 先容斥变成求解长为m,取值[1,v] 总和为k的数组，考虑用如下的生成函数描述总和为k的个数：[x^k] (\frac{x *(1-x^v)}{1- x})^m= [x^{k - m}] (1-x^v)^m  \cdot  (1-x)^{-m}前者二项式系数展开，后者牛顿二项式系数展开，枚举前一项x的系数为x^{iv}, 可得：ans = \sum_{i = 0, r = k - m - iv}^{iv \leq k - m} (-1)^i C(m, i) C(m + r - 1,r)最后ans <-   v^n - ans 即可, 注意n根据费马小定理要对P - 1取模，或者直接传i64复杂度O(\sum m + log P)T4, 一个基环树，考虑将答案拆为3部分：1. 链， 2. 若干次整个环， 3 部分环我们先通过dfs求得基环树的环和链，用倍增维护链上的父节点和其他信息，复杂度O(nlogn)1.如果k > 链长，直接跳到根节点，进入2部分否则，倍增上跳的过程中求和即可，O(log n)2/3 若环长为len，还剩k步，则我们走x = k / len个整环，y = k % len 一部分长的环于是贡献就是 x(x+1)/2 * all(circle) + (x + 1) * getcir(p, p + y - 1), 求解这部分是O(1)的总复杂度是O(nlogn + qlogn)可惜T4 赛后才调完

一面，有点偏综合面吧。首先自我介绍。问项目，介绍一下项目，项目几个人参与了，你负责什么模块。项目中有没有遇到过很紧急的状况？怎么解决的？主要的编程语言。八股进程和线程的区别以及通信方式，进程和线程如何解决并发。网络通讯当中，了解哪些通讯方式。知道哪些调试的方法？平时用哪些？运行期有没有遇到过问题，怎么定位问题的原因和位置？（这方面问的比较细，我答得一般般，说的不太好）有没有遇到过内存泄漏的问题，有什么定位的方法。（这里答得也不太好，说只会看代码，工具不会用）了解的锁。问一些场景题。项目开发的过程中，有没有遇到过问题，怎么解决的？对自己未来的规划？反问。感觉不是一般的技术面，更多的是一些处理问题...