前端算法与数据结构

What — 前端工程师为什么需要算法

前端工程师与算法的关系

前端工程师并非只需要掌握 CSS 和 DOM 操作。算法能力在以下场景中至关重要：

• 性能优化：列表虚拟化、搜索过滤、大量数据处理都需要算法思维
• 面试准备：大厂前端面试中算法题占比逐年上升，LeetCode 已成为标配
• 框架源码理解：Virtual DOM diff（树 diffing）、React Fiber 调度（链表遍历）、Vue 响应式收集（依赖图）等核心机制都依赖经典数据结构与算法
• 工程工具链：打包器模块图（图与拓扑排序）、路由匹配（Trie 树）、模板编译（栈解析）无一不需要算法支撑

算法复杂度基础

大 O 表示法描述算法运行时间/空间随输入规模增长的上界。

面试技巧：先说思路，再写代码，最后分析时间/空间复杂度。复杂度分析是加分项。

前端相关数据结构

Why — 算法在前端中的真实存在

前端框架与工具中的算法映射

前端 vs 后端算法关注点对比

核心认知：前端算法更侧重”实现能力”和”场景落地”，而非极致优化。面试中手写实现题（如 LRU、深拷贝、EventEmitter）的频率远高于纯算法推导。

How — 前端算法学习与实践

1. 数组与字符串

核心技巧：双指针、滑动窗口、前缀和。

双指针

双指针适用于有序数组的查找、原地修改等场景。

// 合并两个有序数组（力扣 88）
function merge(
  nums1: number[],
  m: number,
  nums2: number[],
  n: number
): void {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;
  while (i >= 0 && j >= 0) {
    nums1[k--] = nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
  }
  while (j >= 0) {
    nums1[k--] = nums2[j--];
  }
}

滑动窗口

滑动窗口适用于连续子数组/子串问题。

// 无重复字符的最长子串（力扣 3）
function lengthOfLongestSubstring(s: string): number {
  const charIndex = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (charIndex.has(ch) && charIndex.get(ch)! >= left) {
      left = charIndex.get(ch)! + 1;
    }
    charIndex.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

数组扁平化

// 递归实现
function flatten(arr: unknown[]): unknown[] {
  const result: unknown[] = [];
  for (const item of arr) {
    if (Array.isArray(item)) {
      result.push(...flatten(item));
    } else {
      result.push(item);
    }
  }
  return result;
}

// 迭代实现（栈）
function flattenIterative(arr: unknown[]): unknown[] {
  const stack = [...arr];
  const result: unknown[] = [];
  while (stack.length) {
    const item = stack.pop()!;
    if (Array.isArray(item)) {
      stack.push(...item);
    } else {
      result.push(item);
    }
  }
  return result.reverse();
}

2. 栈与队列

核心技巧：栈处理”最近相关性”（括号、嵌套），队列处理”先进先出”顺序。

有效括号

// 力扣 20：有效的括号
function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{',
  };
  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false;
    } else {
      stack.push(ch);
    }
  }
  return stack.length === 0;
}

浏览器前进后退（栈）

class BrowserHistory {
  private backStack: string[] = [];
  private forwardStack: string[] = [];
  private current: string;

  constructor(url: string) {
    this.current = url;
  }

  visit(url: string): void {
    this.backStack.push(this.current);
    this.current = url;
    this.forwardStack = []; // 新访问清空前进栈
  }

  back(): string {
    if (this.backStack.length === 0) return this.current;
    this.forwardStack.push(this.current);
    this.current = this.backStack.pop()!;
    return this.current;
  }

  forward(): string {
    if (this.forwardStack.length === 0) return this.current;
    this.backStack.push(this.current);
    this.current = this.forwardStack.pop()!;
    return this.current;
  }
}

事件循环模拟（队列）

class EventLoopSimulator {
  private macroQueue: (() => void)[] = [];
  private microQueue: (() => void)[] = [];

  queueMacro(fn: () => void): void {
    this.macroQueue.push(fn);
  }

  queueMicro(fn: () => void): void {
    this.microQueue.push(fn);
  }

