面试速查:核心数据结构手写

面试速查:核心数据结构手写

Hello,我是小兔大白糖。 这篇整理面试口述与高频追问要点,方便对照站内同主题通识文。


正文

面向岗位:大型加密货币交易所 Senior Backend Developer - Risk 考察目标: Coding Interview 中高频出现的 6 大核心数据结构,要求能白板手写、可运行、能说清 trade-off。


目录

  1. LRU Cache
  2. LFU Cache
  3. Bloom Filter
  4. Consistent Hash
  5. Token Bucket
  6. Timing Wheel
  7. 面试现场建议
  8. 常见追问应对

1. LRU Cache

Concept

LRU (Least Recently Used):当 cache 满时,淘汰最久未被访问的 key。核心思想是"时间局部性"——最近被访问的数据很可能再次被访问。

Analogy:就像书桌上只能放 5 本书,新拿一本上来就把最底下那本(最久没看)抽掉。

Python Implementation

"""
LRU Cache - Python implementation using OrderedDict.
Time: get/put O(1), Space O(capacity)
"""
from collections import OrderedDict
 
 
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()  # key -> value, ordered by access time
 
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]
 
    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Pop first (least recently used)
            self.cache.popitem(last=False)
 
    def __repr__(self):
        return f"LRUCache({list(self.cache.items())})"
 
 
# ===================== 测试代码 =====================
def test_lru_cache():
    cache = LRUCache(2)
    cache.put(1, 10)
    cache.put(2, 20)
    assert cache.get(1) == 10  # 1 becomes MRU
    cache.put(3, 30)           # evicts key 2
    assert cache.get(2) == -1  # 2 is evicted
    assert cache.get(3) == 30
    cache.put(4, 40)           # evicts key 1
    assert cache.get(1) == -1
    assert cache.get(3) == 30
    assert cache.get(4) == 40
    print("All LRU Cache tests passed!")
    print(cache)
 
 
if __name__ == "__main__":
    test_lru_cache()

Java Implementation

import java.util.LinkedHashMap;
import java.util.Map;
 
/**
 * LRU Cache - Java implementation using LinkedHashMap.
 * accessOrder=true makes it order by access time (get/put).
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder=true
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
 
    // ===================== 测试代码 =====================
    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = new LRUCache<>(2);
        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println(cache.get(1)); // 10, 1 becomes MRU
        cache.put(3, 30);                 // evicts key 2
        System.out.println(cache.get(2)); // null (evicted)
        System.out.println(cache.get(3)); // 30
        cache.put(4, 40);                 // evicts key 1
        System.out.println(cache.get(1)); // null
        System.out.println(cache.get(3)); // 30
        System.out.println(cache.get(4)); // 40
        System.out.println("Cache contents: " + cache);
    }
}

Complexity Analysis

OperationTimeSpace
getO(1)O(capacity)
putO(1)O(capacity)

手写实现要点:如果不让用 LinkedHashMap/OrderedDict,需要手写 HashMap + Doubly Linked List。HashMap 存 key -> Node 的映射,Double Linked List 维护访问顺序。

大型加密货币交易所 / Risk 实际应用

  • Risk Feature Local Cache:风控规则引擎在本地缓存热点用户的风控特征(如近 24h 交易笔数),减少 Redis 往返。
  • Order Book Snapshot Cache:交易引擎缓存最近几档 order book snapshot,LRU 淘汰冷 snapshot。
  • ** sanctions List 查询结果缓存**:制裁名单 API 返回结果缓存在本地,避免重复调用外部服务。

2. LFU Cache

Concept

LFU (Least Frequently Used):当 cache 满时,淘汰访问频率最低的 key。如果频率相同,淘汰最老的。核心思想是"频率局部性"——被频繁访问的数据更重要。

Analogy:图书馆书架只有 5 个位置,每次把被借次数最少的书下架。

Python Implementation

"""
LFU Cache - Python implementation.
Time: get/put O(1), Space O(capacity)
"""
from collections import defaultdict
 
 
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.freq = 1
        self.prev = None
        self.next = None
 
 
class DLinkedList:
    """Double linked list with dummy head/tail."""
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
 
    def append(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1
 
    def pop(self, node=None):
        if self.size == 0:
            return None
        if not node:
            node = self.tail.prev
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node
 
 
class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.size = 0
        self.min_freq = 0
        self.key_map = {}           # key -> Node
        self.freq_map = defaultdict(DLinkedList)  # freq -> DLinkedList
 
    def get(self, key: int) -> int:
        if key not in self.key_map:
            return -1
        node = self.key_map[key]
        self._update(node)
        return node.val
 
    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_map:
            node = self.key_map[key]
            node.val = value
            self._update(node)
            return
 
        if self.size >= self.capacity:
            # Evict LFU (tail of min_freq list)
            evicted = self.freq_map[self.min_freq].pop()
            del self.key_map[evicted.key]
            self.size -= 1
 
        node = Node(key, value)
        self.key_map[key] = node
        self.freq_map[1].append(node)
        self.min_freq = 1
        self.size += 1
 
    def _update(self, node):
        """Move node from freq list to freq+1 list."""
        freq = node.freq
        self.freq_map[freq].pop(node)
        if self.min_freq == freq and self.freq_map[freq].size == 0:
            self.min_freq += 1
        node.freq += 1
        self.freq_map[node.freq].append(node)
 
 
# ===================== 测试代码 =====================
def test_lfu_cache():
    cache = LFUCache(2)
    cache.put(1, 10)
    cache.put(2, 20)
    assert cache.get(1) == 10    # freq(1)=2
    cache.put(3, 30)             # evicts key 2 (freq=1)
    assert cache.get(2) == -1
    assert cache.get(3) == 30    # freq(3)=2
    cache.put(4, 40)             # evicts key 1 or 3? Both freq=2, evict older (key 1)
    assert cache.get(1) == -1
    assert cache.get(3) == 30
    assert cache.get(4) == 40
    print("All LFU Cache tests passed!")
 
 
if __name__ == "__main__":
    test_lfu_cache()

Java Implementation

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
 
/**
 * LFU Cache - Java implementation using HashMap + LinkedHashSet per frequency.
 * All operations O(1).
 */
