百度后端开发工程师面试 · 手撕题 Top 20 题单

题目内容

给你单链表的头节点 head，将链表反转，返回反转后的头节点。追问升级：每 k 个节点一组进行翻转，不足 k 个的尾部保持原序（LC 25）。

思路解析

迭代法维护两个指针：prev 指向"已反转部分"的新头，curr 指向当前待处理节点。每一步先把 curr.next 暂存（否则断链后找不到后续），再把 curr.next 改指 prev，然后两个指针整体后移。走完一遍后 prev 就是新头。

K 个一组版本是它的直接升级：先向前走 k 步确认剩余节点够一组，够就反转这一组，反转后原来的组头变成了组尾，让它去接后续递归处理的结果；不够 k 个则按题意直接返回、不再翻转。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head
        while curr:
            nxt = curr.next      # 1. 暂存后继，防止断链
            curr.next = prev     # 2. 当前节点反向指向前驱
            prev = curr          # 3. prev 前进到当前节点
            curr = nxt           # 4. curr 前进到暂存的后继
        return prev              # prev 即反转后的头节点

    # ---- 追问：K 个一组翻转（LC 25）----
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        node = head
        for _ in range(k):       # 先探测剩余节点是否够 k 个
            if node is None:
                return head      # 不足 k 个：保持原序
            node = node.next
        prev, curr = None, head
        for _ in range(k):       # 反转这一组，写法同上
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        # 反转后 head 成为组尾，接上后续组的递归结果
        head.next = self.reverseKGroup(curr, k)
        return prev              # prev 是本组新头

题目内容

给定链表头节点 head，返回链表开始入环的第一个节点；若链表无环返回 None。要求空间 O(1)。

思路解析

第一步用快慢指针判环：慢指针每次走 1 步、快指针走 2 步，若有环必在环内相遇（无环则快指针先到终点）。第二步的数学推导是讲解核心：设头到环入口距离为 a，入口到相遇点为 b，环长为 L。相遇时 slow 走了 a+b，fast 走了 a+b+nL，又因 fast 速度是 slow 的两倍，得 2(a+b) = a+b+nL，即 a = nL − b。这意味着从 head 和从相遇点同时每次走一步，它们必然在环入口相遇（slow 再走 a 步相当于绕了整数圈）。

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:        # 第一步：判环
            slow = slow.next             # 慢指针走 1 步
            fast = fast.next.next        # 快指针走 2 步
            if slow is fast:             # 相遇，说明有环
                p = head                 # 第二步：找入口
                while p is not slow:     # 两点同速前进
                    p = p.next
                    slow = slow.next
                return p                 # 相遇点即环入口
        return None                      # fast 走到头：无环

题目内容

设计并实现 LRU（最近最少使用）缓存，支持 get(key) 与 put(key, value)，两者都必须是 O(1)；容量满时淘汰最久未使用的键。

思路解析

O(1) 查找需要哈希表，O(1) 维护"使用顺序"需要双向链表，两者合体即标准答案：哈希表存 key → 链表节点，双向链表按"最近使用"排序（头部最新、尾部最旧）。get 命中时把节点挪到头部；put 时已存在则更新值并挪到头部，否则新建节点插入头部，超容量就删除尾部节点并从哈希表同步移除。使用哑元头尾节点可以消掉所有空链表的边界判断，这是面试代码整洁度的关键。

class Node:
    __slots__ = ('key', 'val', 'prev', 'next')   # 存 key 是为了淘汰时能反查哈希表
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                             # key -> Node，O(1) 定位
        self.head, self.tail = Node(), Node()     # 哑元头尾，免去边界判断
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node: Node) -> None:        # 从链表中摘除节点 O(1)
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node: Node) -> None:    # 插到头部（最近使用）O(1)
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)                        # 命中：刷新为最近使用
        self._push_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:                       # 已存在：更新值并刷新位置
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._push_front(node)
            return
        if len(self.map) == self.cap:             # 满容量：淘汰尾部（最久未用）
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]                 # 哈希表同步删除
        node = Node(key, value)
        self.map[key] = node
        self._push_front(node)

深入：多线程场景怎么改造 LRU

先分层说清：单线程版为什么不线程安全

① 哈希表本身：Java 的 HashMap 并发 put 可能丢更新、破坏桶结构（JDK7 的 resize 死循环是经典八股），Python 的 dict 单次操作虽有 GIL 保护，但"查完再改"的组合操作照样有竞态；② 双向链表：_remove 和 _push_front 各是好几步指针改写，两个线程同时挪节点会把链表改断、改出环；③ 组合操作不原子：put 里"判容量 → 淘汰 → 插入"之间任何一步都可能被插队，可能超容量淘汰、可能淘汰掉刚插入的热点。三层任何一层都足以让答案不成立。

先排除一个常见错答：读写锁

很多人第一反应是"读多写少，上 ReadWriteLock"。但 LRU 的 get 要把节点挪到头部，本质是写操作——所有读都要拿写锁，ReadWriteLock 在这里提供不了任何读并发，反而多一层间接。面试时主动点破这一句，能直接和大多数候选人拉开差距。

方案一：全局锁（基线）

整把 synchronized 或 ReentrantLock 包住所有操作。正确、最简，但所有读写串行化，锁就是瓶颈。它的价值是当基线："先给对的，再谈快的"，然后引出方案二。

方案二：分段锁（面试最期待的答案）

