手写题清单

面试让你「手写一个 XXX」，考的从来不是记忆力，而是能不能写出边界正确、没有低级错误的代码。这 12 段覆盖了 95% 的现场手写题。每段都有：什么时候考、模板、最容易错的那一行。

怎么练

关掉 IDE 的补全，用记事本写，写完再跑。
每段先写骨架（方法签名 + 边界判断），再填逻辑。
写完主动说一句「我检查一下边界」—— 面试官很吃这套。

1. 单例（三种，按推荐排序）

java

// ① 静态内部类：懒加载 + 线程安全，靠类加载机制保证（首选）
public class Singleton {
    private Singleton() {}
    private static class Holder {
        static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton getInstance() { return Holder.INSTANCE; }
}

// ② 枚举：防反射、防反序列化破坏（最安全）
public enum SingletonEnum {
    INSTANCE;
    public void doSomething() {}
}

// ③ 双重检查锁：必须 volatile，否则可能拿到半初始化对象
public class DclSingleton {
    private static volatile DclSingleton instance;
    public static DclSingleton getInstance() {
        if (instance == null) {
            synchronized (DclSingleton.class) {
                if (instance == null) instance = new DclSingleton();
            }
        }
        return instance;
    }
}

// ① 静态内部类：懒加载 + 线程安全，靠类加载机制保证（首选）
public class Singleton {
    private Singleton() {}
    private static class Holder {
        static final Singleton INSTANCE = new Singleton();
    }
    public static Singleton getInstance() { return Holder.INSTANCE; }
}

// ② 枚举：防反射、防反序列化破坏（最安全）
public enum SingletonEnum {
    INSTANCE;
    public void doSomething() {}
}

// ③ 双重检查锁：必须 volatile，否则可能拿到半初始化对象
public class DclSingleton {
    private static volatile DclSingleton instance;
    public static DclSingleton getInstance() {
        if (instance == null) {
            synchronized (DclSingleton.class) {
                if (instance == null) instance = new DclSingleton();
            }
        }
        return instance;
    }
}

易错点：DCL 少写 volatile —— 这是这道题唯一的坑，面试官就在等你说这句。

2. 生产者消费者（三种写法）

java

// ① 生产直接用 BlockingQueue（面试答这个最稳）
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(1000);
queue.put(task);      // 满则阻塞
Task t = queue.take(); // 空则阻塞

// ② wait/notify 版（让手写就写这个）
class Buffer {
    private final int[] items = new int[10];
    private int count = 0, putIdx = 0, takeIdx = 0;

    public synchronized void put(int v) throws InterruptedException {
        while (count == items.length) wait();      // 必须是 while，不是 if
        items[putIdx] = v;
        putIdx = (putIdx + 1) % items.length;
        count++;
        notifyAll();                               // 用 notifyAll，别用 notify
    }

    public synchronized int take() throws InterruptedException {
        while (count == 0) wait();
        int v = items[takeIdx];
        takeIdx = (takeIdx + 1) % items.length;
        count--;
        notifyAll();
        return v;
    }
}

// ① 生产直接用 BlockingQueue（面试答这个最稳）
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(1000);
queue.put(task);      // 满则阻塞
Task t = queue.take(); // 空则阻塞

// ② wait/notify 版（让手写就写这个）
class Buffer {
    private final int[] items = new int[10];
    private int count = 0, putIdx = 0, takeIdx = 0;

    public synchronized void put(int v) throws InterruptedException {
        while (count == items.length) wait();      // 必须是 while，不是 if
        items[putIdx] = v;
        putIdx = (putIdx + 1) % items.length;
        count++;
        notifyAll();                               // 用 notifyAll，别用 notify
    }