  async run(): Promise<void> {
    while (this.macroQueue.length > 0) {
      // 取一个宏任务执行
      const macro = this.macroQueue.shift()!;
      macro();

      // 清空所有微任务
      while (this.microQueue.length > 0) {
        const micro = this.microQueue.shift()!;
        micro();
      }
    }
  }
}

3. 链表

核心技巧：哑节点（dummy head）、快慢指针、递归。

反转链表

interface ListNode {
  val: number;
  next: ListNode | null;
}

// 迭代反转
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

检测环（快慢指针）

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

与 React Fiber 的联系

React Fiber 架构将组件树用链表重新组织：

Fiber 节点结构：
  child    → 第一个子节点
  sibling  → 下一个兄弟节点
  return   → 父节点

这种链表结构使得遍历可以被中断和恢复，是 Fiber 可中断渲染的基础。Fiber 的工作循环本质上就是对链表的深度优先遍历（用循环而非递归实现）。

// Fiber 遍历简化模型
function workLoop(root: FiberNode): void {
  let current: FiberNode | null = root;
  while (current) {
    // 执行工作单元...
    // 深度优先：优先 child，其次 sibling，最后 return
    if (current.child) {
      current = current.child;
    } else if (current.sibling) {
      current = current.sibling;
    } else {
      // 回溯到有未访问 sibling 的祖先
      current = current.return;
      while (current && !current.sibling) {
        current = current.return;
      }
      if (current) current = current.sibling;
    }
  }
}

4. 哈希表

核心技巧：以空间换时间、键值映射、去重计数。

两数之和

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (map.has(complement)) {
      return [map.get(complement)!, i];
    }
    map.set(nums[i], i);
  }
  return [];
}

LRU 缓存

LRU（Least Recently Used）是前端面试高频题，Vue 的 keep-alive 组件即采用此策略。

class LRUCache {
  private capacity: number;
  private map = new Map<number, DLLNode>();
  private head: DLLNode; // 哨兵头
  private tail: DLLNode; // 哨兵尾

  constructor(capacity: number) {
    this.capacity = capacity;
    this.head = { key: 0, value: 0, prev: null, next: null };
    this.tail = { key: 0, value: 0, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key)!;
    this.removeNode(node);
    this.addToHead(node);
    return node.value;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      const node = this.map.get(key)!;
      node.value = value;
      this.removeNode(node);
      this.addToHead(node);
    } else {
      const node: DLLNode = { key, value, prev: null, next: null };
      this.map.set(key, node);
      this.addToHead(node);
      if (this.map.size > this.capacity) {
        const removed = this.tail.prev!;
        this.removeNode(removed);
        this.map.delete(removed.key);
      }
    }
  }

  private removeNode(node: DLLNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addToHead(node: DLLNode): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
}

interface DLLNode {
  key: number;
  value: number;
  prev: DLLNode | null;
  next: DLLNode | null;
}

与 JS Map/WeakMap 的联系

WeakMap 常用于将 DOM 节点与数据关联，当 DOM 节点被移除时，关联数据自动被 GC 回收，避免内存泄漏。

5. 树

核心技巧：递归（DFS）、层序遍历（BFS）、回溯。

三种遍历

interface TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
}

// 前序遍历（根-左-右）
function preorder(root: TreeNode | null, result: number[] = []): number[] {
  if (!root) return result;
  result.push(root.val);
  preorder(root.left, result);
  preorder(root.right, result);
  return result;
}

// 中序遍历（左-根-右）
function inorder(root: TreeNode | null, result: number[] = []): number[] {
  if (!root) return result;
  inorder(root.left, result);
  result.push(root.val);
  inorder(root.right, result);
  return result;
}

// 层序遍历（BFS）
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];
  while (queue.length) {
    const level: number[] = [];
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      level.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result;
}

最大深度

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

与 DOM 树 / Virtual DOM diff 的联系

DOM 本质是一棵树，Virtual DOM diff 算法就是在这棵树上做同层对比：

// 简化版 Virtual DOM diff
interface VNode {
  tag: string;
  props: Record<string, unknown>;
  children: (VNode | string)[];
  key?: string | number;
}