把 key 哈希到 N 个段（取 2 的幂，位运算取模），每段是一个独立的小 LRU，自带一把锁，冲突面降到 1/N。代价是每段独立淘汰，全局 LRU 退化为"段内 LRU"：某段的热点可能被淘汰，而别的段的冷数据还活着——用精确性换并发。这正是 Guava Cache 的设计（也是 JDK7 ConcurrentHashMap 的分段思路）。段内实现直接借 LinkedHashMap(accessOrder=true) + 重写 removeEldestEntry，代码可以写得很短：

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;

/** 分段 LRU：key 哈希到 16 个段，每段独立小 LRU + 独立锁 */
public class ShardedLRUCache<K, V> {
    private static final int SEGMENTS = 16;                 // 2 的幂，位运算取模
    private final Segment<K, V>[] table;

    @SuppressWarnings("unchecked")
    public ShardedLRUCache(int capacity) {
        table = new Segment[SEGMENTS];
        int per = Math.max(1, capacity / SEGMENTS);         // 每段容量 = 总容量 / 段数
        for (int i = 0; i < SEGMENTS; i++) table[i] = new Segment<>(per);
    }

    private Segment<K, V> segmentFor(K key) {
        int h = key.hashCode();
        h ^= (h >>> 16);                       // 扰动高位，减少哈希碰撞（CHM 同款）
        return table[h & (SEGMENTS - 1)];
    }

    public V get(K key) { return segmentFor(key).get(key); }
    public void put(K key, V value) { segmentFor(key).put(key, value); }

    private static final class Segment<K, V> {
        private final ReentrantLock lock = new ReentrantLock();
        private final LinkedHashMap<K, V> map;

        Segment(int capacity) {
            // accessOrder=true：get 也会把条目移到"最近使用"一端
            map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capacity;   // 超容量自动淘汰最旧
                }
            };
        }

        V get(K key) {
            lock.lock();
            try { return map.get(key); }        // get 也改顺序，必须加锁（读写锁失效的原因）
            finally { lock.unlock(); }          // finally 解锁，防异常漏锁
        }

        void put(K key, V value) {
            lock.lock();
            try { map.put(key, value); }
            finally { lock.unlock(); }
        }
    }

    public static void main(String[] args) throws Exception {
        // 语义自检：找 3 个落在同一段的 key，验证段内 LRU 与 get 刷新
        ShardedLRUCache<Integer, Integer> small = new ShardedLRUCache<>(32); // 每段容量 2
        List<Integer> same = new ArrayList<>();
        for (int k = 0; same.size() < 3; k++) {
            if (same.isEmpty() || small.segmentFor(k) == small.segmentFor(same.get(0))) {
                same.add(k);
            }
        }
        int a = same.get(0), b = same.get(1), c = same.get(2);
        small.put(a, 1);
        small.put(b, 2);              // 段满
        small.get(a);                 // 刷新 a，顺序变为 b(旧) a(新)
        small.put(c, 3);              // 应淘汰最旧的 b
        if (small.get(b) != null) throw new AssertionError("应淘汰 b");
        if (small.get(a) == null || small.get(c) == null) throw new AssertionError("a、c 应存活");

        // 并发冒烟：4 线程各 1 万次 put/get，无异常无死锁即通过
        Thread[] ts = new Thread[4];
        for (int t = 0; t < 4; t++) {
            final int id = t;
            ts[t] = new Thread(() -> {
                for (int i = 0; i < 10000; i++) {
                    int k = id * 100000 + (i % 50);
                    small.put(k, i);
                    small.get(k);
                }
            });
        }
        for (Thread t : ts) t.start();
        for (Thread t : ts) t.join();
        System.out.println("ShardedLRU OK: 段内LRU语义 + 并发冒烟通过");
    }
}

口头追问预案：为什么段数取 2 的幂（位运算代替取模、均匀分布）；负载倾斜怎么办（承认 trade-off，或答"监控段负载、动态再哈希"，面试点到即可）；和 JDK7 ConcurrentHashMap 的 Segment 是什么关系（同源思想，JDK8 后 CHM 改用 CAS + synchronized 锁桶头，段的概念被弱化）。

方案三：ConcurrentHashMap + 近似 LRU（现代缓存的方向）

如果要求读路径完全无锁，就必须放弃"同步维护精确顺序"：数据放 ConcurrentHashMap，get 时只把"某 key 被访问了"这条事件写进每线程私有的环形缓冲（避免制造新的共享争用点）；由后台线程（或搭写操作的便车）批量回放事件、异步更新新鲜度；容量超限时按近似顺序淘汰。顺序最终一致、淘汰近似，换来读吞吐拉满。Caffeine 的读缓冲 + W-TinyLFU 就是这条路线的成熟形态——策略本身也从 LRU 进化到了 LFU 变体，命中率更高。面试里能说出"事件缓冲 + 异步维护 + 策略近似"三件套，就已经是资深答案。

Redis 的采样淘汰：另一种近似路线

Redis 干脆不维护 LRU 链表：每个 key 只带一个 24 位的空闲时间时钟，访问时零维护开销。超过 maxmemory 时随机采样 maxmemory-samples（默认 10）个 key，淘汰其中空闲最久的；3.0 之后又加了"淘汰池"——采样结果先进一个按空闲时间排序的小候选堆，再从池里挑最旧的淘汰，逼近真 LRU 的程度大幅提高（官方文档有对比图，10 个采样已非常接近理想 LRU）。