    public synchronized int take() throws InterruptedException {
        while (count == 0) wait();
        int v = items[takeIdx];
        takeIdx = (takeIdx + 1) % items.length;
        count--;
        notifyAll();
        return v;
    }
}

易错点：① if 代替 while（虚假唤醒）；② 用 notify() 只唤醒一个，可能导致两个消费者互等。

3. LRU 缓存（手写双向链表 + HashMap）

java

class LRUCache {
    class Node {
        int k, v;
        Node prev, next;
        Node(int k, int v) { this.k = k; this.v = v; }
    }

    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0); // 哨兵
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        moveToHead(n);
        return n.v;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) {
            n.v = value;
            moveToHead(n);
            return;
        }
        if (map.size() == capacity) {
            Node last = tail.prev;
            remove(last);
            map.remove(last.k);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        addFirst(node);
    }

    private void addFirst(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
    private void remove(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    private void moveToHead(Node n) { remove(n); addFirst(n); }
}

class LRUCache {
    class Node {
        int k, v;
        Node prev, next;
        Node(int k, int v) { this.k = k; this.v = v; }
    }

    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0); // 哨兵
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        moveToHead(n);
        return n.v;
    }

    public void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) {
            n.v = value;
            moveToHead(n);
            return;
        }
        if (map.size() == capacity) {
            Node last = tail.prev;
            remove(last);
            map.remove(last.k);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        addFirst(node);
    }

    private void addFirst(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
    private void remove(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    private void moveToHead(Node n) { remove(n); addFirst(n); }
}

易错点：用哨兵节点，否则头尾判空能写崩。偷懒版：new LinkedHashMap<>(cap, 0.75f, true){ removeEldestEntry... }，但要能讲清为什么。

4. 线程池（简化版，能跑就行）

java

class SimplePool {
    private final BlockingQueue<Runnable> queue;
    private final List<Thread> workers = new ArrayList<>();
    private volatile boolean running = true;

    SimplePool(int core, int queueSize) {
        queue = new ArrayBlockingQueue<>(queueSize);
        for (int i = 0; i < core; i++) {
            Thread t = new Thread(() -> {
                while (running || !queue.isEmpty()) {
                    try {
                        Runnable task = queue.poll(100, TimeUnit.MILLISECONDS);
                        if (task != null) task.run();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                        return;
                    }
                }
            });
            t.start();
            workers.add(t);
        }
    }

    public void execute(Runnable task) throws InterruptedException {
        queue.put(task);   // 满了就阻塞（相当于 CallerRuns 的简化版）
    }

    public void shutdown() {
        running = false;
        workers.forEach(Thread::interrupt);
    }
}

class SimplePool {
    private final BlockingQueue<Runnable> queue;
    private final List<Thread> workers = new ArrayList<>();
    private volatile boolean running = true;

    SimplePool(int core, int queueSize) {
        queue = new ArrayBlockingQueue<>(queueSize);
        for (int i = 0; i < core; i++) {
            Thread t = new Thread(() -> {
                while (running || !queue.isEmpty()) {
                    try {
                        Runnable task = queue.poll(100, TimeUnit.MILLISECONDS);
                        if (task != null) task.run();
                    } catch (InterruptedException e) {
                        Thread.currentThread().interrupt();
                        return;
                    }
                }
            });
            t.start();
            workers.add(t);
        }
    }

    public void execute(Runnable task) throws InterruptedException {
        queue.put(task);   // 满了就阻塞（相当于 CallerRuns 的简化版）
    }

    public void shutdown() {
        running = false;
        workers.forEach(Thread::interrupt);
    }
}

易错点：poll(timeout) 而不是 take()，否则 shutdown 时线程永远醒不来。

5. 快排（含随机 pivot）

java

void quickSort(int[] a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

int partition(int[] a, int l, int r) {
    int idx = l + new Random().nextInt(r - l + 1);   // 随机 pivot，防有序数组退化
    swap(a, idx, r);
    int pivot = a[r], i = l;
    for (int j = l; j < r; j++) {
        if (a[j] < pivot) swap(a, i++, j);
    }
    swap(a, i, r);          // i 是 pivot 的最终位置
    return i;
}

void quickSort(int[] a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

int partition(int[] a, int l, int r) {
    int idx = l + new Random().nextInt(r - l + 1);   // 随机 pivot，防有序数组退化
    swap(a, idx, r);
    int pivot = a[r], i = l;
    for (int j = l; j < r; j++) {
        if (a[j] < pivot) swap(a, i++, j);
    }
    swap(a, i, r);          // i 是 pivot 的最终位置
    return i;
}

易错点：返回 i 而不是 i-1；交换后 pivot 已在 i 位上。

6. 归并排序

java

void mergeSort(int[] a, int l, int r, int[] tmp) {
    if (l >= r) return;
    int m = (l + r) >>> 1;
    mergeSort(a, l, m, tmp);
    mergeSort(a, m + 1, r, tmp);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];  // <= 保证稳定
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    System.arraycopy(tmp, l, a, l, r - l + 1);
}

void mergeSort(int[] a, int l, int r, int[] tmp) {
    if (l >= r) return;
    int m = (l + r) >>> 1;
    mergeSort(a, l, m, tmp);
    mergeSort(a, m + 1, r, tmp);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];  // <= 保证稳定
    while (i <= m) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    System.arraycopy(tmp, l, a, l, r - l + 1);
}

易错点：<= 写成 < 就不稳定了；最后一行的区间长度是 r-l+1。

7. 二分（四个变体，背这四段就够）

java

// ① 找目标（存在返回下标）
int bs(int[] a, int t) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == t) return m;
        if (a[m] < t) l = m + 1; else r = m - 1;
    }
    return -1;
}