public class LFUCache {
    private final int capacity;
    private int minFreq;
    private int size;
    // key -> {value, freq}
    private final Map<Integer, Node> keyMap;
    // freq -> set of keys (insertion order = eviction order)
    private final Map<Integer, LinkedHashSet<Integer>> freqMap;
 
    private static class Node {
        int val;
        int freq;
        Node(int val) {
            this.val = val;
            this.freq = 1;
        }
    }
 
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.size = 0;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
    }
 
    public int get(int key) {
        if (!keyMap.containsKey(key)) return -1;
        Node node = keyMap.get(key);
        updateFreq(key, node);
        return node.val;
    }
 
    public void put(int key, int value) {
        if (capacity == 0) return;
        if (keyMap.containsKey(key)) {
            Node node = keyMap.get(key);
            node.val = value;
            updateFreq(key, node);
            return;
        }
        if (size >= capacity) {
            evictLFU();
        }
        Node node = new Node(value);
        keyMap.put(key, node);
        freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
        size++;
    }
 
    private void updateFreq(int key, Node node) {
        int freq = node.freq;
        freqMap.get(freq).remove(key);
        if (freq == minFreq && freqMap.get(freq).isEmpty()) {
            minFreq++;
        }
        node.freq++;
        freqMap.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(key);
    }
 
    private void evictLFU() {
        LinkedHashSet<Integer> set = freqMap.get(minFreq);
        int keyToEvict = set.iterator().next();
        set.remove(keyToEvict);
        keyMap.remove(keyToEvict);
        size--;
    }
 
    // ===================== 测试代码 =====================
    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1, 10);
        cache.put(2, 20);
        System.out.println(cache.get(1)); // 10
        cache.put(3, 30);                 // evicts key 2
        System.out.println(cache.get(2)); // -1
        System.out.println(cache.get(3)); // 30
        cache.put(4, 40);                 // evicts key 1
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 30
        System.out.println(cache.get(4)); // 40
        System.out.println("LFU Cache tests passed!");
    }
}

Complexity Analysis

OperationTimeSpace
getO(1)O(capacity)
putO(1)O(capacity)

核心设计:key_map 定位节点,freq_map[f] 存储频率为 f 的所有节点(用 DLinkedList 或 LinkedHashSet 保持插入顺序),min_freq 记录当前最小频率用于 O(1) 淘汰。

大型加密货币交易所 / Risk 实际应用

  • Risk Rule Result Cache:高频触发的风控规则(如"大额提币检查")结果缓存,低频规则自然淘汰,避免 Redis 压力。
  • Hot Wallet Address Cache:热钱包地址被高频查询,冷地址自动淘汰。
  • API Response Cache for Internal Services:内部微服务间调用,缓存高频查询的 response。

3. Bloom Filter

Concept

Bloom Filter 是一个概率型数据结构,用于判断"一个元素是否可能属于某个集合"。可能误判(false positive),但绝不会漏判(false negative)。

Analogy:就像酒店前台的黑名单系统,一查"这人可能在黑名单上"就报警,但如果系统说"不在",那一定不在。

Python Implementation

"""
Bloom Filter - Python implementation using multiple hash functions.
Space efficient probabilistic membership test.
"""
import hashlib
import math
import mmh3  # pip install mmh3; fallback to hashlib if not available
 
 
class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float):
        """
        expected_items: 预期插入元素数量
        false_positive_rate: 可接受的误判率 (如 0.01 = 1%)
        """
        self.size = self._optimal_size(expected_items, false_positive_rate)
        self.hash_count = self._optimal_hash_count(self.size, expected_items)
        self.bit_array = [0] * self.size
        self.item_count = 0
 
    @staticmethod
    def _optimal_size(n, p):
        m = - (n * math.log(p)) / (math.log(2) ** 2)
        return int(m)
 
    @staticmethod
    def _optimal_hash_count(m, n):
        k = (m / n) * math.log(2)
        return int(k)
 
    def _hashes(self, item: str):
        """Generate k hash values using double hashing."""
        h1 = mmh3.hash(item, 0) % self.size
        h2 = mmh3.hash(item, 1) % self.size
        for i in range(self.hash_count):
            yield (h1 + i * h2) % self.size
 
    def add(self, item: str):
        for idx in self._hashes(item):
            self.bit_array[idx] = 1
        self.item_count += 1
 
    def __contains__(self, item: str) -> bool:
        return all(self.bit_array[idx] == 1 for idx in self._hashes(item))
 
    def current_false_positive_rate(self) -> float:
        return (1 - math.exp(-self.hash_count * self.item_count / self.size)) ** self.hash_count
 
 
# ===================== 测试代码 =====================
def test_bloom_filter():
    bf = BloomFilter(expected_items=10000, false_positive_rate=0.01)
 
    # Add some items
    for i in range(1000):
        bf.add(f"user_{i}")
 
    # Check membership
    assert "user_5" in bf
    assert "user_999" in bf
    assert "user_not_exist" not in bf  # May be false positive!
 
    # False positive test
    fp_count = 0
    test_size = 10000
    for i in range(test_size):
        if f"nonexistent_{i}" in bf:
            fp_count += 1
 
    print(f"Items added: {bf.item_count}")
    print(f"Bit array size: {bf.size}")
    print(f"Hash functions: {bf.hash_count}")
    print(f"False positives: {fp_count}/{test_size} = {fp_count/test_size:.4f}")
    print(f"Expected FP rate: {bf.current_false_positive_rate():.4f}")
 
 
if __name__ == "__main__":
    test_bloom_filter()

Java Implementation

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
 
/**
 * Bloom Filter - Java implementation.
 * Uses MD5 for multiple hash functions (double hashing technique).
 */
public class BloomFilter {
    private final BitSet bitSet;
    private final int bitSize;
    private final int hashCount;
    private int itemCount;
 