它和方案三是同一个 trade-off 的两种实现：不维护顺序，只记时间戳，在淘汰时近似。好处是多线程环境下完全没有全局共享的可变顺序结构，也就没有锁争用。

题目内容

给你二叉树的根节点 root，返回其节点值按层序遍历的结果（逐层从左到右）。追问：返回二叉树的右视图（每层最右侧节点）。

思路解析

层序遍历就是 BFS 在树上的应用，用队列实现。关键技巧是每轮循环开始时先用 size = len(q) 冻结当前层的节点数，因为遍历过程中还在不断往队列里加下一层的节点，不冻结就无法区分层的边界。右视图只是同一框架的微调：每层弹出到最后一个节点时记录答案。

from collections import deque

class Solution:
    def levelOrder(self, root):
        if not root:
            return []
        ans, q = [], deque([root])
        while q:
            size = len(q)              # 冻结本层节点数，划清层边界
            level = []
            for _ in range(size):
                node = q.popleft()
                level.append(node.val)
                if node.left:          # 下一层节点入队
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(level)
        return ans

    # ---- 追问：右视图（LC 199）----
    def rightSideView(self, root):
        if not root:
            return []
        ans, q = [], deque([root])
        while q:
            size = len(q)
            for i in range(size):
                node = q.popleft()
                if i == size - 1:      # 本层最后一个即右视图节点
                    ans.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
        return ans

题目内容

给定二叉树根节点 root，返回它的中序遍历结果（左 → 根 → 右）。面试官通常明确要求不用递归。

思路解析

递归版一行搞定，但迭代版考察的是对"系统栈"的模拟：用显式栈保存"一路向左"的路径。外层循环条件是"当前节点非空 或 栈非空"——只要还有一个没处理完就继续。内层循环把左链节点全部压栈，然后弹栈访问（此时它是当前最左的未访问节点），再转向它的右子树重复同样的过程。这个"压左链 → 弹出访问 → 转右"的三段节奏要能脱口而出。

class Solution:
    def inorderTraversal(self, root):
        ans, stack = [], []
        curr = root
        while curr or stack:           # 还有节点没处理完
            while curr:                # 1. 沿左链一路压栈
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()         # 2. 弹出：当前最左的未访问节点
            ans.append(curr.val)       #    访问它
            curr = curr.right          # 3. 转向右子树，重复过程
        return ans

题目内容

给定两个整数数组 preorder 和 inorder，其中 preorder 是前序遍历、inorder 是中序遍历（均无重复值），请构造二叉树并返回其根节点。

思路解析

抓住两个性质：前序的第一个元素一定是当前子树的根；中序序列中根的位置把序列切成左子树和右子树两部分。于是递归结构非常清晰：取前序首元素建根，在中序里定位它的下标 m，m 左边有 left_size = m - il 个节点属于左子树，据此就能在前序里切出左右子树对应的区间，递归下去。预处理一个"值 → 中序下标"的哈希表，把每次定位从 O(n) 降到 O(1)，是拿满分的关键优化。

class Solution:
    def buildTree(self, preorder, inorder):
        idx = {v: i for i, v in enumerate(inorder)}   # 值 -> 中序下标，O(1) 定位根

        def build(pl, pr, il, ir):     # 前序区间 [pl, pr]、中序区间 [il, ir]
            if pl > pr:
                return None            # 空区间
            root = TreeNode(preorder[pl])             # 前序首元素 = 根
            m = idx[preorder[pl]]                     # 根在中序的位置
            left_size = m - il                        # 左子树节点数
            # 前序中：根后面 left_size 个是左子树，剩下是右子树
            root.left  = build(pl + 1, pl + left_size, il, m - 1)
            root.right = build(pl + left_size + 1, pr, m + 1, ir)
            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 1)

题目内容

给定二叉树的根节点 root 和两个节点 p、q（均在树中），找到它们的最近公共祖先——一个节点也可以是它自己的祖先。

思路解析

后序递归，返回值定义为"以当前节点为根的子树里是否含有 p 或 q，若有则返回那个节点"。递归边界：节点为空或恰好等于 p/q，直接返回自身。拿到左右子树的结果后分三种情况：左右都非空说明 p、q 分居两侧，当前节点就是 LCA；只有一侧非空则答案在那一侧（LCA 可能是 p 或 q 本身）；都为空返回空。这个"返回值语义"要先讲清楚，代码只有几行。

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None or root is p or root is q:
            return root                # 空，或找到了 p/q：直接返回
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:             # p、q 分居左右两侧 -> 当前节点即 LCA
            return root
        return left if left else right # 都在同一侧；都空则返回 None

题目内容

给你一个整数数组 nums，将该数组升序排列。要求不使用库函数，面试官期待手写快排并分析复杂度（LC 912 的测试用例专门包含大量重复元素，朴素快排会超时）。

思路解析

快排 = 分治：选一个基准 pivot，把数组划分成"小于 pivot / 等于 pivot / 大于 pivot"三段，再递归排序小于和大于两段。两个工程细节能决定面试评价：随机选 pivot，避免有序输入退化成 O(n²)；三路划分（荷兰国旗），等于 pivot 的元素不再参与递归，大量重复数据时性能远好于双路划分。划分时注意 nums[i] > pivot 交换后 i 不能前进，因为换来的元素还没检查过。

import random

