---
id: cs.algorithms.interview
title: 数据结构与算法面试题
type: interview
domain: cs
stack: [algorithms]
tags: [算法, 数据结构, 手写代码, 面试]
level: basic
related: [cs.algorithms.complexity-patterns]
week: [16]
---

# 数据结构与算法面试题

## 基础

### 【基础】哈希表的原理是什么？冲突怎么处理？

**参考答案**：通过哈希函数把键映射到数组下标，平均 O(1) 查找。冲突处理：链地址法（同一位置挂链表 / 树）、开放寻址法（探测下一个空位）。负载因子过高时扩容并重新哈希。

**追问**：Python 的 dict 用哪种？→ 开放寻址；从 3.7 起保证插入顺序。

### 【基础】手写二分查找，找第一个大于等于 target 的位置。

**参考答案**：左闭右开 `[lo, hi)`，`arr[mid] < target` 时 `lo = mid + 1`，否则 `hi = mid`，循环条件 `lo < hi`，返回 `lo`。见[示例](examples/patterns/patterns.py)。

**追问**：怎么找最后一个等于 target 的位置？→ 找第一个大于 target 的位置再减 1，并检查该位置的值是否等于 target。

### 【基础】数组和链表的区别？

**参考答案**：数组连续存储，随机访问 O(1)，中间插入删除 O(n)，缓存友好；链表随机访问 O(n)，已知节点时插入删除 O(1)，额外的指针开销。

**追问**：LRU 为什么用哈希表 + 双向链表？→ 哈希表 O(1) 定位节点，双向链表 O(1) 移动和删除节点。

## 进阶

### 【进阶】实现 LRU 缓存，get 和 put 都是 O(1)。

**参考答案**：哈希表存键到节点的映射，双向链表维护使用顺序：访问时移到尾部，超容量时删除头部。Python 可用 `OrderedDict.move_to_end` 和 `popitem(last=False)`。

**追问**：多线程下怎么办？→ 加锁，或分段锁降低竞争；如果是分布式缓存，用 Redis 的淘汰策略（`allkeys-lru`）。

### 【进阶】如何从海量数据中找出出现次数最多的 K 个？

**参考答案**：哈希计数 + 大小为 K 的小顶堆，O(n log K)。数据放不进内存时：按哈希分片写入多个文件，分别统计 Top K，再合并。

**追问**：可以接受误差时？→ Count-Min Sketch 等近似计数结构，内存固定。

### 【进阶】怎么判断任务依赖中是否有环？

**参考答案**：DFS 三色标记（未访问、访问中、已完成），遇到“访问中”的节点说明有环；或者 Kahn 算法：不断移除入度为 0 的节点，最后仍有节点未移除说明有环。

**追问**：哪些业务会用到？→ 构建系统、CI 流水线、工作流引擎、数据管道调度。

## 场景题

### 【场景题】现场手写：无重复字符的最长子串。

**参考答案**：滑动窗口，记录每个字符最后出现的位置；遇到重复且在窗口内时，左边界移到重复位置的下一位；每步更新最大长度。O(n)。注意 "abba" 这类重复字符已在窗口外的情况。

**追问**：如果允许最多 K 个不同字符？→ 窗口内用哈希表计数，不同字符数超过 K 时收缩左边界。

### 【场景题】运营后台要显示每小时的热门问题 Top 20，怎么做？

**参考答案**：规范化文本 → 哈希计数 → 堆取 Top K；多实例用 Redis 有序集合按小时分 key 累加并设置过期；语义相近的问题再做聚类合并。详见[业务中的算法](scenarios/business-algorithms.md)。

**追问**：复杂度是多少？→ 计数 O(n)，取 Top K 为 O(m log K)，m 是不同问题的数量。