蚂蚁-C++开发-一面 面经

1. 简单做个自我介绍，重点说说你的项目经历和技术栈。

答案要点：

• 基本信息：学校、专业、预期实习时间
• 技术栈：C++、数据结构与算法、Linux、数据库等
• 项目经历：1-2个核心项目，突出技术亮点
• 个人优势：学习能力、代码质量、问题解决能力
• 对蚂蚁的了解和期望

2. 详细介绍一下你简历中的某个项目，包括技术选型、架构设计、遇到的难点和解决方案。

答案要点：

• 项目背景：业务场景、用户规模、技术挑战
• 技术架构：模块划分、技术选型理由、设计模式
• 个人职责：负责的具体模块和功能
• 技术难点： 性能瓶颈及优化方案并发问题及解决方法数据一致性保证异常处理和容错机制
• 量化成果：性能提升、响应时间、资源占用
• 技术沉淀：可复用的组件、文档、经验总结

3. 有一个100GB的文件，内存只有4GB，如何找出文件中出现次数最多的前10个数字？

答案：

• 方案一：分治 + 哈希第一遍：哈希分桶，将数字hash到1000个小文件相同数字一定在同一个文件中第二遍：对每个小文件统计频率，维护全局Top10使用最小堆维护Top10，遍历所有文件的统计结果时间复杂度：O(n)，空间复杂度：O(k)，k为不同数字个数
• 方案二：外部排序 + 统计外部归并排序将文件排序顺序扫描统计相邻相同数字的频率维护最小堆记录Top10时间复杂度：O(n log n)
• 方案三：多路归并 + 在线统计将文件分块，每块排序多路归并的同时统计频率边归并边更新Top10

4. 设计一个近似算法，只读一遍文件就能近似找出出现次数最多的前10个数字。什么情况效果好？什么情况效果差？

答案：

• Count-Min Sketch算法：使用多个哈希函数和计数数组每个数字映射到多个位置，取最小值作为估计空间复杂度：O(w * d)，w为数组宽度，d为哈希函数个数只会高估，不会低估
• Lossy Counting算法：维护一个计数器表，设置阈值低于阈值的元素定期删除适合找频繁项
• Space-Saving算法（推荐）：维护k个计数器（k=100，远大于10）新元素：如果在表中则计数+1，否则替换最小计数器最后返回计数最大的10个空间复杂度：O(k)
• 效果分析：效果好的情况： 数据分布倾斜，热点数据明显Top10的频率远高于其他数字数据重复度高效果差的情况： 数据分布均匀，没有明显热点Top10和Top11-20频率接近数据种类极多，每个数字出现次数都很少

5. 详细说明外部归并排序的原理和实现步骤。

答案：

• 基本思想：将大文件分成多个可以放入内存的小块对每个小块进行内部排序多路归并这些有序小块
• 实现步骤：分块排序阶段：读取能放入内存的数据块（如100MB）使用快速排序或堆排序排序将排序结果写入临时文件重复直到处理完所有数据多路归并阶段：同时打开所有临时文件为每个文件维护一个输入缓冲区使用最小堆选择当前最小元素将最小元素写入输出缓冲区从对应文件读取下一个元素重复直到所有文件处理完
• 优化策略：多级归并：如果临时文件太多，分多轮归并缓冲区优化：合理分配输入输出缓冲区大小预读：异步IO，提前读取数据压缩：临时文件压缩节省磁盘IO
• 复杂度分析：时间复杂度：O(n log n)空间复杂度：O(M)，M为内存大小IO次数：O(n log(n/M))

6. 手写代码：实现有向无环图（DAG）的深拷贝。

答案：

#include <unordered_map>
#include <vector>

// 图节点定义
class Node {
public:
    int val;
    std::vector<Node*> neighbors;
    
    Node(int _val) : val(_val) {}
};

class Solution {