4081 字
20 分钟
Algorithm
2026-02-18
2026-02-21
未分类
无标签
统计加载中...

Algorithm#

明白了，非常抱歉刚才为了精简篇幅省略了原有问题和具体代码。这次我将完整保留所有原始问题，并为你逐一提供切实可用的代码实现（尽量保持代码简洁并直击核心逻辑），方便你直接用于面试复习和实战推演。

1. Promise 与异步并发控制#

Q1: 实现一个 Promise.all

JavaScript

Promise.myAll = function (promises) {
  return new Promise((resolve, reject) => {
    if (!Array.isArray(promises)) return reject(new TypeError('Argument must be an array'));
    let result = [];
    let count = 0;
    if (promises.length === 0) return resolve(result);


    promises.forEach((p, index) => {
      Promise.resolve(p).then(res => {
        result[index] = res; // 保证返回顺序
        count++;
        if (count === promises.length) resolve(result);
      }).catch(reject); // 任一失败则整体失败
    });
  });
};

Q2: 实现一个 Promise.allSettled

JavaScript

Promise.myAllSettled = function (promises) {
  return Promise.myAll(promises.map(p =>
    Promise.resolve(p)
      .then(value => ({ status: 'fulfilled', value }))
      .catch(reason => ({ status: 'rejected', reason }))
  ));
};

Q3: 实现一个异步任务的调度器 & Q4: 用 JS 实现一个并发控制器

(这两题本质是同一种实现，这里提供一个最经典的并发控制器类)

JavaScript

class Scheduler {
  constructor(limit) {
    this.limit = limit; // 最大并发数this.running = 0;   // 当前执行数this.queue = [];    // 等待队列
  }


  add(taskCreator) {
    return new Promise((resolve, reject) => {
      this.queue.push({ taskCreator, resolve, reject });
      this.run();
    });
  }


  run() {
    if (this.running < this.limit && this.queue.length > 0) {
      this.running++;
      const { taskCreator, resolve, reject } = this.queue.shift();


      taskCreator()
        .then(resolve)
        .catch(reject)
        .finally(() => {
          this.running--;
          this.run(); // 递归触发下一个
        });
    }
  }
}

2. 数据结构#

Q5: 实现一个 LRUCache

JavaScript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // Map 维持了插入的顺序
  }


  get(key) {
    if (!this.cache.has(key)) return -1;
    const value = this.cache.get(key);
    // 刷新活跃度：先删后加this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }


  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 淘汰最老的：Map.keys().next().value 是第一个插入的键this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

Q6: 实现一个深拷贝函数（兼容的数据结构越多越好，需要解决循环依赖情况）

JavaScript

function deepClone(target, map = new WeakMap()) {
  if (target === null || typeof target !== 'object') return target;


  // 处理特殊对象if (target instanceof Date) return new Date(target);
  if (target instanceof RegExp) return new RegExp(target);


  // 处理循环引用if (map.has(target)) return map.get(target);


  const cloneTarget = Array.isArray(target) ? [] : {};
  map.set(target, cloneTarget);


  // 遍历拷贝 (Reflect.ownKeys 兼容 Symbol 作为 key)Reflect.ownKeys(target).forEach(key => {
    cloneTarget[key] = deepClone(target[key], map);
  });


  return cloneTarget;
}

Q7: 如何判断一个单向链表是否存在环？(追问) 有没有别的方式？

JavaScript

// 方式 1：快慢指针 (空间复杂度 O(1)，最佳实践)function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}


// 方式 2：Set 缓存法 (空间复杂度 O(N)，容易想到)function hasCycleWithSet(head) {
  const visited = new Set();
  while (head) {
    if (visited.has(head)) return true;
    visited.add(head);
    head = head.next;
  }
  return false;
}

3. 数组/字符串与算法核心题#

Q8: 算法题：进阶版两数之和。给定一个包含重复元素的数组 nums 和一个目标值 target，找出数组中和为 target 的所有不重复的组合。

JavaScript