class Solution:
    def sortArray(self, nums):
        self.quick_sort(nums, 0, len(nums) - 1)
        return nums

    def quick_sort(self, nums, lo, hi):
        if lo >= hi:
            return
        # 1. 随机选基准并换到末尾，避免有序输入退化 O(n^2)
        p = random.randint(lo, hi)
        nums[p], nums[hi] = nums[hi], nums[p]
        pivot = nums[hi]
        # 2. 三路划分：[lo, lt) < pivot, [lt, i) == pivot, (gt, hi] > pivot
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1                # 换来的元素未检查，i 不前进
            else:
                i += 1                 # 等于 pivot：原地归入中段
        # 3. 递归排序两端，中段已就位
        self.quick_sort(nums, lo, lt - 1)
        self.quick_sort(nums, gt + 1, hi)

题目内容

给定整数数组 nums 和整数 k，返回数组中第 k 个最大的元素。要求时间复杂度优于完全排序。

思路解析

两条标准路线，面试中建议都写、并讲清适用场景。解法一：最小堆——维护一个大小恒为 k 的堆，堆顶就是第 k 大；每个元素进出堆各 O(log k)，总 O(n log k)。它的真正价值在于流式场景：数据不能一次性装入内存、或源源不断到来时，堆是唯一选择。解法二：快速选择——借用快排的划分，但只递归目标所在的一侧，平均 O(n)。第 k 大等价于升序下标 n−k。

# 解法一：最小堆（O(n log k)，流式/海量数据首选）
import heapq

class Solution:
    def findKthLargest(self, nums, k):
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:          # 堆大小超过 k 就弹掉最小的
                heapq.heappop(heap)    # 循环结束后堆顶即第 k 大
        return heap[0]

# 解法二：快速选择（平均 O(n)）
import random

class Solution:
    def findKthLargest(self, nums, k):
        target = len(nums) - k         # 第 k 大 = 升序第 n-k 位

        def select(lo, hi):
            p = random.randint(lo, hi)             # 随机基准防退化
            nums[p], nums[hi] = nums[hi], nums[p]
            pivot = nums[hi]
            i = lo                                 # i: 下一个 "< pivot" 的落点
            for j in range(lo, hi):
                if nums[j] < pivot:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
            nums[i], nums[hi] = nums[hi], nums[i]  # 基准归位到 i
            if i == target:
                return nums[i]
            if i < target:                         # 只递归包含目标的一侧
                return select(i + 1, hi)
            return select(lo, i - 1)

        return select(0, len(nums) - 1)

def majorityElement(nums):
    cand, cnt = 0, 0
    for x in nums:
        if cnt == 0:                 # 候选被消耗完，换人
            cand = x
        cnt += 1 if x == cand else -1
    return cand                      # 题目保证存在多数元素，否则需二次验证

题目内容

给你一个非递减整数数组 nums 和目标值 target，找出 target 在数组中的开始和结束位置；不存在则返回 [-1, -1]。要求 O(log n)。

思路解析

二分的难点从来不是思想而是边界。建议背一个语义清晰的模板：lower_bound(t) 返回"第一个 ≥ t 的下标"，区间采用左闭右开 [lo, hi)，循环条件 lo < hi，收缩时 hi = mid（不减一）、lo = mid + 1，循环结束时 lo == hi 就是答案位置。有了这一个函数，左右边界都能推出来：左边界 = lower_bound(target)；右边界 = lower_bound(target+1) − 1。同一模板还能直接解 x 的平方根（最后一个满足 mid² ≤ x 的 mid）。

class Solution:
    def searchRange(self, nums, target):
        def lower_bound(t):              # 第一个 >= t 的下标；不存在返回 len(nums)
            lo, hi = 0, len(nums)        # 左闭右开区间
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < t:
                    lo = mid + 1         # mid 不可能是答案
                else:
                    hi = mid             # mid 可能是答案，保留它
            return lo

        left = lower_bound(target)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]              # target 不存在
        right = lower_bound(target + 1) - 1   # 第一个 >= target+1 的前一个
        return [left, right]

# ---- 变体：LC 69 x 的平方根（最后一个满足 mid*mid <= x 的 mid）----
def mySqrt(x):
    lo, hi = 0, x                        # 闭区间写法对照
    while lo < hi:
        mid = (lo + hi + 1) // 2         # +1 防死锁：取右中位数
        if mid * mid <= x:
            lo = mid                     # mid 可能是答案，保留
        else:
            hi = mid - 1
    return lo

题目内容

给定两个正序（从小到大）数组 nums1 和 nums2，返回这两个数组合并后的中位数。要求时间复杂度 O(log(m+n))。

思路解析

不要真的去合并。核心思想是对较短数组做二分，找一个"切割位置"：把两个数组各自切成左右两半，再拼成总左半和总右半，使得①总左半的元素个数 = (m+n+1)/2；②总左半的所有元素 ≤ 总右半的所有元素。条件②只取决于四个边界值：A 左界 a_l、A 右界 a_r、B 左界 b_l、B 右界 b_r，要求 a_l ≤ b_r 且 b_l ≤ a_r。一旦切割合法，奇数个时中位数 = max(a_l, b_l)，偶数个时 = (max(a_l,b_l) + min(a_r,b_r))/2。a_l > b_r 说明 A 取多了，左移；否则右移。边界用 ±∞ 哨兵处理，避免下标越界。