    public BloomFilter(int expectedItems, double falsePositiveRate) {
        this.bitSize = optimalSize(expectedItems, falsePositiveRate);
        this.hashCount = optimalHashCount(bitSize, expectedItems);
        this.bitSet = new BitSet(bitSize);
        this.itemCount = 0;
    }
 
    private int optimalSize(int n, double p) {
        return (int) (-(n * Math.log(p)) / (Math.log(2) * Math.log(2)));
    }
 
    private int optimalHashCount(int m, int n) {
        return (int) ((m / (double) n) * Math.log(2));
    }
 
    public void add(String item) {
        int[] hashes = getHashes(item);
        for (int hash : hashes) {
            bitSet.set(Math.abs(hash % bitSize), true);
        }
        itemCount++;
    }
 
    public boolean mightContain(String item) {
        int[] hashes = getHashes(item);
        for (int hash : hashes) {
            if (!bitSet.get(Math.abs(hash % bitSize))) {
                return false;
            }
        }
        return true; // May be false positive!
    }
 
    private int[] getHashes(String item) {
        int[] result = new int[hashCount];
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(item.getBytes(StandardCharsets.UTF_8));
            int h1 = bytesToInt(digest, 0);
            int h2 = bytesToInt(digest, 4);
            for (int i = 0; i < hashCount; i++) {
                result[i] = h1 + i * h2;
            }
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
        return result;
    }
 
    private int bytesToInt(byte[] bytes, int offset) {
        return ((bytes[offset] & 0xFF) << 24) |
               ((bytes[offset + 1] & 0xFF) << 16) |
               ((bytes[offset + 2] & 0xFF) << 8) |
               (bytes[offset + 3] & 0xFF);
    }
 
    // ===================== 测试代码 =====================
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(10000, 0.01);
 
        for (int i = 0; i < 1000; i++) {
            bf.add("user_" + i);
        }
 
        System.out.println(bf.mightContain("user_5"));    // true
        System.out.println(bf.mightContain("user_999"));  // true
        System.out.println(bf.mightContain("not_exist")); // false (probably)
 
        // False positive test
        int fp = 0;
        int testSize = 10000;
        for (int i = 0; i < testSize; i++) {
            if (bf.mightContain("nonexistent_" + i)) fp++;
        }
        System.out.println("False positives: " + fp + "/" + testSize);
        System.out.println("Bit size: " + bf.bitSize + ", Hash count: " + bf.hashCount);
    }
}

Complexity Analysis

OperationTimeSpace
addO(k) ~ O(1) (k = hash count, typically 3-7)O(m) bits
mightContainO(k) ~ O(1)O(m) bits

空间效率公式:对于 n 个元素、误判率 p,最优 bit 数组大小 m = -n * ln(p) / (ln2)^2,最优 hash 函数数量 k = m/n * ln2。 例如:n=100万, p=1% 时,只需约 1.14MB。

大型加密货币交易所 / Risk 实际应用

  • Sanctions List Pre-Filter:OFAC / UN 制裁名单预过滤。Bloom Filter 放在 API Gateway 层,快速判断"用户是否在制裁名单上",false positive 再走精确查询。
  • Duplicate Order Detection:防止用户重复提交订单,Bloom Filter 先过滤已存在的 order ID。
  • Blacklist IP Pre-Check:IP 黑名单前置过滤,减少 Redis 查询。
  • Transaction Hash Deduplication:去重已处理的交易 hash,避免重复入账。

4. Consistent Hash

Concept

Consistent Hashing 将节点和数据都映射到同一个 hash 环上,数据归属顺时针最近的节点。当节点增删时,只有相邻节点的数据需要迁移,而不是全部 rehash。

Analogy:就像一群朋友围成一个圈分糖果,每个糖果给顺时针最近的人。有人离开,只影响左右邻居。

Python Implementation

"""
Consistent Hash with Virtual Nodes.
Reduces load imbalance when node count is small.
"""
import hashlib
import bisect
from typing import List, Dict
 
 
class ConsistentHash:
    def __init__(self, nodes: List[str] = None, replicas: int = 150):
        self.replicas = replicas  # Virtual nodes per physical node
        self.ring = []            # Sorted list of hash values
        self.nodes = {}           # hash -> physical node
        self.keys = set()         # Physical nodes
        if nodes:
            for node in nodes:
                self.add_node(node)
 
    def _hash(self, key: str) -> int:
        return int(hashlib.md5(key.encode()).hexdigest(), 16)
 
    def add_node(self, node: str):
        self.keys.add(node)
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            self.nodes[key] = node
            bisect.insort(self.ring, key)
 
    def remove_node(self, node: str):
        self.keys.discard(node)
        for i in range(self.replicas):
            key = self._hash(f"{node}:{i}")
            del self.nodes[key]
            idx = bisect.bisect_left(self.ring, key)
            self.ring.pop(idx)
 
    def get_node(self, key: str) -> str:
        if not self.ring:
            return None
        h = self._hash(key)
        idx = bisect.bisect_right(self.ring, h)
        if idx == len(self.ring):
            idx = 0
        return self.nodes[self.ring[idx]]
 
    def get_distribution(self, test_keys: List[str]) -> Dict[str, int]:
        dist = {node: 0 for node in self.keys}
        for k in test_keys:
            node = self.get_node(k)
            dist[node] += 1
        return dist
 
 
# ===================== 测试代码 =====================
def test_consistent_hash():
    ch = ConsistentHash(nodes=["node-A", "node-B", "node-C"], replicas=150)
 
    # Generate test keys
    test_keys = [f"user_{i}" for i in range(10000)]
    dist = ch.get_distribution(test_keys)
    print("Initial distribution:", dist)
 
    # Add node D
    ch.add_node("node-D")
    dist2 = ch.get_distribution(test_keys)
    print("After adding node-D:", dist2)
 
    # Check data migration percentage
    moved = sum(1 for k in test_keys if ch.get_node(k) != ConsistentHash(
        nodes=["node-A", "node-B", "node-C"], replicas=150
    ).get_node(k))
    print(f"Keys moved: {moved}/{len(test_keys)} = {moved/len(test_keys)*100:.2f}%")
 
    # Remove node B
    ch.remove_node("node-B")
    dist3 = ch.get_distribution(test_keys)
    print("After removing node-B:", dist3)
 
 