function diff(oldNode: VNode, newNode: VNode): Patch[] {
  const patches: Patch[] = [];

  // 1. 同层比较 tag
  if (oldNode.tag !== newNode.tag) {
    patches.push({ type: 'REPLACE', node: newNode });
    return patches;
  }

  // 2. 比较属性
  const propPatches = diffProps(oldNode.props, newNode.props);
  if (propPatches) patches.push({ type: 'PROPS', props: propPatches });

  // 3. 比较子节点（使用 key 优化）
  const childPatches = diffChildren(oldNode.children, newNode.children);
  patches.push(...childPatches);

  return patches;
}

type Patch =
  | { type: 'REPLACE'; node: VNode }
  | { type: 'PROPS'; props: Record<string, unknown> }
  | { type: 'REORDER'; moves: Move[] }
  | { type: 'TEXT'; content: string };

interface Move { index: number; type: 'INSERT' | 'REMOVE'; key?: string | number; }

React diff 三策略：1) 同层比较（不跨层）2) 不同类型直接替换 3) 使用 key 优化列表复用。这些策略将 O(n³) 的树 diff 降为 O(n)。

6. 图

核心技巧：BFS、DFS、拓扑排序。前端主要涉及依赖图分析。

拓扑排序（模块依赖检测）

// 检测模块依赖图中是否存在循环依赖
function hasCircularDependency(
  graph: Map<string, string[]>
): boolean {
  const visited = new Set<string>();
  const inStack = new Set<string>();

  function dfs(node: string): boolean {
    if (inStack.has(node)) return true;  // 环检测
    if (visited.has(node)) return false;

    visited.add(node);
    inStack.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (dfs(neighbor)) return true;
    }

    inStack.delete(node);
    return false;
  }

  for (const node of graph.keys()) {
    if (dfs(node)) return true;
  }
  return false;
}

// 拓扑排序（构建顺序）
function topologicalSort(graph: Map<string, string[]>): string[] {
  const inDegree = new Map<string, number>();
  for (const node of graph.keys()) {
    inDegree.set(node, 0);
  }
  for (const [, deps] of graph) {
    for (const dep of deps) {
      inDegree.set(dep, (inDegree.get(dep) ?? 0) + 1);
    }
  }

  const queue: string[] = [];
  for (const [node, degree] of inDegree) {
    if (degree === 0) queue.push(node);
  }

  const result: string[] = [];
  while (queue.length) {
    const node = queue.shift()!;
    result.push(node);
    for (const dep of graph.get(node) ?? []) {
      inDegree.set(dep, inDegree.get(dep)! - 1);
      if (inDegree.get(dep) === 0) queue.push(dep);
    }
  }

  return result.length === graph.size ? result : []; // 空数组表示有环
}

与模块依赖图的联系

Webpack/Vite 在构建时需要分析模块间的 import 依赖关系，构建有向图后通过拓扑排序确定打包顺序。循环依赖（环）会导致运行时问题，因此检测环是关键步骤。

7. 排序

前端关注点：理解 Array.prototype.sort() 的底层实现及其稳定性。

快速排序

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter((x) => x < pivot);
  const middle = arr.filter((x) => x === pivot);
  const right = arr.filter((x) => x > pivot);
  return [...quickSort(left), ...middle, ...quickSort(right)];
}

归并排序（稳定排序）

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

Array.sort() 的实现

ES2019 规范要求 Array.prototype.sort() 必须是稳定排序。在此之前各引擎行为不一致，是一个常见面试陷阱。

8. 二分查找

核心技巧：在有序数据中 O(log n) 查找。

