跳到主要内容

设计题

问题​

Java 面试中常见的算法设计题有哪些？

答案​

LRU 缓存（LeetCode 146）​

HashMap + 双向链表
class LRUCache {
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(), tail = new Node();
    private int capacity;
    
    static class Node {
        int key, val;
        Node prev, next;
        Node() {}
        Node(int k, int v) { key = k; val = v; }
    }
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);  // 访问后移到头部
        return node.val;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.val = value;
            moveToHead(node);
        } else {
            node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail();  // 淘汰最久未使用
                map.remove(removed.key);
            }
        }
    }
    
    private void addToHead(Node node) {
        node.prev = head; node.next = head.next;
        head.next.prev = node; head.next = node;
    }
    private void removeNode(Node node) {
        node.prev.next = node.next; node.next.prev = node.prev;
    }
    private void moveToHead(Node node) { removeNode(node); addToHead(node); }
    private Node removeTail() { Node node = tail.prev; removeNode(node); return node; }
}

最小栈（LeetCode 155）​

主栈 + 辅助栈
class MinStack {
    Deque<Integer> stack = new ArrayDeque<>();
    Deque<Integer> minStack = new ArrayDeque<>();
    
    public void push(int val) {
        stack.push(val);
        minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek()));
    }
    
    public void pop() { stack.pop(); minStack.pop(); }
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

用栈实现队列（LeetCode 232）​

双栈：输入栈 + 输出栈
class MyQueue {
    Deque<Integer> inStack = new ArrayDeque<>();
    Deque<Integer> outStack = new ArrayDeque<>();
    
    public void push(int x) { inStack.push(x); }
    
    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) outStack.push(inStack.pop());
        }
        return outStack.peek();
    }
    
    public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); }
}

随机化集合（LeetCode 380）​

ArrayList + HashMap，O(1) 插入删除随机获取
class RandomizedSet {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();  // 值 → 索引
    Random rand = new Random();
    
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val);
        int last = list.get(list.size() - 1);
        list.set(idx, last);           // 用最后一个元素覆盖
        map.put(last, idx);
        list.remove(list.size() - 1);  // 删除最后一个
        map.remove(val);
        return true;
    }
    
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}

常见面试问题​

Q1: LRU 为什么用双向链表？​

答案：

双向链表支持 O(1)O(1) 删除任意节点（已知节点引用时直接修改前后指针）。单向链表删除需要知道前驱节点，需 O(n)O(n) 查找。

Q2: LRU 能用 LinkedHashMap 实现吗？​

答案：

可以，LinkedHashMap 内部就是 HashMap + 双向链表，设置 accessOrder=true 即可：

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);  // accessOrder = true
        this.capacity = capacity;
    }
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > capacity;
    }
}

Q3: LFU 缓存怎么实现？​

答案：

  • 维护 key → (val, freq) 和 freq → LinkedHashSet<key>
  • 每次访问频率+1，移到新频率的集合
  • 淘汰时从最小频率的集合中移除最早插入的

相关链接​