if __name__ == "__main__":
    test_consistent_hash()

Java Implementation

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;
 
/**
 * Consistent Hash with Virtual Nodes.
 * Maps both nodes and data to a hash ring.
 */
public class ConsistentHash {
    private final int replicas; // Virtual nodes per physical node
    private final TreeMap<Long, String> ring = new TreeMap<>();
    private final Set<String> nodes = new HashSet<>();
 
    public ConsistentHash(int replicas, Collection<String> nodes) {
        this.replicas = replicas;
        for (String node : nodes) {
            addNode(node);
        }
    }
 
    public void addNode(String node) {
        nodes.add(node);
        for (int i = 0; i < replicas; i++) {
            long hash = hash(node + ":" + i);
            ring.put(hash, node);
        }
    }
 
    public void removeNode(String node) {
        nodes.remove(node);
        for (int i = 0; i < replicas; i++) {
            long hash = hash(node + ":" + i);
            ring.remove(hash);
        }
    }
 
    public String getNode(String key) {
        if (ring.isEmpty()) return null;
        long hash = hash(key);
        Map.Entry<Long, String> entry = ring.ceilingEntry(hash);
        if (entry == null) {
            entry = ring.firstEntry();
        }
        return entry.getValue();
    }
 
    private long hash(String key) {
        try {
            MessageDigest md = MessageDigest.getInstance("MD5");
            byte[] digest = md.digest(key.getBytes(StandardCharsets.UTF_8));
            return ((long) (digest[3] & 0xFF) << 24) |
                   ((long) (digest[2] & 0xFF) << 16) |
                   ((long) (digest[1] & 0xFF) << 8) |
                   ((long) (digest[0] & 0xFF));
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
    }
 
    // ===================== 测试代码 =====================
    public static void main(String[] args) {
        List<String> nodes = Arrays.asList("node-A", "node-B", "node-C");
        ConsistentHash ch = new ConsistentHash(150, nodes);
 
        Map<String, Integer> dist = new HashMap<>();
        for (int i = 0; i < 10000; i++) {
            String node = ch.getNode("user_" + i);
            dist.merge(node, 1, Integer::sum);
        }
        System.out.println("Initial: " + dist);
 
        ch.addNode("node-D");
        dist.clear();
        for (int i = 0; i < 10000; i++) {
            String node = ch.getNode("user_" + i);
            dist.merge(node, 1, Integer::sum);
        }
        System.out.println("After add node-D: " + dist);
 
        ch.removeNode("node-B");
        dist.clear();
        for (int i = 0; i < 10000; i++) {
            String node = ch.getNode("user_" + i);
            dist.merge(node, 1, Integer::sum);
        }
        System.out.println("After remove node-B: " + dist);
    }
}

Complexity Analysis

OperationTimeSpace
addNodeO(replicas * log N)O(replicas * nodes)
removeNodeO(replicas * log N)O(replicas * nodes)
getNodeO(log N)O(replicas * nodes)

虚拟节点数量:通常每个物理节点 100-200 个虚拟节点。虚拟节点越多,负载越均衡,但 ring 越大查询越慢。

大型加密货币交易所 / Risk 实际应用

  • Redis Cluster Sharding:风控特征存储在 Redis Cluster 中,使用 consistent hash 将 userId 映射到特定 Redis 节点,扩容时只迁移 1/N 数据。
  • Kafka Partition Assignment:自定义 partitioner 用 consistent hash 保证相同 key 始终落到同一 partition。
  • Rate Limiting Sharding:API 限流状态分散到多个 Redis 节点,consistent hash 按 userId 分片。
  • Cache Cluster:本地缓存集群(如 Caffeine + Hazelcast)的 key 分布策略。

5. Token Bucket

Concept

Token Bucket 是经典的 rate limiting 算法。桶以固定速率产生 token,请求来时要消费 token,有 token 就通过,没有就拒绝或等待。允许一定程度的突发流量(burst)。

Analogy:就像游乐园的代币机,每隔几秒自动吐出 1 个代币,玩项目需要消耗代币。代币可以攒着,最多攒满一桶。

Python Implementation

"""
Token Bucket - Rate limiting algorithm.
Supports burst traffic while maintaining average rate.
"""
import time
import threading
 
 
class TokenBucket:
    def __init__(self, rate: float, capacity: int):
        """
        rate: tokens added per second
        capacity: maximum tokens in bucket (burst size)
        """
        self.rate = rate
        self.capacity = capacity
        self.tokens = float(capacity)
        self.last_update = time.time()
        self.lock = threading.Lock()
 
    def _add_tokens(self):
        now = time.time()
        elapsed = now - self.last_update
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last_update = now
 
    def consume(self, tokens: int = 1) -> bool:
        with self.lock:
            self._add_tokens()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False
 
    def wait_time(self, tokens: int = 1) -> float:
        """Return seconds to wait before tokens are available."""
        with self.lock:
            self._add_tokens()
            if self.tokens >= tokens:
                return 0.0
            needed = tokens - self.tokens
            return needed / self.rate
 
 
# ===================== 测试代码 =====================
def test_token_bucket():
    bucket = TokenBucket(rate=10.0, capacity=5)  # 10/sec, burst 5
 
    # First 5 should pass immediately (burst)
    for i in range(5):
        assert bucket.consume(), f"Request {i} should pass"
 
    # 6th should fail (bucket empty)
    assert not bucket.consume(), "6th request should fail"
 
    # Wait for refill
    time.sleep(0.2)
    assert bucket.consume(), "Should pass after refill"
 