// 标准二分查找
function binarySearch(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = left + ((right - left) >> 1); // 防溢出写法
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

// 查找插入位置（左边界）
function searchInsert(arr: number[], target: number): number {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    const mid = left + ((right - left) >> 1);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

与虚拟列表的联系

虚拟列表根据 scrollTop 在已排序的位置数组中二分查找起始索引，实现 O(log n) 定位可视区域。

9. 动态规划

前端面试中 DP 难度一般不高，掌握经典入门题即可。

斐波那契（记忆化 / 滚动变量）

// 滚动变量优化空间至 O(1)
function fib(n: number): number {
  if (n <= 1) return n;
  let prev2 = 0;
  let prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

爬楼梯

function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev2 = 1;
  let prev1 = 2;
  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

最长递增子序列

// O(n log n) 解法（贪心 + 二分）
function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];
  for (const num of nums) {
    let left = 0;
    let right = tails.length;
    while (left < right) {
      const mid = left + ((right - left) >> 1);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }
    if (left === tails.length) tails.push(num);
    else tails[left] = num;
  }
  return tails.length;
}

Vue 3 的 DOM diff 中使用了最长递增子序列来最小化 DOM 移动操作。

10. 经典前端算法实现

LRU Cache（完整版）

见上文第 4 节。

Trie 前缀树（路由匹配）

class TrieNode {
  children: Map<string, TrieNode> = new Map();
  isEnd: boolean = false;
  handler?: () => void;
}

class RouterTrie {
  private root = new TrieNode();

  insert(path: string, handler: () => void): void {
    let node = this.root;
    for (const ch of path) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
    node.handler = handler;
  }

  search(path: string): (() => void) | null {
    let node = this.root;
    for (const ch of path) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch)!;
    }
    return node.isEnd ? node.handler ?? null : null;
  }

  startsWith(prefix: string): boolean {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children.has(ch)) return false;
      node = node.children.get(ch)!;
    }
    return true;
  }
}

防抖与节流

// 防抖：延迟执行，重复调用重置计时器
function debounce<T extends (...args: unknown[]) => void>(
  fn: T,
  delay: number,
  options: { leading?: boolean; trailing?: boolean } = {}
): T & { cancel: () => void } {
  const { leading = false, trailing = true } = options;
  let timer: ReturnType<typeof setTimeout> | null = null;
  let lastCallTime = 0;

  function debounced(this: unknown, ...args: unknown[]) {
    const now = Date.now();

    // leading: 第一次调用立即执行
    if (leading && now - lastCallTime > delay) {
      fn.apply(this, args);
      lastCallTime = now;
    }

    if (timer) clearTimeout(timer);
    timer = setTimeout(() => {
      if (trailing) fn.apply(this, args);
      timer = null;
    }, delay);
  }

  debounced.cancel = () => {
    if (timer) clearTimeout(timer);
    timer = null;
  };

  return debounced as T & { cancel: () => void };
}

// 节流：固定间隔执行，高频调用只按间隔触发
function throttle<T extends (...args: unknown[]) => void>(
  fn: T,
  interval: number,
  options: { leading?: boolean; trailing?: boolean } = {}
): T & { cancel: () => void } {
  const { leading = true, trailing = true } = options;
  let timer: ReturnType<typeof setTimeout> | null = null;
  let lastCallTime = 0;
  let lastArgs: unknown[] | null = null;

  function throttled(this: unknown, ...args: unknown[]) {
    const now = Date.now();

    if (!lastCallTime && !leading) {
      lastCallTime = now;
    }

    const remaining = interval - (now - lastCallTime);

    if (remaining <= 0) {
      if (timer) {
        clearTimeout(timer);
        timer = null;
      }
      fn.apply(this, args);
      lastCallTime = now;
      lastArgs = null;
    } else if (trailing && !timer) {
      lastArgs = args;
      timer = setTimeout(() => {
        if (lastArgs) fn.apply(this, lastArgs);
        timer = null;
        lastCallTime = leading ? Date.now() : 0;
        lastArgs = null;
      }, remaining);
    }
  }

  throttled.cancel = () => {
    if (timer) clearTimeout(timer);
    timer = null;
    lastCallTime = 0;
    lastArgs = null;
  };

  return throttled as T & { cancel: () => void };
}

深拷贝（含循环检测）

