手撕代码

目标

意向职位：高性能计算（HPC）和 AI 基础设施（AI Infra）方向。

需要准备的内容：

• 机试：基础数据结构和算法就行
• 面试：可能拷打并行编程、CUDA 等

思维

• 问题澄清：确认输入输出边界（如“空输入如何处理？”）
• 举例验证：设计常规/边缘用例（如超大矩阵、全零输入）
• 暴力解法：先给出基础方案（如 O(n²) 解法）
• 优化分析：识别重复计算/无效操作（如 DP 状态复用）
• 代码实现：模块化编写 + 即时验证（边写边测临界条件）

算法与数据结构

基础

• 哈希表
  • 两数之和系列变种题（如三数之和、四数之和）
• 堆
  • TOP K 问题
  • 合并 K 个有序链表
  • 双指针（快慢指针、滑动窗口）处理时序数据
  • 数据流中位数
• 树
  • 非递归遍历（迭代法实现 DFS）
  • 最近公共祖先 (LCA)
  • Morris 遍历
• 动态规划
  • 状态压缩技巧（如滚动数组）
  • 字符串编辑距离（递归与迭代两种解法）
  • 背包问题（01 背包/完全背包）

并行

• 矩阵路径 DP（最小路径和）
• 树与图
  • 树形 DP
  • 二叉树中的最大路径和
  • Dijkstra 算法的优先队列优化版本
  • 拓扑排序在任务调度中的应用
  • BFS 的层级并行实现
• 矩阵乘法的 OpenMP 并行版本
• 归并排序的 MPI 版本
• 避免 bank conflict 的矩阵转置核函数

操作系统与体系结构

• 缓存一致性协议
  • false sharing 问题
• 内存对齐原则（数据结构 padding 优化）
• 向量化指令（如 AVX-512 在矩阵运算中的应用）

分布式系统

• 通信开销优化策略（如计算与通信重叠）
• 负载均衡算法（静态划分与动态调度）