deepseek梳理java高级开发工程师算法面试题

Java高级工程师算法面试题与答案

一、数据结构与算法基础

1. 红黑树与AVL树比较

题目：详细说明红黑树和AVL树的区别及各自的适用场景，并用Java实现红黑树的插入操作。

答案：

区别对比：

┌──────────────────┬──────────────────────────────┬──────────────────────────────┐
│ 特性            │ 红黑树                        │ AVL树                        │
├──────────────────┼──────────────────────────────┼──────────────────────────────┤
│ 平衡标准        │ 松散平衡（最长路径≤2倍最短路径）│ 严格平衡（左右子树高度差≤1）  │
│ 插入/删除效率   │ O(1)旋转次数                  │ O(log n)旋转次数              │
│ 查找效率        │ 稍慢（因不够严格平衡）         │ 更快                          │
│ 存储开销        │ 1bit颜色信息                  │ 平衡因子（int）               │
│ 适用场景        │ 频繁插入删除（如Java HashMap）│ 查找密集型（如数据库索引）     │
└──────────────────┴──────────────────────────────┴──────────────────────────────┘

红黑树Java实现：

class RedBlackTree {private static final boolean RED = true;private static final boolean BLACK = false;class Node {int key;Node left, right;boolean color;Node(int key) {this.key = key;this.color = RED; // 新节点总是红色}}private Node root;private boolean isRed(Node x) {return x != null && x.color == RED;}public void insert(int key) {root = insert(root, key);root.color = BLACK; // 根节点始终黑色}private Node insert(Node h, int key) {if (h == null) return new Node(key);if (key < h.key) h.left = insert(h.left, key);else if (key > h.key) h.right = insert(h.right, key);// 平衡化操作if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);if (isRed(h.left) && isRed(h.right)) flipColors(h);return h;}private Node rotateLeft(Node h) {Node x = h.right;h.right = x.left;x.left = h;x.color = h.color;h.color = RED;return x;}// rotateRight和flipColors实现类似...
}

二、高级算法设计

2. 分布式ID生成算法

题目：设计一个分布式环境下高性能ID生成服务，要求满足：

1. 全局唯一
2. 趋势递增
3. 高可用
4. 每秒至少10万ID生成

答案：

Snowflake算法改进版：

public class DistributedIdGenerator {private final long twepoch = 1288834974657L; // 起始时间戳private final long workerIdBits = 10L; // 工作机器ID位数private final long maxWorkerId = ~(-1L << workerIdBits);private final long sequenceBits = 12L; // 序列号位数private final long workerIdShift = sequenceBits;private final long timestampShift = sequenceBits + workerIdBits;private final long sequenceMask = ~(-1L << sequenceBits);private long workerId;private long sequence = 0L;private long lastTimestamp = -1L;public DistributedIdGenerator(long workerId) {if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException("workerId不合法");}this.workerId = workerId;}public synchronized long nextId() {long timestamp = timeGen();if (timestamp < lastTimestamp) {throw new RuntimeException("时钟回拨异常");}if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;if (sequence == 0) {timestamp = tilNextMillis(lastTimestamp);}} else {sequence = 0L;}lastTimestamp = timestamp;return ((timestamp - twepoch) << timestampShift) | (workerId << workerIdShift) | sequence;}private long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}private long timeGen() {return System.currentTimeMillis();}
}

优化点：

1. 时钟回拨处理：抛出异常或等待
2. 性能优化：无锁CAS（如用AtomicLong）
3. 分段缓冲：预生成ID减少实时计算压力
4. 监控报警：ID生成速率监控

三、并发算法

3. 高效缓存淘汰算法

题目：实现一个线程安全的LFU（Least Frequently Used）缓存，要求所有操作时间复杂度O(1)。

答案：

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 FreqList {int freq;Node head, tail;FreqList prev, next;FreqList(int freq) {this.freq = freq;head = new Node(0, 0);tail = new Node(0, 0);head.next = tail;tail.prev = head;}void addNode(Node node) {node.next = head.next;head.next.prev = node;head.next = node;node.prev = head;}void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}boolean isEmpty() {return head.next == tail;}}private int capacity;private Map<Integer, Node> cache;private Map<Integer, FreqList> freqMap;private FreqList minFreqList;public LFUCache(int capacity) {this.capacity = capacity;cache = new HashMap<>();freqMap = new HashMap<>();minFreqList = new FreqList(0);freqMap.put(0, minFreqList);}public int get(int key) {if (!cache.containsKey(key)) return -1;Node node = cache.get(key);updateFreq(node);return node.value;}public void put(int key, int value) {if (capacity == 0) return;if (cache.containsKey(key)) {Node node = cache.get(key);node.value = value;updateFreq(node);return;}if (cache.size() == capacity) {Node toRemove = minFreqList.tail.prev;minFreqList.removeNode(toRemove);cache.remove(toRemove.key);if (minFreqList.isEmpty()) {freqMap.remove(minFreqList.freq);}}Node newNode = new Node(key, value);cache.put(key, newNode);FreqList freqList = freqMap.getOrDefault(1, new FreqList(1));freqList.addNode(newNode);freqMap.put(1, freqList);minFreqList = freqList;}private void updateFreq(Node node) {FreqList oldList = freqMap.get(node.freq);oldList.removeNode(node);if (oldList.isEmpty() && node.freq == minFreqList.freq) {minFreqList = oldList.next != null ? oldList.next : oldList;}node.freq++;FreqList newList = freqMap.getOrDefault(node.freq, new FreqList(node.freq));newList.addNode(node);freqMap.put(node.freq, newList);}
}