function deepClone<T>(obj: T, visited = new WeakMap<object, unknown>()): T {
  // 基本类型
  if (obj === null || typeof obj !== 'object') return obj;

  // 循环引用检测
  if (visited.has(obj as object)) return visited.get(obj as object) as T;

  // Date
  if (obj instanceof Date) return new Date(obj) as T;

  // RegExp
  if (obj instanceof RegExp) return new RegExp(obj.source, obj.flags) as T;

  // Map
  if (obj instanceof Map) {
    const clone = new Map();
    visited.set(obj as object, clone);
    obj.forEach((val, key) => clone.set(key, deepClone(val, visited)));
    return clone as T;
  }

  // Set
  if (obj instanceof Set) {
    const clone = new Set();
    visited.set(obj as object, clone);
    obj.forEach((val) => clone.add(deepClone(val, visited)));
    return clone as T;
  }

  // Array
  if (Array.isArray(obj)) {
    const clone: unknown[] = [];
    visited.set(obj as object, clone);
    for (let i = 0; i < obj.length; i++) {
      clone[i] = deepClone(obj[i], visited);
    }
    return clone as T;
  }

  // 普通对象
  const clone = Object.create(Object.getPrototypeOf(obj));
  visited.set(obj as object, clone);
  for (const key of Reflect.ownKeys(obj as object)) {
    (clone as Record<PropertyKey, unknown>)[key] = deepClone(
      (obj as Record<PropertyKey, unknown>)[key],
      visited
    );
  }
  return clone;
}

EventEmitter（发布订阅）

type Listener = (...args: unknown[]) => void;

class EventEmitter {
  private events = new Map<string, Set<Listener>>();

  on(event: string, listener: Listener): () => void {
    if (!this.events.has(event)) {
      this.events.set(event, new Set());
    }
    this.events.get(event)!.add(listener);

    // 返回取消订阅函数
    return () => this.off(event, listener);
  }

  off(event: string, listener: Listener): void {
    this.events.get(event)?.delete(listener);
  }

  once(event: string, listener: Listener): () => void {
    const wrapper: Listener = (...args) => {
      listener(...args);
      this.off(event, wrapper);
    };
    return this.on(event, wrapper);
  }

  emit(event: string, ...args: unknown[]): void {
    const listeners = this.events.get(event);
    if (listeners) {
      // 复制一份防止遍历中修改
      for (const listener of [...listeners]) {
        listener(...args);
      }
    }
  }
}

Promise.all / Promise.race 实现

function promiseAll<T>(promises: Promise<T>[]): Promise<T[]> {
  return new Promise((resolve, reject) => {
    const results: T[] = new Array(promises.length);
    let count = 0;

    if (promises.length === 0) {
      resolve(results);
      return;
    }

    promises.forEach((promise, index) => {
      Promise.resolve(promise).then(
        (value) => {
          results[index] = value;
          count++;
          if (count === promises.length) resolve(results);
        },
        (reason) => reject(reason)
      );
    });
  });
}

function promiseRace<T>(promises: Promise<T>[]): Promise<T> {
  return new Promise((resolve, reject) => {
    if (promises.length === 0) return; // 永远 pending
    promises.forEach((promise) => {
      Promise.resolve(promise).then(resolve, reject);
    });
  });
}

常见陷阱

算法面试备考最佳实践

1. 按专题刷题：先按数据结构分类（链表→栈→树→图），比随机刷效率高 3 倍
2. 前端优先：先刷高频前端实现题（深拷贝、LRU、EventEmitter、Promise），再刷 LeetCode 经典题
3. 限时训练：简单题 15 分钟，中等题 25 分钟，困难题可跳过
4. 先思路后代码：面试中先口头描述思路，确认方向正确再编码
5. 复杂度必答：写完代码主动分析时间/空间复杂度
6. 边界用例：空输入、单元素、重复元素、极大/极小值——提交前先检查
7. 手写能力：脱离 IDE 和自动补全，用白板/纸笔练习
8. 复盘总结：每题做后记录套路模板，同类型题一通百通

推荐刷题顺序：数组/字符串 → 哈希表 → 链表 → 栈/队列 → 树 → 二分查找 → 排序 → 动态规划 → 图

面试题