// ② 找左边界（第一个 >= t 的位置）
int lowerBound(int[] a, int t) {
    int l = 0, r = a.length;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] < t) l = m + 1; else r = m;
    }
    return l;
}

// ③ 找右边界（最后一个 <= t 的位置）=> lowerBound(t+1) - 1

// ④ 旋转数组找最小值
int findMin(int[] a) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] > a[r]) l = m + 1; else r = m;
    }
    return a[l];
}

// ① 找目标（存在返回下标）
int bs(int[] a, int t) {
    int l = 0, r = a.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == t) return m;
        if (a[m] < t) l = m + 1; else r = m - 1;
    }
    return -1;
}

// ② 找左边界（第一个 >= t 的位置）
int lowerBound(int[] a, int t) {
    int l = 0, r = a.length;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] < t) l = m + 1; else r = m;
    }
    return l;
}

// ③ 找右边界（最后一个 <= t 的位置）=> lowerBound(t+1) - 1

// ④ 旋转数组找最小值
int findMin(int[] a) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] > a[r]) l = m + 1; else r = m;
    }
    return a[l];
}

易错点：mid = (l+r)/2 在 l+r 溢出时出错，写 l + (r-l)/2；while (l < r) 还是 <= 取决于区间定义（左闭右开就别用 <=）。

8. 堆 / TopK

java

// 求第 K 大的元素（小顶堆，堆大小维持 K）
int findKthLargest(int[] a, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();  // 默认小顶堆
    for (int x : a) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();   // 弹掉最小的
    }
    return heap.peek();
}

// 求第 K 大的元素（小顶堆，堆大小维持 K）
int findKthLargest(int[] a, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();  // 默认小顶堆
    for (int x : a) {
        heap.offer(x);
        if (heap.size() > k) heap.poll();   // 弹掉最小的
    }
    return heap.peek();
}

易错点：求第 K 大用小顶堆（反直觉）；求中位数要两个堆。

9. 反转链表（迭代 + 递归）

java

// 迭代（首选，O(1) 空间）
ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;   // 先存 next
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;                    // 返回 prev，不是 cur
}

// 递归
ListNode reverseRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRec(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

// 迭代（首选，O(1) 空间）
ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;   // 先存 next
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;                    // 返回 prev，不是 cur
}

// 递归
ListNode reverseRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRec(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

易错点：返回 prev；递归版最后必须 head.next = null，否则成环。

10. 字符串：最长无重复子串

java

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int max = 0, left = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        Integer idx = last.get(c);
        if (idx != null && idx >= left) left = idx + 1;  // 只往右移，不能回退
        last.put(c, i);
        max = Math.max(max, i - left + 1);
    }
    return max;
}

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> last = new HashMap<>();
    int max = 0, left = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        Integer idx = last.get(c);
        if (idx != null && idx >= left) left = idx + 1;  // 只往右移，不能回退
        last.put(c, i);
        max = Math.max(max, i - left + 1);
    }
    return max;
}

易错点：idx >= left 这个判断不能少，否则 left 会往回跳。

11. 大数相加（字符串加法）

java

