【面试题】大厂高压面经实录丨第二期
C++数据结构篇
大厂高压面经实录，结合腾讯、阿里、字节等真实技术面试场景，包含压迫式追问、核心陷阱和代码实战，助你彻底碾压面试官：
⚡️ 一、Top K问题：堆 vs 快速选择（字节跳动3面原题）
面试官（打断式追问）：“10亿整数找Top 100，内存限制1GB，5分钟内手撕代码，禁用第三方库！”
大厂级应答：
-
最小堆解法（海量数据唯一正解）
#include #include std::vector topK(std::vector& nums, int k) { std::priority_queue<int, std::vector, std::greater> min_heap; // 最小堆 for (int num : nums) { if (min_heap.size() min_heap.top()) { min_heap.pop(); min_heap.push(num); // 淘汰堆顶，加入新元素 } } // 转存结果（注意：堆中是无序的） std::vector 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& nums, int left, int right) { int pivot = nums[right]; int i = left; for (int j = left; j = pivot) std::swap(nums[i++], nums[j]); // 注意：降序排列 } std::swap(nums[i], nums[right]); return i;}void quickSelect(std::vector& 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 #include class LRUCache {private: struct Node { int key, val; }; std::list cache; // 双向链表：存储节点 std::unordered_map<int, std::list::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 #include bool hasCycle(int n, std::vector<std::vector>& graph) { std::vector indegree(n, 0); std::queue 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> tables{2}; // 新旧双表 int rehash_idx = -1; // -1表示未在rehash void rehashStep() { 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容器，地狱玩家手写内存分配器。”
资源直通：
戳这里>>「