1. 实现一个带过期时间的 LRU 缓存

考察点：哈希表 + 双向链表 + 过期策略

interface CacheNode {
  key: number;
  value: number;
  expireAt: number;
  prev: CacheNode | null;
  next: CacheNode | null;
}

class LRUCacheWithExpiry {
  private capacity: number;
  private map = new Map<number, CacheNode>();
  private head: CacheNode;
  private tail: CacheNode;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.head = { key: 0, value: 0, expireAt: 0, prev: null, next: null };
    this.tail = { key: 0, value: 0, expireAt: 0, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key)!;
    if (Date.now() > node.expireAt) {
      this.removeNode(node);
      this.map.delete(key);
      return -1;
    }
    this.removeNode(node);
    this.addToHead(node);
    return node.value;
  }

  put(key: number, value: number, ttl: number = 60000): void {
    const expireAt = Date.now() + ttl;
    if (this.map.has(key)) {
      const node = this.map.get(key)!;
      node.value = value;
      node.expireAt = expireAt;
      this.removeNode(node);
      this.addToHead(node);
    } else {
      const node: CacheNode = {
        key, value, expireAt, prev: null, next: null,
      };
      this.map.set(key, node);
      this.addToHead(node);
      if (this.map.size > this.capacity) {
        const removed = this.tail.prev!;
        this.removeNode(removed);
        this.map.delete(removed.key);
      }
    }
  }

  private removeNode(node: CacheNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addToHead(node: CacheNode): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
}

2. 实现并发请求限制

考察点：队列、Promise 控制、异步调度

async function concurrentLimit(
  urls: string[],
  maxConcurrency: number
): Promise<unknown[]> {
  const results: unknown[] = new Array(urls.length);
  let currentIndex = 0;

  async function worker(): Promise<void> {
    while (currentIndex < urls.length) {
      const index = currentIndex++;
      try {
        const response = await fetch(urls[index]);
        results[index] = await response.json();
      } catch (error) {
        results[index] = error;
      }
    }
  }

  const workers = Array.from(
    { length: Math.min(maxConcurrency, urls.length) },
    () => worker()
  );
  await Promise.all(workers);
  return results;
}

3. 实现带并发数限制的 Promise 调度器

考察点：任务队列、微任务调度、并发控制

class Scheduler {
  private maxConcurrency: number;
  private running = 0;
  private queue: Array<() => Promise<unknown>> = [];

  constructor(maxConcurrency: number) {
    this.maxConcurrency = maxConcurrency;
  }

  add<T>(task: () => Promise<T>): Promise<T> {
    return new Promise((resolve, reject) => {
      const wrapped = async () => {
        this.running++;
        try {
          const result = await task();
          resolve(result);
        } catch (error) {
          reject(error);
        } finally {
          this.running--;
          this.next();
        }
      };
      if (this.running < this.maxConcurrency) {
        wrapped();
      } else {
        this.queue.push(wrapped);
      }
    });
  }

  private next(): void {
    if (this.queue.length > 0 && this.running < this.maxConcurrency) {
      const task = this.queue.shift()!;
      task();
    }
  }
}

// 使用示例
// const scheduler = new Scheduler(2);
// scheduler.add(() => fetch('/api/1'));
// scheduler.add(() => fetch('/api/2'));
// scheduler.add(() => fetch('/api/3')); // 等待前两个完成一个后再执行

4. 实现字符串模板引擎

考察点：正则、栈、字符串解析

function render(
  template: string,
  data: Record<string, unknown>
): string {
  return template.replace(/\{\{(\w+(?:\.\w+)*)\}\}/g, (_, path: string) => {
    const keys = path.split('.');
    let result: unknown = data;
    for (const key of keys) {
      result = (result as Record<string, unknown>)?.[key];
      if (result === undefined) return '';
    }
    return String(result);
  });
}

// render('Hello, {{user.name}}!', { user: { name: 'World' } })
// => 'Hello, World!'

5. 实现虚拟列表核心算法

考察点：二分查找、DOM 性能优化

class VirtualList {
  private positions: { top: number; height: number }[] = [];
  private visibleCount: number;
  private containerHeight: number;