时间复杂度分析：

• get操作：HashMap查询O(1) + 链表操作O(1) = O(1)
• put操作：HashMap查询O(1) + 链表操作O(1) = O(1)
• 空间复杂度：O(capacity)

四、分布式算法

4. 一致性哈希算法

题目：实现带虚拟节点的一致性哈希算法，解决分布式缓存数据倾斜问题。

答案：

public class ConsistentHash<T> {private final HashFunction hashFunction;private final int numberOfReplicas; // 虚拟节点数private final SortedMap<Long, T> circle = new TreeMap<>();public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,Collection<T> nodes) {this.hashFunction = hashFunction;this.numberOfReplicas = numberOfReplicas;for (T node : nodes) {add(node);}}public void add(T node) {for (int i = 0; i < numberOfReplicas; i++) {long hash = hashFunction.hash(node.toString() + i);circle.put(hash, node);}}public void remove(T node) {for (int i = 0; i < numberOfReplicas; i++) {long hash = hashFunction.hash(node.toString() + i);circle.remove(hash);}}public T get(Object key) {if (circle.isEmpty()) return null;long hash = hashFunction.hash(key.toString());if (!circle.containsKey(hash)) {SortedMap<Long, T> tailMap = circle.tailMap(hash);hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();}return circle.get(hash);}interface HashFunction {long hash(String key);}// 测试用例public static void main(String[] args) {Set<String> nodes = new HashSet<>(Arrays.asList("Node1", "Node2", "Node3"));ConsistentHash<String> ch = new ConsistentHash<>(key -> {// 使用MD5哈希try {MessageDigest md = MessageDigest.getInstance("MD5");byte[] digest = md.digest(key.getBytes());return ((long)(digest[3] & 0xFF) << 24) | ((long)(digest[2] & 0xFF) << 16)| ((long)(digest[1] & 0xFF) << 8) | (digest[0] & 0xFF);} catch (NoSuchAlgorithmException e) {return key.hashCode();}}, 1000, nodes);System.out.println(ch.get("user123")); // 返回对应的节点}
}

优化点：

1. 虚拟节点数量：通常设置100-200个
2. 哈希函数选择：MD5、MurmurHash等
3. 数据迁移：节点增减时只影响相邻节点
4. 监控统计：节点负载均衡监控

五、机器学习算法

5. 推荐系统相似度算法

题目：实现基于用户的协同过滤推荐算法，包含余弦相似度计算和推荐生成。

答案：

public class UserCFRecommender {private Map<Integer, Map<Integer, Double>> userItemMatrix; // 用户-物品评分矩阵public UserCFRecommender(Map<Integer, Map<Integer, Double>> userItemMatrix) {this.userItemMatrix = userItemMatrix;}// 计算用户相似度矩阵public Map<Integer, Map<Integer, Double>> calculateUserSimilarities() {Map<Integer, Map<Integer, Double>> simMatrix = new HashMap<>();List<Integer> users = new ArrayList<>(userItemMatrix.keySet());for (int i = 0; i < users.size(); i++) {int u1 = users.get(i);simMatrix.putIfAbsent(u1, new HashMap<>());for (int j = i + 1; j < users.size(); j++) {int u2 = users.get(j);double similarity = cosineSimilarity(userItemMatrix.get(u1),userItemMatrix.get(u2));simMatrix.get(u1).put(u2, similarity);simMatrix.putIfAbsent(u2, new HashMap<>());simMatrix.get(u2).put(u1, similarity);}}return simMatrix;}// 余弦相似度计算private double cosineSimilarity(Map<Integer, Double> v1, Map<Integer, Double> v2) {Set<Integer> commonItems = new HashSet<>(v1.keySet());commonItems.retainAll(v2.keySet());double dotProduct = 0.0;double norm1 = 0.0;double norm2 = 0.0;for (int item : commonItems) {dotProduct += v1.get(item) * v2.get(item);}for (double rating : v1.values()) {norm1 += Math.pow(rating, 2);}for (double rating : v2.values()) {norm2 += Math.pow(rating, 2);}return dotProduct / (Math.sqrt(norm1) * Math.sqrt(norm2));}// 生成推荐public List<Integer> recommendItems(int userId, int topN) {Map<Integer, Double> scores = new HashMap<>();Map<Integer, Double> userRatings = userItemMatrix.get(userId);Map<Integer, Map<Integer, Double>> simMatrix = calculateUserSimilarities();for (Map.Entry<Integer, Map<Integer, Double>> entry : userItemMatrix.entrySet()) {int otherUserId = entry.getKey();if (otherUserId == userId) continue;double similarity = simMatrix.get(userId).getOrDefault(otherUserId, 0.0);if (similarity <= 0) continue;for (Map.Entry<Integer, Double> itemEntry : entry.getValue().entrySet()) {int itemId = itemEntry.getKey();if (userRatings.containsKey(itemId)) continue;scores.merge(itemId, itemEntry.getValue() * similarity, Double::sum);}}return scores.entrySet().stream().sorted(Map.Entry.<Integer, Double>comparingByValue().reversed()).limit(topN).map(Map.Entry::getKey).collect(Collectors.toList());}
}

优化方向：

1. 相似度计算：改用皮尔逊相关系数
2. 矩阵稀疏性：使用稀疏矩阵存储
3. 实时更新：增量计算相似度
4. 并行计算：MapReduce实现