快手游戏服务端C++开发一面-面经总结

1、tcp的重传机制有哪几种？具体描述一下

最基本的超时重传 超过时间就会重传
三个重复ACK 快速重传 减少等待超时、
接收方可以发送选择性确认 不用重传整段
乱序到达可以通知哪些丢失 重复数据重传

2、override和final？

override可写可不写
写出来就是显式声明虚函数重写基类了更加清晰

void doSomething(int x) override {  // 使用 override 关键字// 派生类中的实现}

final是最后一代的意思没办法继续继承了无法被重写了的意思

3、epoll的边缘触发和水平触发？

水平是默认的-这个没有疑问，只要fd有没有处理的事件，就不断通知应用程序。

假设一个套接字上有数据可读，水平触发模式下，只要该套接字上还有数据可读，每次调用 epoll_wait 都会返回该事件，直到数据被完全读取。逐步处理数据的场景。

边缘触发:高效爱的，减少系统调用次数，仅仅状态变化才通知一次。
从无到有才能通知一次。适用于事件发生立即处理大量的数据。减少重复通知。必须干完才能给你新派活。

4、tcp的滑动窗口？

滑动窗口为了流量控制
发送方和接收方之间动态调整发送和接受速度防止网络拥塞和丢包
先商定初始窗口大小----不超过窗口范围发送数据包-----ack返回能接受的大小----滑动到新的窗口发送新的数据。

5、stl的常用容器及其底层实现数据结构？

vector：动态数组增长是两倍增长
deque：双端队列（链表）
list：双向链表
queue：一般用deque 也可以list
set：红黑树自平衡二叉查找树 set不重复
map：红黑树键值对
unordered_set 和 unordered_multiset：哈希表无序平均o1 最坏o1

6、static的用法和作用？

函数内静态变量：只初始化一次它在函数调用结束后依然存在，并在下次调用时保留上次的值。

void counter() {static int count = 0;  // 只初始化一次count++;std::cout << "Count: " << count << std::endl;
}int main() {counter();  // 输出: Count: 1counter();  // 输出: Count: 2counter();  // 输出: Count: 3return 0;
}

上面的例子可以看出来每次调用counter函数都不会把他置为0 而是保持上一次不变了才能加

全局静态变量-全局静态函数：作用域限制在自己的文件不能被其他文件访问防止冲突（命名）

类中的静态变量静态成员函数：这就是归为类而不是某个实例的属性了不实例化 Example 类的情况下直接通过类名调用。

7、智能指针？

这个不写了感觉是必考

8、虚函数、虚表指针？

有虚函数就有虚表
虚表里面是虚函数地址
虚表指针指向虚表
通过虚表指针找到虚表找到对应的函数指针再调用函数

每个 Base 对象有一个 vptr，指向 Base_vtable；
每个 Derived 对象有一个 vptr，指向 Derived_vtable。
调用虚函数时，通过对象的 vptr 指针确定实际调用的函数。

class Base {
public:virtual void func1() { /* ... */ }virtual void func2() { /* ... */ }
};class Derived : public Base {
public:void func1() override { /* ... */ } // 重写基类的 func1void func3() { /* ... */ } // 派生类独有的函数
};对于 Base 类，它的虚表可能看起来像这样：Base_vtable:
+---------------------+
| Base::func1 address |
+---------------------+
| Base::func2 address |
+---------------------+而对于 Derived 类，它的虚表可能看起来像这样：Derived_vtable:
+---------------------+
| Derived::func1 address | // 重写后的函数地址
+-----------------------+
| Base::func2 address    | // 没有重写，指向基类的函数地址
+-----------------------+

9、内存碎片？

不能有效利用的零散空间影响系统性能和使用效率
有两种：外部碎片内部碎片

外部碎片指的是由于内存块的分配和释放操作导致可用的空闲内存被分割成许多小块，这些小块分布在整个内存空间中，而每个小块都不足以满足新的内存分配请求。即便系统总的空闲内存足够，但因为它们不连续，导致无法分配给需要较大连续空间的请求。

内部碎片指的是分配的内存块内部未被使用的部分。由于内存分配器一般会按照一定的对齐要求（如8字节或16字节对齐）来分配内存，所以分配的内存块可能会比实际需要的稍大，导致一部分内存未被使用。

10、索引的优缺点？

优点：加速检索提高效率可以条件查询
缺点：增加空间降低写入性能还要维护有可能失效

11、索引可以用哪些数据结构实现？

B树多路搜索自平衡搜索树
B+树变种叶子节点怎么怎么样
哈希表
跳表（多层链表查找变成logn）
前缀树trie 就是用于前缀匹配

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == nullptr || root == p || root == q) return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);if(left == nullptr) return right;if(right == nullptr) return left;return root;}
};