class Solution:
    def findMedianSortedArrays(self, A, B):
        if len(A) > len(B):              # 保证在较短数组上二分，复杂度 O(log min(m,n))
            A, B = B, A
        n, m = len(A), len(B)
        half = (n + m + 1) // 2          # 总左半应有的元素数
        lo, hi = 0, n                    # i: A 放进左半的个数，二分它
        while lo <= hi:
            i = (lo + hi) // 2
            j = half - i                 # B 放进左半的个数由总数反推
            a_l = A[i - 1] if i > 0 else float('-inf')   # 哨兵：空的一侧视为无穷
            a_r = A[i] if i < n else float('inf')
            b_l = B[j - 1] if j > 0 else float('-inf')
            b_r = B[j] if j < m else float('inf')
            if a_l <= b_r and b_l <= a_r:                # 切割合法
                if (n + m) % 2 == 1:
                    return max(a_l, b_l)                 # 奇数：左半最大
                return (max(a_l, b_l) + min(a_r, b_r)) / 2
            if a_l > b_r:                                # A 左半取多了
                hi = i - 1
            else:                                        # A 左半取少了
                lo = i + 1

题目内容

给定字符串 s，找出其中不含有重复字符的最长子串的长度。

思路解析

滑动窗口模板题。窗口 [left, right] 内维持无重复：right 右移扩展窗口，遇到重复就把 left 收缩到重复字符上次出现位置的右侧。最优写法用哈希表记录每个字符最近出现的下标，left 可以跳跃式收缩（直接跳到 last[ch]+1），比逐个右移的集合写法更快也更优雅。注意一个细节：last[ch] 可能落在当前窗口左边（已经失效），所以要加 last[ch] >= left 的判断。

class Solution:
    def lengthOfLongestSubstring(self, s):
        last = {}                        # 字符 -> 最近出现的下标
        left = 0
        ans = 0
        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1      # 跳过重复字符（last[ch] < left 说明已失效）
            last[ch] = right             # 更新最近位置
            ans = max(ans, right - left + 1)   # 窗口长度 = right-left+1
        return ans

题目内容

给定整数数组 nums 和窗口大小 k，窗口从最左端滑动到最右端，每次移动一位，返回每个窗口位置的最大值。

思路解析

暴力每窗口 O(k) 共 O(nk)，用单调队列降到 O(n)：双端队列存下标，保持队头到队尾对应的值单调递减，队头永远是当前窗口最大值。每来一个新元素 x：把队尾所有 ≤ x 的元素弹出（它们被 x"压制"，在 x 出窗口前永远轮不到当最大值），再把 x 的下标入队；然后检查队头下标是否已滑出窗口，是则弹出。每个下标至多入队、出队一次，均摊 O(1)。

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums, k):
        dq = deque()                     # 存下标，对应值从队头到队尾单调递减
        ans = []
        for i, x in enumerate(nums):
            while dq and nums[dq[-1]] <= x:
                dq.pop()                 # 队尾不可能再当最大值，清除
            dq.append(i)                 # 当前元素入队
            if dq[0] <= i - k:
                dq.popleft()             # 队头下标已滑出窗口
            if i >= k - 1:               # 窗口已成型，记录答案
                ans.append(nums[dq[0]])
        return ans

题目内容

给定整数数组 nums，找到具有最大和的连续子数组（至少包含一个元素），返回其最大和。

思路解析

Kadane 算法。定义状态：以当前元素结尾的最大子数组和为 curr。对于新元素 x 只有两种选择——接在前一段后面（curr + x），或者另起一段（x），取较大者；全局答案 best 记录所有位置的 curr 最大值。之所以能 O(1) 空间，是因为 curr 只依赖前一个状态，无需存整个 dp 数组。讲的时候点破 DP 定义，是区分"背过"和"懂了"的关键。

class Solution:
    def maxSubArray(self, nums):
        best = curr = nums[0]            # 以当前元素结尾的最大子数组和
        for x in nums[1:]:
            curr = max(x, curr + x)      # 另起一段，或延续前一段
            best = max(best, curr)       # 更新全局最优
        return best

题目内容

数字 n 代表生成括号的对数，设计一个函数生成所有合法的括号组合。例如 n=3 时输出 ["((()))","(()())","(())()","()(())","()()()"]。

思路解析

回溯法逐个位置决定放 '(' 还是 ')'，剪枝条件是合法括号序列的两条铁律：左括号数量没到 n 就可以放左括号；右括号数量严格小于左括号数量时才能放右括号。这两条同时保证了过程中不非法、结束时恰好各 n 个。回溯模板"选择 → 递归 → 撤销"要写标准：path 用列表追加再弹出，避免字符串拼接产生大量副本。

class Solution:
    def generateParenthesis(self, n):
        ans = []

        def dfs(path, open_cnt, close_cnt):
            if len(path) == 2 * n:           # 长度够了，收集答案
                ans.append(''.join(path))
                return
            if open_cnt < n:                 # 剪枝1：左括号还有剩
                path.append('(')
                dfs(path, open_cnt + 1, close_cnt)
                path.pop()                   # 撤销选择（回溯）
            if close_cnt < open_cnt:         # 剪枝2：右括号不能多于左括号
                path.append(')')
                dfs(path, open_cnt, close_cnt + 1)
                path.pop()

        dfs([], 0, 0)
        return ans

题目内容

给定两个以字符串形式表示的非负整数 num1 和 num2，返回它们的乘积（同样以字符串表示）。禁止转成整数直接相乘。

