📚 课程目录第4章技术面试基础题

技术面试基础题：编程语言、数据结构、算法高频考点及答题框架

本章聚焦大厂与中小厂在编程语言、数据结构、算法三大方向上的考察差异。核心目标：建立标准化的审题→建模→编码→验证回答路径，在60秒内展现清晰的解题思维。

  📌 本章复习策略： 大厂重最优解 + 源码原理，中小厂重基础实现 + 场景判断。每道题先用“暴力解”保底，再展示优化思路，最后落地代码。

类别	高频考点	大厂侧重	中小厂侧重
编程语言 Java / Go / Python	HashMap 原理、并发机制、JVM 内存模型、垃圾回收、Go goroutine 调度	源码深度（JDK 8 vs 11）、锁优化、内存调优、协程调度细节	基础 API 使用、常见异常处理、集合类选型、包管理
数据结构数组 / 链表 / 栈 / 队列 / 树	数组 vs 链表、栈与队列互实现、二叉树遍历、LRU 缓存	变体结构（跳表、布隆过滤器）、多线程安全、O(1) 特殊操作	基本操作复杂度、数组与链表场景对比、简单树遍历
算法排序 / 搜索 / 递归 / DP	快速排序、二分查找、反转链表、两数之和、斐波那契	最优解 + 复杂度分析、空间压缩、海量数据处理	基础实现、边界处理、暴力解优化到 O(n²) 以内

编程语言 · 高频

问题：请描述 Java 中 HashMap 的 put 和 get 流程

🎯 面试官考察点

是否读过 HashMap 源码，理解数组+链表+红黑树结构
对哈希冲突、扩容、树化阈值的掌握
能否区分 JDK 7 与 JDK 8 的实现差异

📐 回答框架

hash 计算 → 槽位定位 → 冲突处理 → 树化判断 → 扩容机制。先讲 put 流程，再对比 get 流程，最后点出 JDK 8 优化点。

💡 示例回答

put 时先对 key 做 hash 扰动，定位数组槽位；空槽直接插入，冲突则遍历链表或红黑树查找 key，存在则覆盖，否则新增。链表长度 ≥8 且数组长度 ≥64 时转红黑树。get 流程类似，通过 hash 定位后遍历查找。JDK 8 相比 7 引入红黑树，优化了 hash 碰撞严重时的性能。

❓ 可能追问

负载因子默认 0.75 的原因？
红黑树与链表转换阈值为什么是 8 和 6？
HashMap 在并发下可能出什么问题？

⚠️ 避坑提醒

❌ 不要只说“数组+链表”，必须提红黑树优化（JDK 8+）。
❌ 避免混淆 hashCode() 和 equals() 的作用顺序。
✅ 主动提及“JDK 7 头插法 vs JDK 8 尾插法”体现源码深度。

数据结构 · 基础

问题：数组和链表有什么区别？各自适合什么场景？

🎯 面试官考察点

是否理解存储结构差异带来的时间复杂度变化
能否结合CPU缓存行解释数组的局部性优势
场景判断能力：读多写少 vs 频繁增删

📐 回答框架

存储结构 → 访问方式 → 插入删除 → 内存分配 → 场景推荐。先对比核心差异，再给出选型建议，最后提一下缓存友好性。

💡 示例回答

数组连续内存存储，支持 O(1) 随机访问，但插入删除需移动元素 O(n)；链表非连续存储，不支持随机访问 O(n)，插入删除仅改指针 O(1)。数组适合读多写少、大小固定的场景，链表适合频繁增删、大小不定的场景。另外数组的连续空间对 CPU 缓存更友好。

❓ 可能追问

ArrayList 和 LinkedList 实际应用如何选择？
双向链表和单向链表各自优势？
数组和链表在并发场景下的问题？

⚠️ 避坑提醒

❌ 避免只说“数组查询快、链表增删快”，必须带上时间复杂度。
❌ 不要忽略“数组扩容代价”和“链表额外内存开销”。
✅ 主动提及“ArrayList 扩容因子 1.5”或“LinkedList 内存碎片”加分。

算法 · 高频

问题：请实现反转链表，并分析复杂度

🎯 面试官考察点

链表指针操作的基本功，能否正确处理引用丢失
迭代与递归两种思路的掌握程度
边界情况处理：空链表、单节点、两个节点

📐 回答框架

迭代法（三指针）→ 递归法 → 边界处理 → 复杂度分析。先给出迭代实现，再提递归思路，最后给出时空复杂度。

💡 示例回答

使用三指针迭代：prev 初始为 null，curr 指向 head。遍历时先保存 next = curr.next，再将 curr.next 指向 prev，然后移动 prev = curr，curr = next。遍历结束返回 prev 作为新头节点。时间复杂度 O(n)，空间复杂度 O(1)。递归版本需要 O(n) 栈空间。

❓ 可能追问

递归实现反转链表？
反转链表中第 m 到 n 个节点？
K 个一组反转链表？

⚠️ 避坑提醒

❌ 循环内必须先保存 next，否则断链后无法继续遍历。
❌ 递归法要注意链表长度较大时可能栈溢出。
✅ 面试时主动写出“空链表直接返回 null”作为边界保护。