68 lines
3.5 KiB
Markdown
68 lines
3.5 KiB
Markdown
---
|
||
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 是不同问题的数量。
|