    # Wait time test
    bucket2 = TokenBucket(rate=2.0, capacity=1)
    assert bucket2.consume()
    wait = bucket2.wait_time()
    print(f"Wait time: {wait:.3f}s")
    assert 0.4 < wait < 0.6
 
    print("All Token Bucket tests passed!")
 
 
if __name__ == "__main__":
    test_token_bucket()

Java Implementation

/**
 * Token Bucket - Thread-safe rate limiter.
 * Allows burst up to capacity, then throttles to steady rate.
 */
public class TokenBucket {
    private final double rate;        // tokens per second
    private final double capacity;
    private double tokens;
    private long lastUpdateTimeNanos;
    private final Object lock = new Object();
 
    public TokenBucket(double rate, double capacity) {
        this.rate = rate;
        this.capacity = capacity;
        this.tokens = capacity;
        this.lastUpdateTimeNanos = System.nanoTime();
    }
 
    public boolean consume(double tokens) {
        synchronized (lock) {
            refill();
            if (this.tokens >= tokens) {
                this.tokens -= tokens;
                return true;
            }
            return false;
        }
    }
 
    public boolean consume() {
        return consume(1.0);
    }
 
    public double waitTime(double tokens) {
        synchronized (lock) {
            refill();
            if (this.tokens >= tokens) {
                return 0.0;
            }
            double needed = tokens - this.tokens;
            return needed / rate;
        }
    }
 
    private void refill() {
        long now = System.nanoTime();
        double elapsed = (now - lastUpdateTimeNanos) / 1_000_000_000.0;
        tokens = Math.min(capacity, tokens + elapsed * rate);
        lastUpdateTimeNanos = now;
    }
 
    // ===================== 测试代码 =====================
    public static void main(String[] args) throws InterruptedException {
        TokenBucket bucket = new TokenBucket(10.0, 5.0);
 
        // Burst 5 should pass
        for (int i = 0; i < 5; i++) {
            System.out.println("Request " + i + ": " + bucket.consume());
        }
        System.out.println("Request 5: " + bucket.consume()); // false
 
        Thread.sleep(200);
        System.out.println("After 200ms: " + bucket.consume()); // true
 
        // Wait time
        TokenBucket bucket2 = new TokenBucket(2.0, 1.0);
        bucket2.consume();
        System.out.println("Wait time: " + bucket2.waitTime(1.0) + "s");
    }
}

Complexity Analysis

OperationTimeSpace
consumeO(1)O(1)
wait_timeO(1)O(1)

关键设计:懒加载 refill(只在 consume 时计算),避免定时器线程。用 System.nanoTime() 保证精度。

大型加密货币交易所 / Risk 实际应用

  • Per-User API Rate Limit:每个用户每秒钟最多 N 次 API 调用,大型加密货币交易所 交易 API 的 X-MBX-USED-WEIGHT-1M 就是这种机制。
  • Withdrawal Rate Limit:提币接口按用户限流,防止机器人批量提币。
  • Internal Service Throttling:风控服务调用外部数据源(如链上分析 API)时用 token bucket 限流,防止打挂对方。
  • Order Placement Burst Control:允许用户短时间内下少量订单(burst),但长期平均速率受控。

6. Timing Wheel

Concept

Timing Wheel(时间轮)是 Kafka / Netty 使用的高效定时器结构。将时间划分为固定槽位(slot),每个槽位挂一个任务链表。指针每 tick 转动一格,到期就执行该槽位的所有任务。

Analogy:就像老式火车站的大钟,每个刻度(slot)下面挂着该时刻发车的列车(task)。指针每走一格,就把该刻度的所有车放行。

Python Implementation

"""
Hierarchical Timing Wheel - Multi-level timing wheel for efficient timeout management.
Level 0: tick=1ms,  20 slots  -> max 20ms
Level 1: tick=20ms, 60 slots  -> max 1200ms
Level 2: tick=1s,   60 slots  -> max 60s
"""
import time
import threading
from collections import deque
from typing import Callable, List, Optional
 
 
class TimerTask:
    def __init__(self, delay_ms: int, callback: Callable, recurring: bool = False):
        self.delay_ms = delay_ms
        self.callback = callback
        self.recurring = recurring
        self.rounds = 0  # How many rounds to wait in current slot
 
    def run(self):
        self.callback()
 
 
class TimingWheelLevel:
    def __init__(self, tick_ms: int, wheel_size: int):
        self.tick_ms = tick_ms
        self.wheel_size = wheel_size
        self.slots = [deque() for _ in range(wheel_size)]
        self.current_tick = 0
        self.interval = tick_ms * wheel_size
 
    def add(self, task: TimerTask, remaining_ms: int):
        """Add task, return True if task is placed in this level."""
        if remaining_ms >= self.interval:
            return False
        ticks = remaining_ms // self.tick_ms
        task.rounds = ticks // self.wheel_size
        slot_idx = (self.current_tick + ticks) % self.wheel_size
        self.slots[slot_idx].append(task)
        return True
 
    def advance(self) -> List[TimerTask]:
        self.current_tick = (self.current_tick + 1) % self.wheel_size
        slot = self.slots[self.current_tick]
        expired = []
        remaining = deque()
        for task in slot:
            if task.rounds <= 0:
                expired.append(task)
            else:
                task.rounds -= 1
                remaining.append(task)
        self.slots[self.current_tick] = remaining
        return expired
 
 
class HierarchicalTimingWheel:
    def __init__(self, tick_ms: int = 1, wheel_size: int = 20):
        self.tick_ms = tick_ms
        self.wheel_size = wheel_size
        # Level 0: tick=1ms,   20 slots -> 20ms
        # Level 1: tick=20ms,  60 slots -> 1200ms
        # Level 2: tick=1200ms, 60 slots -> 72000ms (72s)
        self.levels = [
            TimingWheelLevel(tick_ms, wheel_size),
            TimingWheelLevel(tick_ms * wheel_size, wheel_size),
            TimingWheelLevel(tick_ms * wheel_size * wheel_size, wheel_size),
        ]
        self.running = False
        self.lock = threading.Lock()
        self.thread: Optional[threading.Thread] = None
 
