Java秋招面试之第14章 系统设计算法题
第14章 系统设计算法题
面试重要程度：⭐⭐⭐⭐⭐
常见提问方式：设计数据结构、实现缓存、设计算法
预计阅读时间：45分钟
开场白
兄弟，系统设计算法题是大厂面试的重头戏！这类题目不仅考察你的编程能力，更重要的是考察你的系统设计思维和工程实践能力。从LRU缓存到一致性哈希，从限流器到分布式锁，这些都是实际工作中会遇到的核心问题。
今天我们就把这些经典的系统设计算法题彻底搞定，让你在面试中展现出架构师级别的思维深度。
🗄️ 14.1 缓存设计
LRU缓存实现
面试必考：
面试官："设计并实现一个LRU（最近最少使用）缓存，支持get和put操作，时间复杂度要求O(1)。"
核心思路与实现：
// LRU缓存 - LeetCode 146
public class LRUCache {
// 双向链表节点
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点，简化边界处理
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果key存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
} else {
// 如果key存在，修改value，并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode lastNode = tail.prev;
removeNode(lastNode);
return lastNode;
}
// 面试加分项：提供调试方法
public void printCache() {
System.out.print("LRU Cache: ");
DLinkedNode current = head.next;
while (current != tail) {
System.out.print("(" + current.key + "," + current.value + ") ");
current = current.next;
}
System.out.println();
}
}
// 面试技巧：解释设计思路
class LRUCacheExplanation {
public void explainDesign() {
System.out.println("=== LRU缓存设计思路 ===");
System.out.println("1. 数据结构选择：");
System.out.println(" - HashMap：O(1)时间查找节点");
System.out.println(" - 双向链表：O(1)时间移动节点");
System.out.println("2. 核心操作：");
System.out.println(" - get：查找 + 移到头部");
System.out.println(" - put：插入/更新 + 移到头部 + 可能删除尾部");
System.out.println("3. 为什么用双向链表：");
System.out.println(" - 需要O(1)删除任意节点");
System.out.println(" - 单向链表删除需要O(n)找前驱节点");
System.out.println("4. 伪头尾节点的作用：");
System.out.println(" - 简化边界条件处理");
System.out.println(" - 避免空指针异常");
}
}
LFU缓存实现
进阶考题：
// LFU缓存 - LeetCode 460
public class LFUCache {
// 节点定义
class Node {
int key, value, freq;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
this.freq = 1;
}
}
// 双向链表（用于存储相同频率的节点）
class DoublyLinkedList {
Node head, tail;
DoublyLinkedList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
void addFirst(Node node) {
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
Node removeLast() {
if (head.next == tail) return null;
Node last = tail.prev;
remove(last);
return last;
}
boolean isEmpty() {
return head.next == tail;
}
}
private int capacity;
private int minFreq;
private Map<Integer, Node> keyToNode;
private Map<Integer, DoublyLinkedList> freqToList;
public LFUCache(int capacity) {
this.capacity = capacity;
this.minFreq = 1;
this.keyToNode = new HashMap<>();
this.freqToList = new HashMap<>();
}
public int get(int key) {
Node node = keyToNode.get(key);
if (node == null) {
return -1;
}
// 增加频率
increaseFreq(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) return;
Node node = keyToNode.get(key);
if (node != null) {
// 更新已存在的key
node.value = value;
increaseFreq(node);
} else {
// 插入新key
if (keyToNode.size() >= capacity) {
// 删除最少使用的节点
removeMinFreqNode();
}
// 插入新节点
Node newNode = new Node(key, value);
keyToNode.put(key, newNode);
freqToList.computeIfAbsent(1, k -> new DoublyLinkedList()).addFirst(newNode);
minFreq = 1;
}
}
private void increaseFreq(Node node) {
int oldFreq = node.freq;
int newFreq = oldFreq + 1;
// 从旧频率链表中移除
freqToList.get(oldFreq).remove(node);
// 如果旧频率链表为空且是最小频率，更新最小频率
if (freqToList.get(oldFreq).isEmpty() && oldFreq == minFreq) {
minFreq++;
}
// 更新节点频率并加入新频率链表
node.freq = newFreq;
freqToList.computeIfAbsent(newFreq, k -> new DoublyLinkedList()).addFirst(node);
}
private void removeMinFreqNode() {
DoublyLinkedList minFreqList = freqToList.get(minFreq);
Node nodeToRemove = minFreqList.removeLast();
keyToNode.remove(nodeToRemove.key);
}
// 面试加分项：复杂度分析
public void analyzeComplexity() {
System.out.println("=== LFU缓存复杂度分析 ===");
System.out.println("时间复杂度：");
System.out.println("- get操作：O(1)");
System.out.println("- put操作：O(1)");
System.out.println("空间复杂度：O(capacity)");
System.out.println("关键设计：");
System.out.println("- keyToNode：快速定位节点");
System.out.println("- freqToList：按频率组织节点");
System.out.println("- minFreq：快速找到最小频率");
}
}
🔐 14.2 数据结构设计
设计Twitter
系统设计经典题：
// 设计Twitter - LeetCode 355
public class Twitter {
// 推文类
class Tweet {
int id;
int timestamp;
Tweet next;
Tweet(int id, int timestamp) {
this.id = id;
this.timestamp = timestamp;
}
}
// 用户类
class User {
int id;
Set<Integer> followed;
Tweet tweetHead;
User(int id) {
this.id = id;
this.followed = new HashSet<>();
follow(id); // 关注自己
}
void follow(int followeeId) {
followed.add(followeeId);
}
void unfollow(int followeeId) {
if (followeeId != this.id) { // 不能取关自己
followed.remove(followeeId);
}
}
void post(int tweetId, int timestamp) {
Tweet tweet = new Tweet(tweetId, timestamp);
tweet.next = tweetHead;
tweetHead = tweet;
}
}
private Map<Integer, User> userMap;
private int timestamp;
public Twitter() {
userMap = new HashMap<>();
timestamp = 0;
}
public void postTweet(int userId, int tweetId) {
if (!userMap.containsKey(userId)) {
userMap.put(userId, new User(userId));
}
userMap.get(userId).post(tweetId, timestamp++);
}
public List<Integer> getNewsFeed(int userId) {
List<Integer> result = new ArrayList<>();
if (!userMap.containsKey(userId)) {
return result;
}
// 使用优先队列合并多个用户的推文
PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.timestamp - a.timestamp);
User user = userMap.get(userId);
for (int followeeId : user.followed) {
User followee = userMap.get(followeeId);
if (followee != null && followee.tweetHead != null) {
pq.offer(followee.tweetHead);
}
}
// 取最新的10条推文
while (!pq.isEmpty() && result.size() < 10) {
Tweet tweet = pq.poll();
result.add(tweet.id);
if (tweet.next != null) {
pq.offer(tweet.next);
}
}
return result;
}
public void follow(int followerId, int followeeId) {
if (!userMap.containsKey(followerId)) {
userMap.put(followerId, new User(followerId));
}
if (!userMap.containsKey(followeeId)) {
userMap.put(followeeId, new User(followeeId));
}
userMap.get(followerId).follow(followeeId);
}
public void unfollow(int followerId, int followeeId) {
if (userMap.containsKey(followerId)) {
userMap.get(followerId).unfollow(followeeId);
}
}
// 面试技巧：解释设计选择
public void explainDesign() {
System.out.println("=== Twitter设计思路 ===");
System.out.println("1. 数据结构选择：");
System.out.println(" - HashMap存储用户：O(1)查找用户");
System.out.println(" - 链表存储推文：按时间顺序，便于遍历");
System.out.println(" - 优先队列合并：多路归并，获取最新推文");
System.out.println("2. 关键优化：");
System.out.println(" - 推文链表：避免存储所有推文的全局列表");
System.out.println(" - 懒加载：只在需要时创建用户对象");
System.out.println(" - 限制数量：只返回最新10条推文");
}
}
设计跳表
高级数据结构：
// 跳表实现
public class Skiplist {
class Node {
int val;
Node[] next;
Node(int val, int level) {
this.val = val;
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
Java面试圣经 文章被收录于专栏
Java面试圣经，带你练透java圣经