  constructor(
    itemCount: number,
    itemHeight: number,
    containerHeight: number
  ) {
    this.containerHeight = containerHeight;
    this.visibleCount = Math.ceil(containerHeight / itemHeight) + 1;

    // 预计算每项位置（等高场景可 O(1) 计算，不等高需存储）
    for (let i = 0; i < itemCount; i++) {
      this.positions.push({ top: i * itemHeight, height: itemHeight });
    }
  }

  // 根据 scrollTop 二分查找起始索引
  getVisibleRange(scrollTop: number): {
    startIndex: number;
    endIndex: number;
    offsetY: number;
  } {
    let left = 0;
    let right = this.positions.length - 1;
    while (left <= right) {
      const mid = (left + right) >> 1;
      const { top, height } = this.positions[mid];
      if (scrollTop >= top && scrollTop < top + height) {
        const startIndex = mid;
        const endIndex = Math.min(
          startIndex + this.visibleCount,
          this.positions.length - 1
        );
        return {
          startIndex,
          endIndex,
          offsetY: this.positions[startIndex].top,
        };
      }
      if (scrollTop < top) right = mid - 1;
      else left = mid + 1;
    }
    return { startIndex: 0, endIndex: this.visibleCount - 1, offsetY: 0 };
  }
}

6. 判断两个对象深相等

考察点：递归、类型判断、边界处理

function isDeepEqual(a: unknown, b: unknown): boolean {
  // 同一引用
  if (a === b) return true;

  // null 或非对象
  if (a === null || b === null || typeof a !== 'object' || typeof b !== 'object') {
    return false;
  }

  // 类型不同
  if (Object.prototype.toString.call(a) !== Object.prototype.toString.call(b)) {
    return false;
  }

  // 数组
  if (Array.isArray(a)) {
    if (a.length !== (b as unknown[]).length) return false;
    return a.every((val, i) => isDeepEqual(val, (b as unknown[])[i]));
  }

  // 普通对象
  const keysA = Object.keys(a);
  const keysB = Object.keys(b);
  if (keysA.length !== keysB.length) return false;

  return keysA.every(
    (key) => Object.prototype.hasOwnProperty.call(b, key) &&
      isDeepEqual(
        (a as Record<string, unknown>)[key],
        (b as Record<string, unknown>)[key]
      )
  );
}

7. 实现一个 JSON Path 查询器

考察点：递归、路径解析、树遍历

function queryByPath(obj: unknown, path: string): unknown {
  const tokens = path
    .replace(/\[(\d+)]/g, '.$1')  // arr[0] → arr.0
    .replace(/\['([^']+)']/g, '.$1') // obj['key'] → obj.key
    .split('.')
    .filter(Boolean);

  let result: unknown = obj;
  for (const token of tokens) {
    if (result === null || result === undefined) return undefined;
    result = (result as Record<string | number, unknown>)[token];
  }
  return result;
}

// queryByPath({ a: { b: [{ c: 42 }] } }, "a.b[0].c") => 42

8. 实现数组扁平化并去重排序

考察点：递归/迭代扁平化、Set 去重、排序

function flattenUniqueSort(arr: unknown[]): number[] {
  // 扁平化
  function flat(input: unknown[]): number[] {
    const result: number[] = [];
    for (const item of input) {
      if (Array.isArray(item)) {
        result.push(...flat(item));
      } else if (typeof item === 'number') {
        result.push(item);
      }
    }
    return result;
  }

  // 去重 + 排序
  return [...new Set(flat(arr))].sort((a, b) => a - b);
}

// flattenUniqueSort([1, [2, [3, 2, 1], 4], [5, 3]])
// => [1, 2, 3, 4, 5]

相关链接

• LeetCode 热题 100 — 高频算法题精选
• 代码随想录 — 按专题系统刷题指南
• React Fiber 架构 — Fiber 链表遍历原理
• Vue3 Diff 算法源码 — 最长递增子序列应用
• V8 Array.sort 实现 — TimSort 原理
• ES2019 Stable sort — 规范要求