思路解析

模拟竖式乘法，但用数组统一处理进位更优雅。核心观察：num1[i] × num2[j] 的乘积最多影响结果数组的两个位置：i+j（进位位）和 i+j+1（本位），且两个位置都 ≤ m+n−1，所以 m 位 × n 位的积最多 m+n 位，开 m+n 长度的数组即可。从低位往高位逐对相乘，把结果叠加到对应位置：个位留在 p2，进位累加到 p1（累加而非赋值，因为多个乘积会落在同一位）。最后去掉前导零拼成字符串。

class Solution:
    def multiply(self, num1, num2):
        if num1 == "0" or num2 == "0":       # 特判，避免结果剩前导零
            return "0"
        m, n = len(num1), len(num2)
        res = [0] * (m + n)                  # 乘积最多 m+n 位
        for i in range(m - 1, -1, -1):       # 从低位开始模拟竖式
            for j in range(n - 1, -1, -1):
                mul = int(num1[i]) * int(num2[j])
                p1, p2 = i + j, i + j + 1    # 乘积影响的两个位置
                total = mul + res[p2]        # 叠加该位已有值
                res[p2] = total % 10         # 本位留个位
                res[p1] += total // 10       # 进位累加到高位（注意是 +=）
        s = ''.join(str(d) for d in res).lstrip('0')   # 去前导零
        return s if s else "0"

题目内容

实现一个有界缓冲区：生产者线程在缓冲区满时阻塞，消费者线程在缓冲区空时阻塞，要求线程安全。

思路解析

三种写法体现递进理解：写法一 wait/notify——synchronized 块内用 while 循环判断条件（防虚假唤醒与条件失效），条件不满足就 wait 释放锁，操作后 notifyAll。写法二 BlockingQueue——生产级首选，put/take 自带阻塞，说明"真实项目优先用 JUC 组件"的工程意识。写法三 Lock + Condition——两个条件队列 notFull/notEmpty 分别挂生产者和消费者，signal 精确唤醒，避免 notifyAll 的无效唤醒，是最能体现功底的一版。

// 写法一：synchronized + wait/notify（面试白板首选，最短最完整）
import java.util.LinkedList;
import java.util.Queue;

public class ProducerConsumer {
    private final Queue<Integer> buffer = new LinkedList<>();
    private final int capacity;

    public ProducerConsumer(int capacity) { this.capacity = capacity; }

    public synchronized void produce(int item) throws InterruptedException {
        while (buffer.size() == capacity) {  // 必须 while：防虚假唤醒/条件被抢先改变
            wait();                          // 满：释放锁并挂起
        }
        buffer.offer(item);
        notifyAll();                         // 有数据了，唤醒消费者
    }

    public synchronized int consume() throws InterruptedException {
        while (buffer.isEmpty()) {
            wait();                          // 空：释放锁并挂起
        }
        int item = buffer.poll();
        notifyAll();                         // 有空位了，唤醒生产者
        return item;
    }
}

// 写法二：BlockingQueue（生产代码首选，一句"面试时优先这版"很加分）
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

public class ProducerConsumerV2 {
    public static void main(String[] args) {
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(5); // 有界，自带阻塞
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                try { queue.put(i); }          // 满时自动阻塞
                catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            }
        }, "producer").start();
        new Thread(() -> {
            for (int i = 0; i < 10; i++) {
                try { System.out.println("take " + queue.take()); }  // 空时自动阻塞
                catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            }
        }, "consumer").start();
    }
}

// 写法三：ReentrantLock + 双 Condition（精确唤醒，功底版）
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

public class ProducerConsumerV3 {
    private final Queue<Integer> buffer = new LinkedList<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull  = lock.newCondition();  // 生产者等"不满"
    private final Condition notEmpty = lock.newCondition();  // 消费者等"不空"

    public ProducerConsumerV3(int capacity) { this.capacity = capacity; }

    public void produce(int item) throws InterruptedException {
        lock.lock();
        try {
            while (buffer.size() == capacity) notFull.await();
            buffer.offer(item);
            notEmpty.signal();                 // 只唤醒消费者，无无效唤醒
        } finally {
            lock.unlock();                     // finally 里解锁，防异常泄漏锁
        }
    }

    public int consume() throws InterruptedException {
        lock.lock();
        try {
            while (buffer.isEmpty()) notEmpty.await();
            int item = buffer.poll();
            notFull.signal();                  // 只唤醒生产者
            return item;
        } finally {
            lock.unlock();
        }
    }
}

深入：消费者批量刷写（Batch Flush，size + time 双触发）

题面

生产者持续产生数据，消费者不逐条处理，而是攒批刷写（数据库批量插入、日志批量落盘、批量上报）：攒满 N 条就刷，或者距上次刷写超过 T 毫秒就刷，两者先到先触发；关停时要把剩余数据刷完，一条不丢。

三个设计点，讲清楚再写码

① 批量取用 drainTo：消费者先 poll(timeout) 等到第一条，再 drainTo(batch, 剩余额度) 一次性把队列里现成的都捞走——比循环 poll 快，且天然"有多少拿多少"；② 双触发：size 满立即刷（吞吐优先），time 到也刷（延迟有界），计时用 nanoTime（单调钟，不受系统改时间影响，currentTimeMillis 可能回跳）；③ 关停排空 + 背压：有界队列满时 put 阻塞生产者，就是天然背压；close 只置标志位不 interrupt，让 worker 把队列和缓冲都排空后优雅退出。

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.TimeUnit;
import java.util.function.Consumer;

