研发工程师面试宝典 - 第4节

面试问题：请详细对比数组和链表的区别，并结合工程场景说明选型依据。

• 面试官考察点：基础数据结构特性掌握、复杂度分析、工程权衡能力。
• 回答框架： 存储结构 → 随机访问性能 → 增删性能 → 缓存局部性 → 工程场景映射。
• 示例回答：“数组连续内存，支持O(1)随机访问，但中间增删需移动元素（O(n)）；链表离散存储，支持O(1)插入/删除（已知节点），但随机访问需遍历（O(n)）。Java中ArrayList封装数组，适用读多写少（如日志存储）；LinkedList封装链表，适用写多读少（如消息队列）。”
• 可能追问：“CPU缓存行如何影响数组遍历性能？”“HashMap的数组开链结构结合了哪些优势？”

面试问题：请设计和实现一个最近最少使用（LRU）缓存，要求get和put操作时间复杂度为O(1)。

• 面试官考察点：数据结构组合设计能力、手写代码边界控制、时空复杂度意识。
• 回答框架： 选型（HashMap+双向链表） → 核心API（get/put） → 复杂度分析 → 手写代码（注意头尾哨兵节点）。
• 示例回答：“采用HashMap + 双向链表。Map提供O(1)查询，链表维护访问顺序。get时若存在则移至头部；put时若key存在则更新值并移至头部，不存在则创建新节点插入头部，若容量超限则删除尾部节点。Java的LinkedHashMap正是基于此实现，需注意重写removeEldestEntry方法。”
• 可能追问：“为什么必须用双向链表而不是单向？”“如何实现线程安全的版本（ConcurrentHashMap + 锁）？”

面试问题：给定整数数组 nums 和整数目标值 target，请返回和为目标值的两个数的数组下标。

• 面试官考察点：思维推导过程（暴力→优化）、哈希表运用、变量命名规范、边界条件处理。
• 回答框架： 暴力解 → 瓶颈分析 → 哈希优化 → 手写代码（含空值判断） → 测试用例。
• 示例回答：“暴力两层循环时间复杂度O(n²)，可优化为哈希表。遍历数组，检查target - nums[i]是否在map中，在则返回索引，否则写入map。编码时注意参数校验和变量命名，如用numToIndexMap命名map，增强代码可读性。整体时间复杂度O(n)，空间复杂度O(n)。”
• 可能追问：“如果数组是升序排列的，如何进一步优化？”（双指针O(n)，空间O(1)）