function twoSumUnique(nums, target) {
  nums.sort((a, b) => a - b); // 必须先排序const res = [];
  let left = 0, right = nums.length - 1;


  while (left < right) {
    const sum = nums[left] + nums[right];
    if (sum === target) {
      res.push([nums[left], nums[right]]);
      // 跳过重复元素去重while (left < right && nums[left] === nums[left + 1]) left++;
      while (left < right && nums[right] === nums[right - 1]) right--;
      left++;
      right--;
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return res;
}

Q9: （算法题）给定一个整数数组 nums 和一个整数 target，以及一个整数 k，编写一个函数 kSum，找出数组中所有满足元素个数为 k 且元素之和等于 target 的不重复组合。

JavaScript

function kSum(nums, target, k) {
  nums.sort((a, b) => a - b);


  function nSum(start, target, n) {
    const res = [];
    if (n === 2) { // 降维到 2Sumlet l = start, r = nums.length - 1;
      while (l < r) {
        let sum = nums[l] + nums[r];
        if (sum === target) {
          res.push([nums[l], nums[r]]);
          while (l < r && nums[l] === nums[l + 1]) l++;
          while (l < r && nums[r] === nums[r - 1]) r--;
          l++; r--;
        } else if (sum < target) l++;
        else r--;
      }
    } else { // 递归拆解for (let i = start; i < nums.length - n + 1; i++) {
        if (i > start && nums[i] === nums[i - 1]) continue; // 去重const subRes = nSum(i + 1, target - nums[i], n - 1);
        for (let arr of subRes) {
          res.push([nums[i], ...arr]);
        }
      }
    }
    return res;
  }
  return nSum(0, target, k);
}

Q10: （算法题）给到你一个整数数组和一个值 k，需要你找到这个整数数组里面连续项加起来等于 k 的情况有多少种？

JavaScript

// 前缀和 + 哈希表 (LeetCode 560)function subarraySum(nums, k) {
  const map = new Map();
  map.set(0, 1); // 初始前缀和为0的次数为1let count = 0;
  let preSum = 0;


  for (const num of nums) {
    preSum += num;
    if (map.has(preSum - k)) {
      count += map.get(preSum - k);
    }
    map.set(preSum, (map.get(preSum) || 0) + 1);
  }
  return count;
}

Q11: （算法题）找出一个整形数组里面第二小的元素，怎么做？口述，不用写代码。

(虽然原题要求口述，但按你的指令，这里给出代码实现以便直观理解口述逻辑)

JavaScript

// 口述逻辑：遍历一次数组。维护 min 和 secondMin 两个变量。function findSecondMinimum(nums) {
  let min = Infinity, secondMin = Infinity;
  for (let num of nums) {
    if (num < min) {
      secondMin = min; // 原本最小的退居第二
      min = num;
    } else if (num > min && num < secondMin) {
      secondMin = num; // 介于最小和第二小之间
    }
  }
  return secondMin === Infinity ? -1 : secondMin;
}

Q12: 算法题：买卖股票的最佳时机。（给定一个数组，代表每天的股票价格，求最大利润）。

JavaScript

function maxProfit(prices) {
  let minPrice = Infinity;
  let maxProfit = 0;
  for (let price of prices) {
    if (price < minPrice) {
      minPrice = price; // 记录历史最低点
    } else if (price - minPrice > maxProfit) {
      maxProfit = price - minPrice; // 更新最大利润
    }
  }
  return maxProfit;
}

Q13: 算法题：有序数组的子集判断

JavaScript

function isSubsequence(sub, main) {
  let i = 0, j = 0;
  while (i < main.length && j < sub.length) {
    if (main[i] === sub[j]) j++; // 匹配上了，子集指针右移
    i++; // 主数组指针永远右移
  }
  return j === sub.length;
}

Q14: (算法题) LeetCode：3375. 使数组的值全部为 K 的最少操作次数

JavaScript

function minOperations(nums, k) {
  const set = new Set(nums);
  let hasSmaller = false;


  for (let num of set) {
    if (num < k) return -1; // 只能减小，如果原本就有比 K 小的，永远无法全部变成 K
  }


  // 需要操作的次数就是大于 K 的不同元素的种类数return set.has(k) ? set.size - 1 : set.size;
}

Q15: 第一题：二叉树每层最右节点 (二叉树的右视图)

JavaScript

function rightSideView(root) {
  if (!root) return [];
  const res = [];
  const queue = [root];


  while (queue.length > 0) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      let node = queue.shift();
      if (i === size - 1) res.push(node.val); // 记录该层最后一个节点if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return res;
}

Q16: 第二题：实现一个 JSON.stringify，功能尽可能完善

JavaScript

