C++数据结构篇
大厂高压面经实录，结合腾讯、阿里、字节等真实技术面试场景，包含压迫式追问、核心陷阱和代码实战，助你彻底碾压面试官：
⚡️ 一、Top K问题：堆 vs 快速选择（字节跳动3面原题）
面试官（打断式追问）：“10亿整数找Top 100，内存限制1GB，5分钟内手撕代码，禁用第三方库！”
大厂级应答：
最小堆解法（海量数据唯一正解）
#include <queue>
#include <vector>
std::vector<int> topK(std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // 最小堆
for (int num : nums) {
if (min_heap.size() < k) {
min_heap.push(num);
} else if (num > min_heap.top()) {
min_heap.pop();
min_heap.push(num); // 淘汰堆顶，加入新元素
}
}
// 转存结果（注意：堆中是无序的）
std::vector<int> res;
while (!min_heap.empty()) {
res.push_back(min_heap.top());
min_heap.pop();
}
return res;
}性能关键点：
- 时间复杂度：
O(n log k) - 空间复杂度：
O(k)（仅需常驻100个元素） - 陷阱：若用最大堆全排序 → 内存爆炸
O(n)
2.快速选择（面试加分项）
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; ++j) {
if (nums[j] >= pivot) std::swap(nums[i++], nums[j]); // 注意：降序排列
}
std::swap(nums[i], nums[right]);
return i;
}
void quickSelect(std::vector<int>& nums, int left, int right, int k) {
if (left >= right) return;
int pos = partition(nums, left, right);
if (pos == k) return;
else if (pos < k) quickSelect(nums, pos + 1, right, k);
else quickSelect(nums, left, pos - 1, k);
}致命细节：
- 平均
O(n)，但需处理最坏情况（如全有序时退化为O(n²)） → 必须随机化基准值
std::swap(nums[right], nums[left + rand() % (right - left + 1)]); // 随机选择基准🌳 二、二叉树序列化与反序列化（腾讯T9手撕代码）
面试官（甩白板）：“支持带空指针的任意结构，写代码实现二叉树↔字符串双向转换！”
避坑实现：
// 序列化（前序遍历）
std::string serialize(TreeNode* root) {
if (!root) return "#,";
return std::to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
}
// 反序列化
TreeNode* deserialize(std::string data) {
std::istringstream ss(data);
return buildTree(ss);
}
TreeNode* buildTree(std::istringstream& ss) {
std::string token;
std::getline(ss, token, ',');
if (token == "#") return nullptr;
TreeNode* root = new TreeNode(std::stoi(token));
root->left = buildTree(ss);
root->right = buildTree(ss);
return root;
}字节跳动死亡追问：
- 为什么不用中序？ → 中序无法确定根位置，序列化结果歧义（反例：
1,#,2可对应多种结构） - 空间如何优化？ → 用层序遍历替代前序（避免递归栈溢出）
- 内存泄漏风险 → 面试中需主动补充析构函数！
📦 三、LRU缓存设计（阿里P8限时手撕）
面试官：“5分钟实现O(1)的get/put，写错一行代码直接挂！”
工业级答案：
#include <unordered_map>
#include <list>
class LRUCache {
private:
struct Node { int key, val; };
std::list<Node> cache; // 双向链表：存储节点
std::unordered_map<int, std::list<Node>::iterator> map; // 哈希表：key->链表迭代器
int capacity;
public:
LRUCache(int cap) : capacity(cap) {}
int get(int key) {
if (!map.count(key)) return -1;
auto it = map[key];
cache.splice(cache.end(), cache, it); // 关键：移动节点到链表尾部（表示最近使用）
return it->val;
}
void put(int key, int value) {
if (map.count(key)) {
auto it = map[key];
it->val = value; // 更新值
cache.splice(cache.end(), cache, it);
return;
}
if (cache.size() == capacity) { // 淘汰队头
map.erase(cache.front().key);
cache.pop_front();
}
cache.push_back({key, value});
map[key] = std::prev(cache.end());
}
};腾讯终面拷问：
- 为什么必须用双向链表？ → 单链表无法O(1)删除中间节点（需遍历找前驱）
- 线程安全如何实现？ → 答：用读写锁（
std::shared_mutex）保护链表和哈希表
🔍 四、图论：拓扑排序检测环（华为自动驾驶团队真题）
面试官：“百万节点任务依赖图，实时判断是否成环，系统要求高并发低延迟！”
分布式级方案：
#include <vector>
#include <queue>
bool hasCycle(int n, std::vector<std::vector<int>>& graph) {
std::vector<int> indegree(n, 0);
std::queue<int> q;
// 计算入度
for (int i = 0; i < n; ++i)
for (int neighbor : graph[i])
indegree[neighbor]++;
// 入度0节点入队
for (int i = 0; i < n; ++i)
if (indegree[i] == 0) q.push(i);
int count = 0;
while (!q.empty()) {
int node = q.front(); q.pop();
count++;
for (int neighbor : graph[node]) {
if (--indegree[neighbor] == 0)
q.push(neighbor);
}
}
return count != n; // 存在环时count < n
}字节跳动加问：
- 如何并行化？ → 分片计算入度（如按节点ID哈希分片），合并结果（
atomic同步） - DFS染色法缺点 → 递归深度大时栈溢出，且无法增量更新
⚙️ 五、哈希表：高并发优化（美团中间件团队终面）
面试官：“线上服务哈希表扩容卡顿10秒，引发雪崩！不许重启，如何急救？”
T9架构师方案：
- 渐进式Rehash（Redis同款）
class ProgressiveHashMap {
std::vector<std::unordered_map<int, int>> tables{2}; // 新旧双表
int rehash_idx = -1; // -1表示未在rehash
void rehashStep() {
if (rehash_idx < 0) return;
auto& old_table = tables[0];
auto& new_table = tables[1];
// 每次迁移1个桶
auto it = old_table.begin();
std::advance(it, rehash_idx);
new_table.insert(*it);
old_table.erase(it);
rehash_idx++;
if (rehash_idx >= old_table.size()) {
tables[0] = std::move(tables[1]); // 迁移完成
rehash_idx = -1;
}
}
public:
void put(int key, int val) {
if (rehash_idx >= 0) rehashStep(); // 每次操作迁移一桶
// ... 正常插入逻辑
}
};2.替代分配器降低碎片
LD_PRELOAD="/usr/lib/libtcmalloc.so" ./my_program # 加载tcmalloc
- 性能对比：
方案 平均延迟 碎片率 glibc malloc 120ms 高 tcmalloc 35ms 低70% 渐进式Rehash <1ms波动 趋近0
💎 大厂面试终极技巧
- 数据结构选择铁律：
- 随机访问 →
vector（连续内存+缓存友好） - 高频插入删除 →
list（O(1)节点操作） - 快速查找 →
unordered_map（哈希表）或map（红黑树有序）
- 随机访问 →
- 代码手撕三大原则：
- 先写边界条件（空输入、容量满等）
- 主动检测内存泄漏（智能指针/析构函数）
- 时间复杂度必须脱口而出
- 反杀追问话术：
“我设计的LRU时间复杂度是O(1)，因为哈希表查找O(1)，链表移动节点也是O(1)。您担心线程安全问题？可以引入分段锁，但读多写少场景更推荐
std::shared_mutex...”
来自阿里P9的忠告：
“区分普通码农和架构师的核心——普通玩家背答案，高端玩家能改造STL容器，地狱玩家手写内存分配器。”
资源直通：
戳这里>>「