    def start(self):
        self.running = True
        self.thread = threading.Thread(target=self._tick_loop)
        self.thread.daemon = True
        self.thread.start()
 
    def stop(self):
        self.running = False
        if self.thread:
            self.thread.join()
 
    def schedule(self, delay_ms: int, callback: Callable, recurring: bool = False):
        task = TimerTask(delay_ms, callback, recurring)
        with self.lock:
            self._add_task(task, delay_ms)
 
    def _add_task(self, task: TimerTask, remaining_ms: int):
        for level in self.levels:
            if level.add(task, remaining_ms):
                return
        # Overflow: put in highest level's last slot
        self.levels[-1].slots[-1].append(task)
 
    def _tick_loop(self):
        while self.running:
            time.sleep(self.tick_ms / 1000.0)
            with self.lock:
                self._advance()
 
    def _advance(self):
        carry = True
        for level in self.levels:
            expired = level.advance()
            for task in expired:
                # Execute in thread pool (simplified: direct call)
                task.run()
                if task.recurring:
                    self._add_task(task, task.delay_ms)
            if level.current_tick != 0:
                carry = False
                break  # No carry to next level
 
 
# ===================== 测试代码 =====================
def test_timing_wheel():
    results = []
 
    def callback(name):
        results.append((name, time.time()))
        print(f"[{time.time():.3f}] Task '{name}' executed")
 
    tw = HierarchicalTimingWheel(tick_ms=10, wheel_size=10)
    tw.start()
 
    tw.schedule(30, lambda: callback("A"))   # 30ms
    tw.schedule(50, lambda: callback("B"))   # 50ms
    tw.schedule(150, lambda: callback("C"))  # 150ms -> goes to level 1
 
    time.sleep(0.3)
    tw.stop()
 
    assert len(results) >= 3, f"Expected 3 tasks, got {len(results)}"
    print(f"\nAll {len(results)} tasks executed successfully!")
 
 
if __name__ == "__main__":
    test_timing_wheel()

Java Implementation

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.*;
 
/**
 * Hierarchical Timing Wheel - Multi-level timing wheel.
 * Netty/Kafka style timer for efficient timeout management.
 */
public class HierarchicalTimingWheel {
    private final long tickMs;
    private final int wheelSize;
    private final TimingWheelLevel[] levels;
    private final ScheduledExecutorService executor;
    private final ExecutorService taskExecutor;
 
    public HierarchicalTimingWheel(long tickMs, int wheelSize) {
        this.tickMs = tickMs;
        this.wheelSize = wheelSize;
        this.levels = new TimingWheelLevel[3];
        // Level 0: tick=1ms, 20 slots -> 20ms
        // Level 1: tick=20ms, 60 slots -> 1200ms
        // Level 2: tick=1200ms, 60 slots -> 72000ms
        this.levels[0] = new TimingWheelLevel(tickMs, wheelSize);
        this.levels[1] = new TimingWheelLevel(tickMs * wheelSize, wheelSize);
        this.levels[2] = new TimingWheelLevel(tickMs * wheelSize * wheelSize, wheelSize);
        this.executor = Executors.newSingleThreadScheduledExecutor();
        this.taskExecutor = Executors.newFixedThreadPool(4);
    }
 
    public void start() {
        executor.scheduleAtFixedRate(this::tick, tickMs, tickMs, TimeUnit.MILLISECONDS);
    }
 
    public void stop() {
        executor.shutdown();
        taskExecutor.shutdown();
    }
 
    public void schedule(long delayMs, Runnable task) {
        TimerTask timerTask = new TimerTask(delayMs, task);
        addTask(timerTask, delayMs);
    }
 
    private synchronized void addTask(TimerTask task, long remainingMs) {
        for (TimingWheelLevel level : levels) {
            if (level.add(task, remainingMs)) return;
        }
        levels[levels.length - 1].slots[wheelSize - 1].add(task);
    }
 
    private synchronized void tick() {
        boolean carry = true;
        for (TimingWheelLevel level : levels) {
            List<TimerTask> expired = level.advance();
            for (TimerTask task : expired) {
                taskExecutor.execute(task.runnable);
            }
            if (level.currentTick != 0) {
                carry = false;
                break;
            }
        }
    }
 
    private static class TimerTask {
        long delayMs;
        Runnable runnable;
        int rounds = 0;
        TimerTask(long delayMs, Runnable runnable) {
            this.delayMs = delayMs;
            this.runnable = runnable;
        }
    }
 
    private class TimingWheelLevel {
        final long tickMs;
        final int wheelSize;
        final Queue<TimerTask>[] slots;
        int currentTick = 0;
        final long interval;
 
        @SuppressWarnings("unchecked")
        TimingWheelLevel(long tickMs, int wheelSize) {
            this.tickMs = tickMs;
            this.wheelSize = wheelSize;
            this.interval = tickMs * wheelSize;
            this.slots = new Queue[wheelSize];
            for (int i = 0; i < wheelSize; i++) slots[i] = new LinkedList<>();
        }
 
        boolean add(TimerTask task, long remainingMs) {
            if (remainingMs >= interval) return false;
            long ticks = remainingMs / tickMs;
            task.rounds = (int) (ticks / wheelSize);
            int slotIdx = (int) ((currentTick + ticks) % wheelSize);
            slots[slotIdx].add(task);
            return true;
        }
 
        List<TimerTask> advance() {
            currentTick = (currentTick + 1) % wheelSize;
            Queue<TimerTask> slot = slots[currentTick];
            List<TimerTask> expired = new LinkedList<>();
            Queue<TimerTask> remaining = new LinkedList<>();
            for (TimerTask task : slot) {
                if (task.rounds <= 0) {
                    expired.add(task);
                } else {
                    task.rounds--;
                    remaining.add(task);
                }
            }
            slots[currentTick] = remaining;
            return expired;
        }
    }
 