function myStringify(data) {
  const type = typeof data;


  if (type !== 'object' || data === null) {
    if (type === 'string') return `"${data}"`;
    if (type === 'function' || type === 'undefined' || type === 'symbol') return undefined;
    return String(data);
  }


  if (data instanceof Date) return `"${data.toISOString()}"`;


  if (Array.isArray(data)) {
    const arrStr = data.map(item => myStringify(item) || 'null');
    return `[${arrStr.join(',')}]`;
  }


  const objStr = Object.keys(data).reduce((acc, key) => {
    const valStr = myStringify(data[key]);
    if (valStr !== undefined) acc.push(`"${key}":${valStr}`);
    return acc;
  }, []);


  return `{${objStr.join(',')}}`;
}

4. 组件实现 (核心逻辑层)#

Q17: （手写代码）请编写一个倒计时组件/方法，按秒维度倒计时。

JavaScript

// 基于原生 JS 的核心计算逻辑，可在 React/Vue 中封装为 Hookfunction startCountdown(endTimeStr, onTick) {
  const endTime = new Date(endTimeStr).getTime();


  const timer = setInterval(() => {
    const now = Date.now();
    const diff = Math.max(0, endTime - now); // 毫秒差if (diff === 0) {
      clearInterval(timer);
      onTick({ h: 0, m: 0, s: 0, finished: true });
      return;
    }


    const h = Math.floor(diff / (1000 * 60 * 60));
    const m = Math.floor((diff % (1000 * 60 * 60)) / (1000 * 60));
    const s = Math.floor((diff % (1000 * 60)) / 1000);


    onTick({ h, m, s, finished: false });
  }, 1000); // 实际生产中推荐 requestAnimationFrame 以避免后台休眠导致的节流return () => clearInterval(timer); // 返回清理函数
}

Q18: （手撕代码）JS 写一个搜索过滤组件 (带有防抖)

JavaScript

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


class SearchFilter {
  constructor(dataList, inputEl, resultEl) {
    this.dataList = dataList;
    this.resultEl = resultEl;


    // 绑定防抖事件
    inputEl.addEventListener('input', debounce((e) => {
      this.handleSearch(e.target.value);
    }, 300));
  }


  handleSearch(keyword) {
    if (!keyword.trim()) {
      this.render([]); return;
    }
    const filtered = this.dataList.filter(item => item.includes(keyword));
    this.render(filtered);
  }


  render(list) {
    if (list.length === 0) {
      this.resultEl.innerHTML = '<div>没匹配到了</div>';
    } else {
      this.resultEl.innerHTML = list.map(i => `<div>${i}</div>`).join('');
    }
  }
}

Q19: 如果让你设计一个通用的全屏覆盖层组件（Overlay/Dialog），你会怎么设计？需要管理生命周期吗？

JavaScript

// React 伪代码：考察 Portal、生命周期管理与事件拦截import { useEffect } from 'react';
import { createPortal } from 'react-dom';


function Dialog({ isOpen, onClose, children }) {
  useEffect(() => {
    if (!isOpen) return;


    // 生命周期管理 1: 阻止背景滚动document.body.style.overflow = 'hidden';


    // 生命周期管理 2: 监听 ESC 键const handleEsc = (e) => e.key === 'Escape' && onClose();
    window.addEventListener('keydown', handleEsc);


    return () => {
      // 销毁时清理document.body.style.overflow = 'auto';
      window.removeEventListener('keydown', handleEsc);
    };
  }, [isOpen, onClose]);


  if (!isOpen) return null;


  // 使用 Portal 挂载到 body 下，脱离当前 DOM 树的 CSS 层叠上下文限制return createPortal(
    <div className="overlay" onClick={onClose} style={{position: 'fixed', inset: 0}}><div className="content" onClick={e => e.stopPropagation()}>
        {/* 阻止点击穿透 */}
        {children}
      </div></div>,
    document.body
  );
}

5. 其他编程题#

Q20: （编程题）实现一个 Add 函数，运算只能通过调用 expensiveCall 实现

JavaScript

// 假设 given: function expensiveCall(a, b, cb) { setTimeout(() => cb(a+b), 100) }const asyncAdd = (a, b) => new Promise(resolve => expensiveCall(a, b, resolve));