/** 批量刷写器：size + time 双触发，关停排空（Kafka batch.size + linger.ms 同款思想） */
public class BatchFlusher<T> implements AutoCloseable {
    private final BlockingQueue<T> queue;              // 有界队列：满时 put 阻塞 = 天然背压
    private final List<T> batch = new ArrayList<>();   // 消费者私有缓冲，单线程访问无需加锁
    private final int batchSize;
    private final long intervalNanos;
    private final Consumer<List<T>> sink;             // 刷写回调（批量插入/落盘/上报）
    private final Thread worker;
    private volatile boolean closed = false;

    public BatchFlusher(int batchSize, long intervalMs, int queueCap, Consumer<List<T>> sink) {
        this.batchSize = batchSize;
        this.intervalNanos = TimeUnit.MILLISECONDS.toNanos(intervalMs);
        this.queue = new ArrayBlockingQueue<>(queueCap);
        this.sink = sink;
        this.worker = new Thread(this::loop, "batch-flusher");
        this.worker.start();
    }

    /** 生产端：入队即返回，仅队列满时阻塞（背压） */
    public void submit(T item) throws InterruptedException {
        if (closed) throw new IllegalStateException("flusher closed");
        queue.put(item);
    }

    private void loop() {
        long nextFlushAt = System.nanoTime() + intervalNanos;   // 单调钟计时，防时钟回跳
        while (true) {
            try {
                // 等第一条，超时 = 距截止剩余时间；超时返回 null 走时间触发
                T head = queue.poll(Math.max(nextFlushAt - System.nanoTime(), 0), TimeUnit.NANOSECONDS);
                if (head != null) {
                    batch.add(head);
                    queue.drainTo(batch, batchSize - batch.size());  // 批量取是核心：一次捞走现成的
                }
                boolean sizeUp  = batch.size() >= batchSize;        // 触发1：攒满
                boolean timeUp  = System.nanoTime() >= nextFlushAt; // 触发2：到点
                boolean closing = closed && queue.isEmpty();        // 关停排空：有多少刷多少
                if (sizeUp || timeUp || (closing && !batch.isEmpty())) {
                    if (!batch.isEmpty()) {
                        List<T> toFlush = new ArrayList<>(batch);   // 传副本：sink 可能异步持有
                        batch.clear();
                        sink.accept(toFlush);
                    }
                    nextFlushAt = System.nanoTime() + intervalNanos;
                }
                if (closing && batch.isEmpty()) return;   // 排空完毕，优雅退出
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                if (!batch.isEmpty()) sink.accept(batch); // 被中断也不丢数据
                return;
            }
        }
    }

    @Override
    public void close() {
        closed = true;                          // 不 interrupt：让 worker 自然排空
        try { worker.join(3000); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
    }

    public static void main(String[] args) throws Exception {
        List<Integer> flushed = new ArrayList<>();
        List<Integer> sizes = new ArrayList<>();
        Object lock = new Object();
        BatchFlusher<Integer> f = new BatchFlusher<>(10, 150, 100, list -> {
            synchronized (lock) { sizes.add(list.size()); flushed.addAll(list); }
        });

        // 场景1：连发 25 条 -> 应按 10/10 触发 size 刷写，余 5 条靠后续触发
        for (int i = 0; i < 25; i++) f.submit(i);
        // 场景2：再发 3 条不满批 -> 靠 time 触发或关停排空刷出
        Thread.sleep(50);
        for (int i = 100; i < 103; i++) f.submit(i);
        f.close();

        synchronized (lock) {
            if (flushed.size() != 28) throw new AssertionError("丢数据: " + flushed.size());
            for (int s : sizes) if (s < 1 || s > 10) throw new AssertionError("批大小越界: " + s);
            System.out.println("BatchFlusher OK: 各批大小=" + sizes + "，共刷 " + flushed.size() + " 条，无丢失");
        }
    }
}

口头追问预案：① 为什么用单消费者线程（保序、实现简单；要多并发就按 key 分片多实例，顺序在片内保证——呼应 Q3 深入里的分段思想）；② sink 刷写失败怎么办（重试 + 失败进死信队列 / 落本地 WAL，业务侧做幂等）；③ 传给 sink 为什么是副本（sink 若异步消费，原缓冲被 clear 会踩数据）；④ 和 Q20 线程池的区别（线程池是"任务并行执行"，批量刷写是"数据攒批串行落盘"，一个是执行器一个是缓冲管道）。

题目内容

三个线程分别打印 A、B、C，要求按 A→B→C 的顺序循环打印 10 轮（输出 "ABCABC...ABC"）。

思路解析

本质是"令牌在线程间传递"。用三个 Semaphore 各代表一个线程的执行权：初始只有 A 的令牌为 1，B、C 为 0。每个线程的循环逻辑完全一致：acquire 自己的令牌 → 打印 → release 下一个线程的令牌。令牌传递天然形成环形顺序，不需要共享状态变量，也不会虚假唤醒，是这道题最干净的解法。对照写法：synchronized + state + wait/notifyAll（每轮所有人被唤醒、只有 state 匹配者继续），代码更长且有无用唤醒。

import java.util.concurrent.Semaphore;

public class TurnPrinter {
    // 三个令牌：初始只有 A 持有（permits=1），B、C 等待（permits=0）
    private static final Semaphore SA = new Semaphore(1);
    private static final Semaphore SB = new Semaphore(0);
    private static final Semaphore SC = new Semaphore(0);

