手写题（5 题）

这 5 道不算「刷题」，但面试出现频率极高，能直接看出基本功。全部用 JavaScript 写。 返回目录：4.algorithms/题单.md

1. LRU 缓存

题意：实现 get / put，容量满了淘汰最久未使用的。 思路：哈希表 + 双向链表。哈希表 O(1) 定位，链表 O(1) 移动和删除。JS 的 Map 恰好保持插入顺序，可以直接当「链表」用。 复杂度：get / put 都是 O(1)。 易错：get 命中后必须先删再插，把 key 移到「最新」的位置，只 set 不 delete 顺序不变。 易错：淘汰时取 this.map.keys().next().value，就是最旧的那个 key。

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map(); // 迭代顺序 = 插入顺序，最旧的在最前面
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key); // 先删
    this.map.set(key, val); // 再插 -> 变成最新
    return val;
  }

  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.cap) {
      // Map 的第一个 key 就是最久未使用的
      this.map.delete(this.map.keys().next().value);
    }
  }
}

追问：「不用 Map 怎么写？」——手写双向链表 + 哈希表，链表头是最新、尾是最旧，这是 Java / Go 面试的写法。

2. 限流器（令牌桶）

题意：实现 allow()，每秒放 rate 个令牌，桶容量 burst，令牌够才能通过。 思路：惰性补充令牌——不启定时器，每次请求按时间差算该补多少，省掉后台任务。 复杂度：O(1)。 易错：补充令牌后要 Math.min(burst, ...) 封顶，否则长时间空闲后桶会溢出。 易错：更新 last 要放在算完 elapsed 之后。 追问：「分布式限流怎么做？」——Redis + Lua 保证原子性，或在网关层统一限流。

class RateLimiter {
  constructor(rate, burst) {
    this.rate = rate; // 每秒补充的令牌数
    this.burst = burst; // 桶容量
    this.tokens = burst; // 初始装满
    this.last = Date.now();
  }

  allow(now = Date.now()) {
    const elapsed = (now - this.last) / 1000;
    this.tokens = Math.min(this.burst, this.tokens + elapsed * this.rate); // 惰性补充
    this.last = now;

    if (this.tokens >= 1) {
      this.tokens -= 1;
      return true;
    }
    return false;
  }
}

3. Promise.all

题意：手写 Promise.all，全部成功才成功，任一失败就失败。 思路：计数 + 结果数组，任一 reject 就整体 reject。 易错：结果要按输入顺序存，用 results[i] = value 而不是 push（push 是完成顺序）。 易错：空数组要同步 resolve（new Promise 里直接 return resolve([])）。 追问：「allSettled / race / any 怎么写？」——allSettled 把每个 promise 都包一层不 reject；race 谁先 settle 就用谁。

function promiseAll(iterable) {
  const items = Array.from(iterable);
  return new Promise((resolve, reject) => {
    const results = new Array(items.length);
    let count = 0;
    if (items.length === 0) return resolve(results);

    items.forEach((item, i) => {
      // Promise.resolve 包一层，兼容普通值
      Promise.resolve(item).then((value) => {
        results[i] = value; // 按下标存，保证顺序
        if (++count === items.length) resolve(results);
      }, reject);
    });
  });
}

4. 防抖 / 节流

题意：防抖 = 停止触发后 wait 毫秒执行一次（搜索框）；节流 = wait 毫秒内最多执行一次（滚动事件）。 思路：防抖用 clearTimeout 不断重置；节流用时间戳判断距上次执行够不够久。 易错：this 和参数要透传，所以返回普通函数（不是箭头函数）+ apply。 易错：防抖第一次触发也要等 wait，如果要求「立即执行一次」需要额外加 immediate 分支。

function debounce(fn, wait) {
  let timer = null;
  return function (...args) {
    clearTimeout(timer);
    timer = setTimeout(() => fn.apply(this, args), wait);
  };
}

function throttle(fn, wait) {
  let last = 0;
  return function (...args) {
    const now = Date.now();
    if (now - last >= wait) {
      last = now;
      fn.apply(this, args);
    }
  };
}

追问：「节流的「最后一次也要执行」怎么加？」——加一个 timer：如果还在冷却期，就把最后一次调用记下来，冷却结束时补执行。

5. 手写 Promise（then / 链式调用）

题意：实现一个能链式调用、支持异步回调的简易 Promise。 思路：三个状态 + 回调队列；then 返回新的 Promise，把结果透传下去。 易错：回调必须异步执行（queueMicrotask），否则 then 里拿不到最终状态。 易错：then 的参数不是函数时要透传（值继续往后走，错误继续往后抛）。 易错：回调抛异常要变成 reject，then 才能链式捕获。

class MyPromise {
  constructor(executor) {
    this.state = 'pending'; // pending | fulfilled | rejected
    this.value = undefined;
    this.callbacks = [];
    const resolve = (v) => this.settle('fulfilled', v);
    const reject = (e) => this.settle('rejected', e);
    try {
      executor(resolve, reject);
    } catch (e) {
      reject(e); // executor 里抛错直接 reject
    }
  }

  settle(state, value) {
    if (this.state !== 'pending') return; // 状态不可逆
    if (value instanceof MyPromise) {
      // resolve 一个 Promise 要跟着它的结果走
      return value.then(
        (v) => this.settle('fulfilled', v),
        (e) => this.settle('rejected', e)
      );
    }
    this.state = state;
    this.value = value;
    const callbacks = this.callbacks;
    this.callbacks = [];
    callbacks.forEach((cb) => this.run(cb));
  }

  run({ onFulfilled, onRejected, resolve, reject }) {
    queueMicrotask(() => {
      const handler = this.state === 'fulfilled' ? onFulfilled : onRejected;
      if (typeof handler !== 'function') {
        // 透传：没有对应回调就把值/错误交给下一个 Promise
        (this.state === 'fulfilled' ? resolve : reject)(this.value);
        return;
      }
      try {
        resolve(handler(this.value));
      } catch (e) {
        reject(e);
      }
    });
  }

  then(onFulfilled, onRejected) {
    return new MyPromise((resolve, reject) => {
      const cb = { onFulfilled, onRejected, resolve, reject };
      if (this.state === 'pending') {
        this.callbacks.push(cb); // 还没 settle，先存起来
      } else {
        this.run(cb); // 已经 settle，异步执行
      }
    });
  }
}