    // ===================== 测试代码 =====================
    public static void main(String[] args) throws InterruptedException {
        HierarchicalTimingWheel tw = new HierarchicalTimingWheel(10, 10);
        tw.start();
 
        CountDownLatch latch = new CountDownLatch(3);
 
        tw.schedule(30, () -> {
            System.out.println("Task A executed");
            latch.countDown();
        });
        tw.schedule(50, () -> {
            System.out.println("Task B executed");
            latch.countDown();
        });
        tw.schedule(150, () -> {
            System.out.println("Task C executed (level 1)");
            latch.countDown();
        });
 
        latch.await(1, TimeUnit.SECONDS);
        tw.stop();
        System.out.println("All tasks executed!");
    }
}

Complexity Analysis

OperationTimeSpace
scheduleO(1)O(tasks)
tick (per tick)O(expired_tasks)O(tasks)
cancelO(1) with hashtableO(tasks)

层级设计:单层时间轮最大只能表示 tick * slots 的延迟。层级时间轮通过多层(如毫秒级、秒级、分钟级)实现任意大的延迟,同时保持 O(1) 的插入和 tick。

大型加密货币交易所 / Risk 实际应用

  • Order Timeout Management:挂单超过 N 秒未成交自动取消。交易引擎管理百万级订单的超时,Timing Wheel 比 PriorityQueue 高效得多。
  • Connection Timeout:WebSocket / TCP 连接超时管理,Netty 的 HashedWheelTimer 就是这种实现。
  • Delayed Message Processing:Kafka 的 delayed operation(如 delayed fetch, delayed produce)使用 Timing Wheel 管理。
  • Risk Alert Throttling:风控告警在触发后 N 分钟内不重复发送,Timing Wheel 管理 cooldown 时间。
  • Session Expiry:用户登录 session TTL 管理,到期自动踢出。

7. 面试现场建议

7.1 30 分钟白板 LRU 的标准流程

Phase 1:理解题意 (2 min)

  • 确认:get 和 put 都要是 O(1)
  • 确认:是否需要 thread-safe?(通常先写单线程,再提 thread-safe)
  • 确认:capacity 是 count-based 还是 size-based?(先 count-based)

Phase 2:核心设计 (5 min)

  • 在白板上画:HashMap + Doubly Linked List
  • HashMap: key -> Node,O(1) 定位
  • Doubly Linked List: 维护访问顺序,head=MRU, tail=LRU
  • 写 Node 结构:key, val, prev, next

Phase 3:实现代码 (15 min)

class Node:
    def __init__(self, k, v):
        self.key = k
        self.val = v
        self.prev = self.next = None
  • 先写 __init__ 初始化 dummy head/tail
  • 再写 _remove(node) 和 _add_to_head(node) 辅助方法
  • 然后写 get:如果存在,remove + add_to_head
  • 最后写 put:如果存在 update + move_to_head;如果不存在 add_to_head + 检查 capacity

Phase 4:测试走查 (5 min)

  • 口头走一遍:cap=2, put(1), put(2), get(1), put(3), get(2)=?
  • 预期:get(2) = -1,因为 2 被淘汰

Phase 5:扩展讨论 (3 min)

  • "如果要 thread-safe,可以加 ReadWriteLock,读多写少场景性能更好"
  • "如果要 size-based(比如缓存总大小不超过 100MB),Node 里加 size 字段,总量超了就淘汰"
  • "如果要 eviction callback(如淘汰时写回 DB),在 _remove 里触发"

7.2 加分项(主动提及)

话题一句话表达
Thread Safety"单线程版本先保证正确性,生产环境会用 ConcurrentHashMap + ReentrantReadWriteLock"
Size-based Eviction"大型加密货币交易所 缓存的是 protobuf 对象,按字节数控制更合理,Node 里加 size 字段"
Expiration Policy"可以加 expireAt 字段,get 时检查是否过期,类似 Caffeine 的 expireAfterWrite"
Eviction Callback"淘汰时触发 onEvict(key, value),用于 write-through 或 audit log"
Distributed LRU"单节点用本地缓存,集群场景用 Redis + local LRU 做 L1/L2,或用 Hazelcast/Caffeine 分布式版本"
Cache Warming"服务启动时预加载热点数据,避免冷启动击穿 DB"

7.3 避免的坑

  • 不要先写 list.remove(key):链表删除需要节点引用,不是 key
  • 不要忘记更新 HashMap:put 新 key 时,old node 要从 HashMap 删除
  • 不要写错边界条件:self.size > self.capacity 时才淘汰,不是 >=
  • 不要过度设计:先写单线程,面试官问才加锁

8. 常见追问应对

Q1: How to make LRU thread-safe?

Model Answer:

"单线程版本用 HashMap + DoubleLinkedList。线程安全版本有两种方案:

  1. 粗粒度锁:ReentrantLock 保护所有操作,简单但并发度低。
  2. 细粒度锁:Java 的 ConcurrentHashMap 保证 map 安全,链表操作用 ReentrantReadWriteLock,读多写少时性能更好。
  3. Lock-free:用 ConcurrentLinkedDeque + ConcurrentHashMap,但实现复杂,容易出 bug。 生产环境我倾向方案 2,够简单且性能足够。大型加密货币交易所 的 Caffeine 缓存库内部用了 Striped ReadWriteLock,分段锁减少竞争。"

Q2: What's the false positive rate of Bloom Filter?

Model Answer:

"False Positive Rate 的公式是: 假阳性率近似:p ≈ (1 - exp(-k*n/m))^k(m 位数,n 元素数,k 哈希次数) 其中 k=hash 函数数量, n=插入元素数, m=bit 数组大小。 给定 n 和 p,最优参数是:

  • m = -n * ln(p) / (ln2)^2
  • k = m/n * ln2 例如 n=100万, p=0.1% 时,m ≈ 1.44MB, k=10。 False Negative 一定为 0——如果 Bloom Filter 说不在,那一定不在。"

Q3: How many virtual nodes for Consistent Hash?

Model Answer:

"虚拟节点数量是 load balance 和 metadata overhead 的 trade-off:

  • 太少(<50):节点少时负载不均衡,hash 环上大片区域归一个节点。
  • 太多(>500):内存开销大,查询变慢(TreeMap 的 O(log N) 中 N 变大)。
  • Sweet spot:100-200 个虚拟节点/物理节点。 例如 大型加密货币交易所 的 Redis Cluster 有 10 个节点,150 个虚拟节点,ring 上共 1500 个点,TreeMap 查询完全够用。 还可以给不同权重的节点配不同数量的虚拟节点,实现 weighted consistent hash。"

Q4: Token Bucket vs Sliding Window?

Model Answer:

"两者都是限流算法,但场景不同:

维度Token BucketSliding Window
突发流量允许 burst(桶里有 token 就能用)严格平滑(按窗口平均)
内存开销O(1) 两个变量O(N) 记录每个请求时间
精度高(懒加载计算)取决于窗口粒度
适用场景API rate limit,允许突发严格计数,如短信发送次数
大型加密货币交易所 API 用 Token Bucket 因为交易场景需要允许合理 burst(如开盘瞬间的下单潮)。Sliding Window 用在严格计数场景,如每日提币次数限制。"

Q5: What's the difference between Timing Wheel and Priority Queue?

Model Answer:

"两者都能管理定时任务,但 Timing Wheel 在大规模任务下性能更好:

  • PriorityQueue(Min-Heap):插入 O(log N),取最小 O(1),tick 时检查堆顶是否到期。适合任务数量少(<1万)。
  • Timing Wheel:插入 O(1),tick 时只检查当前 slot。适合任务数量极大(百万级)。 因为 PriorityQueue 的 O(log N) 在 N=100万时约等于 20 次比较,而 Timing Wheel 永远是 O(1)。Kafka 处理百万级 delayed fetch 请求就是用的 Timing Wheel。"

Q6: How to handle memory limit in LFU?

Model Answer:

"LFU 通常有两种内存控制方式:

  1. Count-based:限制 key 的数量(如最多 1 万个),实现简单。
  2. Size-based:限制总内存大小(如最多 100MB),每个 Node 记录 size(如 value 的 byte 长度),put 时检查 total_size + new_size > capacity,超了就按 LFU 淘汰直到满足。 大型加密货币交易所 场景下,value 可能是 protobuf message 或大 JSON,size-based 更合理。实现时在 Node 里加 int size,LFUCache 里维护 current_size,淘汰时循环调用 evict 直到 current_size + new_size <= capacity。"

Q7: Can Bloom Filter support deletion?

Model Answer:

"标准 Bloom Filter 不支持删除,因为多个 key 可能共享同一个 bit,删除会误伤其他 key。 但有两种变体支持删除:

  1. Counting Bloom Filter:每个 bit 改成 counter(如 4-bit),add 时 counter++,delete 时 counter--。空间开销 ×4~8。
  2. Cuckoo Filter:用 cuckoo hash 存储指纹,支持删除且空间效率比 Counting Bloom Filter 更好。 大型加密货币交易所 制裁名单场景是只增不减(名单只会加人),标准 Bloom Filter 就够了。如果是动态黑白名单,可以用 Cuckoo Filter 或 Redis 的 RedisBloom 模块。"

Q8: How would you implement this in a distributed setting?

Model Answer:

"分布式场景下每种结构有不同的方案:

  • LRU/LFU:单节点用 Caffeine,分布式用 Redis(但 Redis 的 LRU 是近似的)。更高可用用 Hazelcast / Ignite。
  • Bloom Filter:可以每个节点持有一份相同的 Bloom Filter(只读),更新时广播或定时同步。或者用 RedisBloom 模块。
  • Consistent Hash:配合 virtual node 做数据分片,如 Redis Cluster 的 16384 个 slot 就是一种 consistent hash。
  • Token Bucket:分布式限流用 Redis + Lua 脚本实现原子 INCR 和 EXPIRE,或者用专门的限流服务(如 Sentinel)。大型加密货币交易所 可能用 Redis Cell 模块或自研的分布式 token bucket。
  • Timing Wheel:单节点用本地 wheel,分布式延迟任务用 Redis ZSET(score=执行时间戳)或 Kafka delayed operation。"

Q9: What's the time complexity of Consistent Hash with virtual nodes?

Model Answer:

"查找是 O(log V),V = 虚拟节点总数 = 物理节点数 × replicas。因为用 TreeMap/红黑树维护有序的 hash ring。 添加/删除节点是 O(replicas × log V),因为要对每个虚拟节点做 TreeMap 的插入/删除。 如果 replicas=150,物理节点=10,V=1500,log(1500)≈11,完全可以忽略。 优化:如果 hash 函数分布均匀,可以用跳表或数组+二分查找替代 TreeMap,查找降到 O(log V) 但常数更小。"

Q10: How does Timing Wheel handle tasks with very long delays (e.g., 1 day)?

Model Answer:

"单层时间轮最大只能表示 tick × slots 的延迟,比如 tick=1ms, slots=1024,最大只能表示约 1 秒。 层级时间轮(Hierarchical Timing Wheel) 解决这个问题:

  • Level 0:tick=1ms, 1024 slots -> 约 1s
  • Level 1:tick=1s, 1024 slots -> 约 17min
  • Level 2:tick=1min, 1024 slots -> 约 17h
  • Level 3:tick=1h, 1024 slots -> 约 42d 插入时从高层到低层,找到能容纳该 delay 的最底层放入。tick 时低层转一圈 carry 到高层。 Kafka 的 TimingWheel 就是三层结构,Netty 的 HashedWheelTimer 是单层但支持大 delay(通过 rounds 计数)。"

Last Updated: 2026-05-14 Target Position: 大型加密货币交易所 Senior Backend Developer - Risk Study Tip: 先背熟 LRU 和 Token Bucket 的手写代码(考频最高),然后 Bloom Filter 和 Consistent Hash(系统 design 必考),最后 LFU 和 Timing Wheel(高级/追问)。