async function sum(...args) {
  if (args.length === 0) return 0;
  if (args.length === 1) return args[0];


  // 并发两两相加let promises = [];
  for (let i = 0; i < args.length; i += 2) {
    if (i + 1 < args.length) {
      promises.push(asyncAdd(args[i], args[i + 1]));
    } else {
      promises.push(Promise.resolve(args[i])); // 落单的直接保留
    }
  }


  const results = await Promise.all(promises);
  return sum(...results); // 递归，直到只剩一个结果
}

Q21: （编程题 2）监听列表元素曝光（可以查 API 文档）

JavaScript

function observeElements(selector, onVisible) {
  const observer = new IntersectionObserver((entries, obs) => {
    entries.forEach(entry => {
      if (entry.isIntersecting) {
        onVisible(entry.target); // 触发曝光上报逻辑
        obs.unobserve(entry.target); // 上报后取消监听，节省性能
      }
    });
  }, { threshold: 0.5 }); // 露出 50% 算作曝光document.querySelectorAll(selector).forEach(el => observer.observe(el));
}

Q22: （编程题 3）开放题 为了性能要求，我们页面经常会组装一个 combo 请求

JavaScript

// 利用微任务批量收集同步发起的请求let batchIds = [];
let batchPromises = [];


function getUserInfo(id) {
  return new Promise((resolve, reject) => {
    batchIds.push(id);
    batchPromises.push({ resolve, reject });


    // 如果是这批的第一个请求，注册一个微任务去真正发请求if (batchIds.length === 1) {
      Promise.resolve().then(() => {
        const idsToFetch = [...batchIds];
        const promisesToResolve = [...batchPromises];


        // 清空队列，准备下一批
        batchIds = []; batchPromises = [];


        // 模拟真实 Combo 请求： fetch(`/api/users?ids=${idsToFetch.join(',')}`)
        mockFetch(idsToFetch).then(res => {
          promisesToResolve.forEach((p, idx) => p.resolve(res[idx]));
        }).catch(err => {
          promisesToResolve.forEach(p => p.reject(err));
        });
      });
    }
  });
}

Q23: （算法题）遇到中括号 [n] 重复对应次数，小括号 () 作为整体。

(此类题通常变种自 LeetCode 394 字符串解码，此处提供经典的栈解析法)

JavaScript

function decodeString(s) {
  let numStack = [];
  let strStack = [];
  let currentStr = '';
  let currentNum = 0;


  for (let char of s) {
    if (!isNaN(char)) {
      currentNum = currentNum * 10 + Number(char);
    } else if (char === '(' || char === '[') {
      numStack.push(currentNum || 1); // 默认倍数为 1
      strStack.push(currentStr);
      currentStr = '';
      currentNum = 0;
    } else if (char === ')' || char === ']') {
      const repeatTimes = numStack.pop();
      const prevStr = strStack.pop();
      currentStr = prevStr + currentStr.repeat(repeatTimes);
    } else {
      currentStr += char;
    }
  }
  return currentStr;
}

Q24: 第三题：微信团队组织员工去公园郊游，需要从租车点租赁自行车 (贪心双指针)

(背景：每车最多坐两人，有最大载重 limit)

JavaScript

function numRescueBikes(people, limit) {
  people.sort((a, b) => a - b);
  let left = 0;
  let right = people.length - 1;
  let bikes = 0;


  while (left <= right) {
    // 如果最轻和最重的能拼一辆车if (people[left] + people[right] <= limit) {
      left++;
    }
    // 无论是否拼车，最重的人都要消耗一辆车
    right--;
    bikes++;
  }
  return bikes;
}

太棒了。理解了 Event Loop（事件循环）在这些具体工程场景中的运作机制，你的 JavaScript 功底就会产生质的飞跃。不仅能写出这些代码，还能在面试中和面试官探讨“为什么要这么写”。

我们先用一张图在脑海里建立模型，然后再把 Q22 和 Q20 放进去跑一遍。

JavaScript 的运行机制就像一个永不停歇的工厂流水线，遵循着一个极其严格的“潜规则”：同步代码执行完后，必须把“微任务队列（Microtask Queue）”彻底清空，然后才能执行下一个“宏任务（Macrotask）”，并且在微任务清空后、下一个宏任务开始前，浏览器才有机会进行页面的重新渲染（Rendering）。

  • 同步代码：直接执行的代码（变量赋值、普通的函数调用）。
  • 微任务 (Microtask)：Promise.then/catch/finally、MutationObserver。它们的优先级极高，相当于“VIP 插队”。
  • 宏任务 (Macrotask)：setTimeout、setInterval、网络请求回调（Ajax/Fetch）、DOM 事件回调。