String add(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int x = i >= 0 ? a.charAt(i--) - '0' : 0;
        int y = j >= 0 ? b.charAt(j--) - '0' : 0;
        int sum = x + y + carry;
        sb.append(sum % 10);
        carry = sum / 10;
    }
    return sb.reverse().toString();
}

String add(String a, String b) {
    StringBuilder sb = new StringBuilder();
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    while (i >= 0 || j >= 0 || carry > 0) {
        int x = i >= 0 ? a.charAt(i--) - '0' : 0;
        int y = j >= 0 ? b.charAt(j--) - '0' : 0;
        int sum = x + y + carry;
        sb.append(sum % 10);
        carry = sum / 10;
    }
    return sb.reverse().toString();
}

易错点：循环条件要带 carry > 0，否则 99 + 1 会漏掉最高位的 1。

12. 限流（令牌桶，最常问）

java

class TokenBucket {
    private final int capacity;          // 桶容量
    private final double ratePerSec;     // 每秒补充
    private double tokens;
    private long lastRefillNanos;

    TokenBucket(int capacity, double ratePerSec) {
        this.capacity = capacity;
        this.ratePerSec = ratePerSec;
        this.tokens = capacity;
        this.lastRefillNanos = System.nanoTime();
    }

    synchronized boolean tryAcquire() {
        long now = System.nanoTime();
        double add = (now - lastRefillNanos) / 1e9 * ratePerSec;
        tokens = Math.min(capacity, tokens + add);
        lastRefillNanos = now;
        if (tokens >= 1) {
            tokens -= 1;
            return true;
        }
        return false;
    }
}

class TokenBucket {
    private final int capacity;          // 桶容量
    private final double ratePerSec;     // 每秒补充
    private double tokens;
    private long lastRefillNanos;

    TokenBucket(int capacity, double ratePerSec) {
        this.capacity = capacity;
        this.ratePerSec = ratePerSec;
        this.tokens = capacity;
        this.lastRefillNanos = System.nanoTime();
    }

    synchronized boolean tryAcquire() {
        long now = System.nanoTime();
        double add = (now - lastRefillNanos) / 1e9 * ratePerSec;
        tokens = Math.min(capacity, tokens + add);
        lastRefillNanos = now;
        if (tokens >= 1) {
            tokens -= 1;
            return true;
        }
        return false;
    }
}

易错点：必须先补充令牌再判断；tokens 要用 double，整数会丢精度。

现场手写检查表

写完（或写到一半卡住）时，按这个顺序自查：

[ ] 空输入 / 单元素 / 全是相同元素，会怎样？
[ ] 循环边界是 l < r 还是 l <= r，和我的区间定义一致吗？
[ ] 有没有可能数组越界（i-1 / i+1）？
[ ] 整数溢出（mid、sum、count）？
[ ] 返回值是 prev 还是 cur（链表）、i 还是 i-1（分区）？
[ ] 并发版本：while 还是 if？notify 还是 notifyAll？volatile 有吗？

面试官更在意「你能不能自己发现边界问题」，而不是一次写对。主动说「这里我要处理一下空数组」，比闷头写完更有分。

手写题清单 ​

怎么练 ​

1. 单例（三种，按推荐排序） ​

2. 生产者消费者（三种写法） ​

3. LRU 缓存（手写双向链表 + HashMap） ​

4. 线程池（简化版，能跑就行） ​

5. 快排（含随机 pivot） ​

6. 归并排序 ​

7. 二分（四个变体，背这四段就够） ​

8. 堆 / TopK ​

9. 反转链表（迭代 + 递归） ​

10. 字符串：最长无重复子串 ​

11. 大数相加（字符串加法） ​

12. 限流（令牌桶，最常问） ​

现场手写检查表 ​

手写题清单

怎么练

1. 单例（三种，按推荐排序）

2. 生产者消费者（三种写法）

3. LRU 缓存（手写双向链表 + HashMap）

4. 线程池（简化版，能跑就行）

5. 快排（含随机 pivot）

6. 归并排序

7. 二分（四个变体，背这四段就够）

8. 堆 / TopK

9. 反转链表（迭代 + 递归）

10. 字符串：最长无重复子串

11. 大数相加（字符串加法）

12. 限流（令牌桶，最常问）

现场手写检查表