    public static void main(String[] args) {
        // 每个线程：等自己的令牌 -> 打印 -> 把令牌交给下一个（A->B->C->A 环形）
        new Thread(() -> print(SA, SB, 'A'), "T-A").start();
        new Thread(() -> print(SB, SC, 'B'), "T-B").start();
        new Thread(() -> print(SC, SA, 'C'), "T-C").start();
    }

    private static void print(Semaphore self, Semaphore next, char c) {
        for (int i = 0; i < 10; i++) {
            try {
                self.acquire();        // 等待上一个线程交出令牌
                System.out.print(c);
                next.release();        // 交给下一个线程
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                return;
            }
        }
    }
}

题目内容

手写一个线程安全的单例类，并解释每一行的作用。

思路解析

标准答案是 DCL（Double-Checked Locking），得分点全在细节：第一次判空让已初始化后直接返回、不碰锁（快路径）；synchronized 块内第二次判空防止多个线程同时通过第一关后重复创建；volatile 是灵魂——new 实际分三步（分配内存 → 初始化对象 → 引用指向内存），无 volatile 时指令重排可能让别的线程拿到"已分配但未初始化"的对象。另外给出静态内部类（懒加载且线程安全，靠类加载机制）和枚举（最强，防反射防序列化）两个替代方案，展示知识面。

public class Singleton {
    // volatile 必加：禁止 new 的三步操作（分配内存/初始化/赋引用）重排序，
    // 否则其他线程可能拿到未初始化完成的对象
    private static volatile Singleton instance;

    private Singleton() {}               // 私有构造：禁止外部 new

    public static Singleton getInstance() {
        if (instance == null) {          // 第一次检查：快路径，避免每次加锁
            synchronized (Singleton.class) {
                if (instance == null) {  // 第二次检查：防止并发重复创建
                    instance = new Singleton();
                }
            }
        }
        return instance;
    }
}

// 替代方案一：静态内部类（推荐，懒加载 + 线程安全，利用类加载锁）
class SingletonHolder {
    private SingletonHolder() {}
    private static class Holder {        // 内部类只在首次被引用时加载
        private static final SingletonHolder INSTANCE = new SingletonHolder();
    }
    public static SingletonHolder getInstance() { return Holder.INSTANCE; }
}

// 替代方案二：枚举（《Effective Java》推荐，天然防反射、防序列化破坏）
enum SingletonEnum { INSTANCE }

题目内容

实现一个简化版线程池：固定数量的工作线程从一个任务队列中取任务执行；支持 execute 提交任务、shutdown 停止。

思路解析

线程池的本质非常朴素：工作线程 = 一个死循环，不断从阻塞队列 take 任务并 run；提交任务 = 往阻塞队列 put。阻塞队列同时解决了"无任务时线程挂起等待"和"多生产者多消费者的线程安全"两个问题。shutdown 用 volatile 标志位 + interrupt 打破 take 的阻塞，被唤醒的 worker 先把队列剩余任务排空再退出，不丢任务。写完要能对照说出 JDK ThreadPoolExecutor 的执行流程：核心线程未满 → 建核心线程；核心满 → 进队列；队列满 → 建非核心线程（到 maximumPoolSize）；都满 → 拒绝策略。七大参数（corePoolSize、maximumPoolSize、keepAliveTime、unit、workQueue、threadFactory、handler）要报得出来。

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

/** 简易线程池：worker 循环从任务队列取任务执行 */
public class MiniThreadPool {
    private final BlockingQueue<Runnable> taskQueue;
    private final List<Thread> workers = new ArrayList<>();
    private volatile boolean shutdown = false;     // volatile：所有线程立即可见

    public MiniThreadPool(int poolSize, int queueCapacity) {
        this.taskQueue = new LinkedBlockingQueue<>(queueCapacity);
        for (int i = 0; i < poolSize; i++) {
            Thread worker = new Thread(() -> {
                while (true) {
                    try {
                        Runnable task = taskQueue.take();   // 无任务：阻塞等待
                        task.run();                         // 执行任务（注意不是 start）
                    } catch (InterruptedException e) {
                        if (shutdown) {                       // 关停信号：排空剩余任务再退出
                            Runnable rest;
                            while ((rest = taskQueue.poll()) != null) rest.run();
                            return;
                        }
                        Thread.currentThread().interrupt();   // 非关停中断：恢复标志
                        return;
                    }
                }
            }, "mini-pool-worker-" + i);
            worker.start();
            workers.add(worker);
        }
    }

    public void execute(Runnable task) {
        if (shutdown) throw new IllegalStateException("pool already shut down");
        try {
            taskQueue.put(task);                            // 队列满：阻塞提交者（拒绝策略的简化版）
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    public void shutdown() {                                // 简化版：实际还应等队列排空
        shutdown = true;
        for (Thread w : workers) w.interrupt();             // 打断 take 阻塞，让 worker 退出
    }

    public static void main(String[] args) {
        MiniThreadPool pool = new MiniThreadPool(3, 10);
        for (int i = 0; i < 8; i++) {
            final int id = i;
            pool.execute(() ->
                System.out.println(Thread.currentThread().getName() + " run task-" + id));
        }
        pool.shutdown();
    }
}