星辉游戏 C++ 服务端工程师一面面经
《面试题目》
- 自我介绍（侧重Java经验及算竞经历）
- C++八股：
- vector如何实现扩容？
- map的底层原理是什么？
- Redis：
- Redis的基本数据结构有哪些？
- 算法题：
- 给定n个数，求这些数的最小公倍数（建议思路：两两处理，利用公式：a*b / gcd(a,b)）。
- 场景题：面试官给出一道场景设计题。
《参考解析》
-
vector扩容机制： 当插入元素超过当前容量时，vector会申请一块更大的内存（通常是旧容量的1.5倍或2倍），将原内存数据拷贝到新内存，销毁旧内存并释放资源。该操作复杂度为O(N)，频繁扩容会产生性能开销，建议使用reserve提前预分配。
-
map底层原理： C++中的std::map通常由红黑树（平衡二叉搜索树）实现，保证了插入、删除、查找操作的时间复杂度均为O(logN)，且保持键值对的有序性。
-
Redis基本数据结构： 包括String（字符串）、List（双向链表）、Hash（哈希表）、Set（无序集合）、Sorted Set（跳表+哈希表）。常用于缓存、计数器、排行榜及分布式锁等场景。
-
最小公倍数算法： 利用公式：lcm(a, b) = (a * b) / gcd(a, b)，其中gcd为最大公约数（可使用辗转相除法实现）。对于n个数，可采用累积计算：lcm(x1, x2, …, xn) = lcm(lcm(x1, x2), x3)…。