一、 拆解 Q22：Combo 请求合并（微任务的“聚宝盆”效应）#

这个场景在现代前端 Web 性能优化中非常经典。当页面加载时，多个独立的组件可能都在向服务端请求不同 ID 的用户信息，如果不做合并，就会产生大量的网络并发请求，消耗 TCP 连接资源并导致“瀑布流（Waterfall）”阻塞。

利用微任务在当前事件循环末尾统一执行的特性，我们可以完美实现“收集”与“统一发送”。

代码执行时间线：

  1. 同步阶段（收集需求）：

    • 组件 A 调用了 getUserInfo(1)。id = 1 被推入 batchIds 数组。
    • 因为这是第一个请求，触发 Promise.resolve().then(...)，这意味着往微任务队列里塞入了一个动作：“去发真实的网络请求”。
    • 组件 B 同步调用了 getUserInfo(2)。id = 2 被推入数组（此时 batchIds 变成了 [1, 2]）。因为数组长度不再是 1，所以它不会再注册新的微任务，只是默默把自己的 Promise 的 resolve 方法交给了管家。

  2. 微任务阶段（集中爆发）：

    • 同步代码执行完毕，主线程空闲（Call Stack 空了）。
    • Event Loop 检查微任务队列，发现了刚才注册的那个“发网络请求”的动作。
    • 这个微任务开始执行，此时它拿到的 batchIds 已经是完整收集到的 [1, 2]。它组装出一个 /api/users?ids=1,2 的请求发给服务端。

  3. 网络回调阶段（宏任务）：

    • 服务端返回数据后，触发网络回调（宏任务）。代码遍历之前存下来的 resolve 函数，把对应的数据精确分发给组件 A 和组件 B。

核心意义：利用微任务，我们把多次零散的网络 I/O 损耗，在不阻塞浏览器渲染生命周期的前提下，压缩成了一次高吞吐的请求。

二、 拆解 Q20：并发异步加法（宏微任务的交替执行）#

题目要求只能用 expensiveCall（内部是 setTimeout，属于宏任务）来实现加法，这就涉及到了如何通过 Promise（微任务）来编排并发的宏任务。

假设我们要计算 sum(1, 2, 3, 4)，并且 expensiveCall 固定耗时 100ms。

代码执行时间线：

  1. 第一轮：分组并发

    • for 循环同步执行，遇到 1 和 2，调用 asyncAdd(1, 2)；遇到 3 和 4，调用 asyncAdd(3, 4)。
    • asyncAdd 内部调用了 expensiveCall。于是，Web APIs 里同时注册了两个 100ms 的定时器。
    • 同步代码走到 await Promise.all([p1, p2])。此时，sum 函数的执行被暂停，让出主线程。

  2. 等待与回调（100ms 后）

    • 100ms 到了，两个 setTimeout 的回调被推入宏任务队列。
    • Event Loop 依次执行这两个宏任务，分别调用了 resolve(3) 和 resolve(7)。
    • resolve 的调用触发了 Promise 状态改变，将后续操作推入微任务队列。

  3. 第二轮：递归合并

    • Promise.all 监控到所有的微任务都完成了，它自身的状态也变为 resolve，恢复 sum 函数的执行，拿到了结果 [3, 7]。
    • 此时进入下一层递归：return sum(3, 7)。
    • 重复上述过程，再次注册一个 100ms 的定时器。
    • 最终在 200ms 后得到结果 10。如果是串行相加（1+2=3, 3+3=6, 6+4=10），则需要 300ms。

核心意义：通过 Promise.all 这个微任务收集器，我们像一棵倒置的二叉树一样，把底层原本耗时极长的宏任务进行了“并行化”处理，大幅度压缩了总耗时。

理解了这套底层机制，你会发现很多框架的设计思路都与之息息相关。比如我们刚才聊到的微任务会在浏览器重新渲染（Repaint）之前执行完毕，这就保证了我们在微任务里处理的大量数据逻辑，不会导致页面出现中间状态的闪烁。

Css
Design mode
稳定运行
4年5月10天
Frame
Astro
SEO
Sitemap
订阅
RSS