🧮 算法数据结构

What is bubble sort? What is its basic idea?

考察点：冒泡排序原理。

答案：

冒泡排序是一种简单的排序算法。其基本思想是：通过多次遍历待排序的数组，每次比较相邻的两个元素，如果前一个比后一个大，则交换它们的位置。这样每一轮遍历后，最大的元素会“冒泡”到数组末尾。重复该过程，直到所有元素有序。

主要步骤：

1. 从头到尾依次比较相邻元素，较大的向后移动。
2. 每一轮结束后，未排序区间减少一个元素。
3. 重复上述过程，直到没有需要交换的元素。

复杂度分析：

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$
• 适合数据量较小的场景

How to implement array deduplication? What are the common methods?

考察点：数组去重方法。

答案：

数组去重是指将数组中重复的元素去除，只保留唯一值。常见实现方法有：

1. 利用 ES6 的 Set 结构：

   const arr = [1, 2, 2, 3, 1];
   const uniqueArr = [...new Set(arr)]; // [1, 2, 3]
   

2. 利用对象（哈希表）记录出现过的元素：

   function unique(arr) {
      const seen = {};
      return arr.filter(item => {
         if (seen[item]) return false;
         seen[item] = true;
         return true;
      });
   }
   // unique([1,2,2,3,1]) => [1,2,3]
   

3. 利用数组的 indexOf 或 includes 方法：

   function unique(arr) {
      const result = [];
      for (let i = 0; i < arr.length; i++) {
         if (result.indexOf(arr[i]) === -1) {
            result.push(arr[i]);
         }
      }
      return result;
   }
   

4. 利用 Array.prototype.filter 和 indexOf：

   arr.filter((item, index) => arr.indexOf(item) === index);
   

实际开发中推荐使用 Set，语法简洁且性能优越。复杂数据类型（如对象数组）去重可结合 Map 或自定义 key。

What is binary search? What scenarios is it suitable for?

考察点：二分查找应用。

答案：

二分查找是一种高效的查找算法，适用于有序数组或有序区间。其基本思想是：每次都将查找区间一分为二，通过比较中间元素与目标值的大小关系，决定下一步在左半区还是右半区继续查找，直到找到目标或区间为空。

主要步骤：

1. 设定左右指针，计算中间位置；
2. 比较中间值与目标值，若相等则返回结果；
3. 若目标值小于中间值，则右指针左移；反之左指针右移；
4. 重复上述过程，直到查找结束。

时间复杂度为 $O(\log n)$，空间复杂度为 $O(1)$。

适用场景：

• 有序数组、链表、区间查找；
• 查找某个元素是否存在；
• 查找第一个/最后一个满足条件的元素（如左/右边界）；
• 解决如“查找最小满足条件的值”、“查找最大不超过目标的值”等问题。

常见应用包括：有序数组查找、求解算法题中的上下界、前端分页、性能优化等。

How to reverse a string? What are the implementation methods?

考察点：字符串操作。

答案：

字符串反转是指将字符串中的字符顺序颠倒。常见实现方式有：

常见实现方法：

1. 利用内置方法：

   const str = "hello";
   const reversed = str.split("").reverse().join(""); // "olleh"
   

2. 使用循环遍历：

   function reverseString(str) {
     let result = "";
     for (let i = str.length - 1; i >= 0; i--) {
       result += str[i];
     }
     return result;
   }
   // reverseString("hello") => "olleh"
   

3. 递归实现：

   function reverseString(str) {
     if (str.length <= 1) return str;
     return reverseString(str.slice(1)) + str[0];
   }
   // reverseString("hello") => "olleh"
   

4. ES6扩展运算符：

   const str = "hello";
   const reversed = [...str].reverse().join(""); // "olleh"
   

性能对比：

• 内置方法：语法简洁，性能较好，推荐使用
• 循环遍历：适合需要手动处理字符的场景
• 递归实现：适合面试考察递归思想
• 扩展运算符：现代化写法，可读性好

实际应用：

• 字符串处理和格式化
• 回文检测的辅助功能
• 数据展示中的文本反转效果

What is recursion? What are the characteristics of recursive functions?

考察点：递归基本概念。

答案：

递归是一种算法思想，指函数在自身内部调用自身，通常用于解决可以分解为相同子问题的问题。

递归函数的特点：

1. 必须有明确的终止条件（递归出口），否则会无限调用导致栈溢出；
2. 每次调用时问题规模缩小，逐步逼近终止条件；
3. 递归过程通常包含“递归调用”和“返回结果”两个阶段；
4. 适合解决分治、树结构、回溯等问题。

经典例子：斐波那契数列、阶乘、二叉树遍历等。

示例：求阶乘

function factorial(n) {
   if (n === 0) return 1; // 终止条件
   return n * factorial(n - 1); // 递归调用
}
// factorial(5) => 120

实际开发中递归要注意出口条件和性能问题，部分场景可用循环或尾递归优化。

How to determine if an array is a palindrome?

考察点：回文判断方法。

答案：

回文数组是指正着和反着遍历元素顺序完全一致的数组。判断方法有：

1. 双指针法：分别从数组两端向中间遍历，比较对应元素是否相等。

   function isPalindrome(arr) {
      let left = 0, right = arr.length - 1;
      while (left < right) {
         if (arr[left] !== arr[right]) return false;
         left++;
         right--;
      }
      return true;
   }
   // isPalindrome([1,2,3,2,1]) => true
   // isPalindrome([1,2,3]) => false
   

2. 反转数组法：将数组反转后与原数组比较。

   function isPalindrome(arr) {
      return arr.join() === arr.slice().reverse().join();
   }
   

实际开发中推荐双指针法，空间复杂度低，适合大数组。回文判断常用于字符串、链表等场景。

What is selection sort? What are its core steps?

考察点：选择排序流程。

答案：

选择排序是一种简单直观的排序算法。其核心思想是：每一轮从未排序区间中选择最小（或最大）元素，放到已排序区间的末尾。

核心步骤：

1. 从数组起始位置开始，遍历未排序区间，找到最小值的索引；
2. 将最小值与当前轮起始位置元素交换；
3. 已排序区间右移一位，重复上述过程，直到所有元素有序。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

示例代码：

function selectionSort(arr) {
   for (let i = 0; i < arr.length - 1; i++) {
      let minIdx = i;
      for (let j = i + 1; j < arr.length; j++) {
         if (arr[j] < arr[minIdx]) minIdx = j;
      }
      if (minIdx !== i) {
         [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
      }
   }
   return arr;
}
// selectionSort([3,1,2]) => [1,2,3]

选择排序优点是实现简单，缺点是效率较低，适合数据量较小或对空间要求极高的场景。

How to merge two sorted arrays?

考察点：数组合并技巧。

答案：

合并两个有序数组，常用方法是双指针法。通过分别遍历两个数组，将较小元素依次放入结果数组，直到所有元素合并完成。

1. 双指针法：

   function mergeSorted(arr1, arr2) {
      let i = 0, j = 0, result = [];
      while (i < arr1.length && j < arr2.length) {
         if (arr1[i] < arr2[j]) {
            result.push(arr1[i++]);
         } else {
            result.push(arr2[j++]);
         }
      }
      // 合并剩余部分
      return result.concat(arr1.slice(i)).concat(arr2.slice(j));
   }
   // mergeSorted([1,3,5],[2,4,6]) => [1,2,3,4,5,6]
   

2. ES6简洁写法（合并后排序）：

   const merged = [...arr1, ...arr2].sort((a,b) => a-b);
   

实际开发中推荐双指针法，时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$，适合大数据量场景。合并有序数组常用于归并排序、分页等。

What is insertion sort? How does it differ from bubble sort?

考察点：插入排序特点。

答案：

插入排序是一种简单直观的排序算法。其基本思想是：将数组分为已排序区间和未排序区间，每次从未排序区间取出一个元素，插入到已排序区间的合适位置，使已排序区间始终有序。具体做法是：从第二个元素开始，依次与前面的元素比较，找到合适位置插入。

区别：

• 冒泡排序每轮通过相邻元素交换，把最大（或最小）元素“冒泡”到末尾，排序过程是不断交换；
• 插入排序每轮将当前元素插入到前面已排序区间的合适位置，排序过程是移动和插入。

插入排序适合数据量较小、部分有序的场景，时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。实际性能通常优于冒泡排序，尤其在数据基本有序时。

示例代码：

function insertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let key = arr[i], j = i - 1;
      while (j >= 0 && arr[j] > key) {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = key;
   }
   return arr;
}
// insertionSort([3,1,2]) => [1,2,3]

How to find the maximum and minimum values in an array?

考察点：数组遍历。

答案：

查找数组中的最大值和最小值，最常用的方法是遍历数组，依次比较每个元素。

1. 循环遍历法：

function findMaxMin(arr) {
   let max = arr[0], min = arr[0];
   for (let i = 1; i < arr.length; i++) {
      if (arr[i] > max) max = arr[i];
      if (arr[i] < min) min = arr[i];
   }
   return { max, min };
}
// findMaxMin([3, 1, 5, 2]) => { max: 5, min: 1 }

2. 使用 ES6 内置方法：

const arr = [3, 1, 5, 2];
const max = Math.max(...arr);
const min = Math.min(...arr);
// max = 5, min = 1

实际开发中推荐使用内置方法，语法简洁；循环遍历适合需要同时处理其他逻辑或兼容性要求的场景。时间复杂度均为 $O(n)$，空间复杂度为 $O(1)$。

What is time complexity? How to measure algorithm efficiency?
- 考察点：算法复杂度基础。
答案：
时间复杂度是衡量算法运行时间随输入规模增长的变化趋势，通常用大O符号表示（如 $O(1)$、$O(n)$、$O(n^2)$）。它反映了算法在最坏、平均或最好情况下的执行效率。

衡量算法效率常用指标：

1. 时间复杂度：描述算法执行所需的基本操作次数，关注增长趋势而非具体耗时。
2. 空间复杂度：描述算法运行过程中额外占用的内存空间。

常见时间复杂度：

• $O(1)$：常数时间，如直接访问数组元素；
• $O(n)$：线性时间，如遍历数组；
• $O(n^2)$：平方时间，如双重循环排序；
• $O(
  log n)$：对数时间，如二分查找。

算法效率衡量方法：

• 通过分析代码中的循环、递归、分支等结构，统计基本操作次数；
• 忽略常数和低阶项，只关注主导项；
• 比较不同算法的复杂度，选择更优方案。

实际开发中，时间复杂度是评估算法性能的重要依据，尤其在大数据量或高性能场景下。空间复杂度也需关注，避免内存浪费。

What are deep copy and shallow copy? How to distinguish them?

考察点：拷贝机制基础。

答案：

浅拷贝是指只复制对象的第一层属性，如果属性是引用类型（如对象、数组），则只复制引用地址，原始对象和新对象会共享同一块内存。深拷贝则是递归复制所有层级的数据，新对象与原对象完全独立，互不影响。

区分方法：

• 浅拷贝：修改嵌套对象会影响原对象。
• 深拷贝：修改嵌套对象不会影响原对象。

常见实现方式：

1. 浅拷贝：

// 对象
const obj = { a: 1, b: { c: 2 } };
const shallow = Object.assign({}, obj);
// 或
const shallow2 = { ...obj };

2. 深拷贝：

// 简单对象/数组
const deep = JSON.parse(JSON.stringify(obj));
// 递归实现
function deepClone(obj) {
   if (obj === null || typeof obj !== 'object') return obj;
   const result = Array.isArray(obj) ? [] : {};
   for (let key in obj) {
      if (obj.hasOwnProperty(key)) {
         result[key] = deepClone(obj[key]);
      }
   }
   return result;
}

注意：JSON 方法不支持函数、undefined、循环引用等特殊情况。实际开发中可用第三方库如 lodash 的 _.cloneDeep。

How to traverse a DOM tree? What are the common methods?

考察点：DOM树遍历。

答案：

遍历DOM树常用的方法有递归遍历和迭代遍历。DOM树本质是一个多叉树结构，可以通过递归或循环访问每个节点。

1. 递归遍历：

function traverse(node) {
   if (!node) return;
   // 处理当前节点
   console.log(node.tagName);
   // 遍历子节点
   for (let i = 0; i < node.children.length; i++) {
      traverse(node.children[i]);
   }
}
// traverse(document.body);

2. 迭代遍历（广度优先）：

function bfsTraverse(root) {
   const queue = [root];
   while (queue.length) {
      const node = queue.shift();
      console.log(node.tagName);
      for (let i = 0; i < node.children.length; i++) {
         queue.push(node.children[i]);
      }
   }
}
// bfsTraverse(document.body);

3. 原生API：

• Element.childNodes、Element.children 可遍历子节点；
• TreeWalker、NodeIterator 可按需遍历特定类型节点。

实际开发中递归遍历适合深度优先，迭代遍历适合广度优先。可根据需求选择合适方式。

How to convert an array of objects into a tree structure?

考察点：数据结构转换。

答案：

对象数组转树形结构，常见于菜单、分类、组织架构等场景。一般对象包含 id、parentId 字段，通过遍历和映射实现父子关系。

常见实现方法：

1. 使用哈希表辅助：

function arrayToTree(arr) {
   const map = {};
   const result = [];
   arr.forEach(item => {
      map[item.id] = { ...item, children: [] };
   });
   arr.forEach(item => {
      const node = map[item.id];
      if (item.parentId) {
         map[item.parentId].children.push(node);
      } else {
         result.push(node);
      }
   });
   return result;
}
// 示例数据
const arr = [
   { id: 1, parentId: null, name: 'A' },
   { id: 2, parentId: 1, name: 'B' },
   { id: 3, parentId: 1, name: 'C' },
   { id: 4, parentId: 2, name: 'D' }
];
// arrayToTree(arr)

2. 递归法：适合数据量较小或需要自定义处理时。

实际开发中推荐哈希表法，时间复杂度为 $O(n)$，高效且易维护。

What is a hash table? What are its applications in front-end development?

考察点：哈希表基础。

答案：

哈希表是一种通过哈希函数将键映射到数组下标，实现高效查找、插入和删除的数据结构。常见实现有对象（Object）、Map、Set 等。

特点：

• 查找、插入、删除操作平均时间复杂度为 $O(1)$；
• 适合存储键值对，快速定位数据。

前端常见应用：

1. 数据去重：利用对象或 Set 记录已出现元素，实现数组去重。
2. 统计频次：如统计字符串/数组中每个元素出现次数。
3. 缓存设计：如 LRU 缓存、接口数据缓存，提升性能。
4. 快速查找：如根据 id 查找对象、字典映射、路由表。
5. 权限管理、配置映射：如角色权限、菜单配置等。

示例：统计字符出现次数

function countChars(str) {
   const map = {};
   for (const ch of str) {
      map[ch] = (map[ch] || 0) + 1;
   }
   return map;
}
// countChars('aabbc') => { a: 2, b: 2, c: 1 }

实际开发中推荐使用 Map/Set，语法更灵活，支持任意类型键。

How to determine if an object is empty?

考察点：对象判空方法。

答案：

判断对象是否为空，常见方法有：

1. 使用 Object.keys：

function isEmpty(obj) {
   return Object.keys(obj).length === 0;
}
// isEmpty({}) => true
// isEmpty({a:1}) => false

2. 使用 for…in 循环：

function isEmpty(obj) {
   for (let key in obj) {
      if (obj.hasOwnProperty(key)) return false;
   }
   return true;
}

3. ES2020 Object.entries/Object.values：

Object.entries(obj).length === 0
Object.values(obj).length === 0

注意：判空只针对普通对象，不适用于数组、null、undefined 等。实际开发中推荐使用 Object.keys 方法，语法简洁且兼容性好。

What is the difference between recursion and iteration?

考察点：算法思想对比。

答案：

递归和迭代是两种常见的算法实现方式：

• 递归：函数在自身内部调用自身，通常用于解决可分解为相同子问题的问题。需要有终止条件，否则会导致栈溢出。
• 迭代：通过循环结构（如 for、while）重复执行操作，直到满足条件为止。

区别：

1. 递归更适合处理树结构、分治、回溯等问题，代码简洁但可能带来性能和栈空间消耗。
2. 迭代适合线性、顺序处理，效率高，空间消耗低。
3. 递归实现通常更直观，迭代更易于优化和控制。

示例：斐波那契数列

// 递归实现
function fib(n) {
   if (n <= 1) return n;
   return fib(n - 1) + fib(n - 2);
}

// 迭代实现
function fibIter(n) {
   if (n <= 1) return n;
   let a = 0, b = 1;
   for (let i = 2; i <= n; i++) {
      [a, b] = [b, a + b];
   }
   return b;
}

实际开发中，优先考虑迭代实现，递归适合表达复杂结构或考察递归思想。

How to count the occurrences of each character in a string?

考察点：字符统计方法。

答案：

统计字符串中每个字符出现的次数，常用方法是遍历字符串，利用对象（哈希表）记录每个字符的出现次数。

示例代码：

function countChars(str) {
   const map = {};
   for (const ch of str) {
      map[ch] = (map[ch] || 0) + 1;
   }
   return map;
}
// countChars('aabbc') => { a: 2, b: 2, c: 1 }

也可用 Map 实现：

function countChars(str) {
   const map = new Map();
   for (const ch of str) {
      map.set(ch, (map.get(ch) || 0) + 1);
   }
   return map;
}
// countChars('aabbc') => Map { 'a' => 2, 'b' => 2, 'c' => 1 }

时间复杂度为 $O(n)$，空间复杂度为 $O(k)$（k为字符种类数）。实际开发中推荐对象或 Map，语法简洁且高效。

What is the core idea of quick sort? How to implement it?

考察点：快速排序原理。

答案：

快速排序是一种分治思想的高效排序算法。核心思想是：每次从数组中选择一个“基准”元素，将数组分为左右两部分，左边都比基准小，右边都比基准大，然后递归地对左右两部分继续排序，最终整个数组有序。

主要步骤：

1. 选择基准元素（通常选第一个或随机一个）；
2. 将数组分为小于基准和大于基准的两部分；
3. 递归排序左右两部分；
4. 合并结果。

时间复杂度：平均 $O(n\log n)$，最坏 $O(n^2)$，空间复杂度 $O(\log n)$（递归栈）。

示例代码：

function quickSort(arr) {
   if (arr.length <= 1) return arr;
   const pivot = arr[0];
   const left = arr.slice(1).filter(x => x < pivot);
   const right = arr.slice(1).filter(x => x >= pivot);
   return [...quickSort(left), pivot, ...quickSort(right)];
}
// quickSort([3,1,4,2]) => [1,2,3,4]

实际开发中可用原地分区法优化空间复杂度。快速排序适合大数据量场景，是实际应用最广泛的排序算法之一。

What types of data is merge sort suitable for processing?

考察点：归并排序应用。

答案：

归并排序是一种稳定、高效的排序算法，特别适合处理以下类型的数据：

1. 大规模数据：归并排序的时间复杂度为 $O(n\log n)$，在数据量很大时依然能保持较高效率。
2. 链表结构：归并排序不依赖随机访问，适合链表等顺序存储结构，能避免频繁移动节点。
3. 外部排序：当数据量大到无法全部加载到内存时，归并排序可分块处理，适合磁盘等外部存储排序。
4. 需要稳定排序的场景：归并排序是稳定排序，能保证相等元素的原始顺序。

优缺点：

• 优点：稳定、时间复杂度低、适合大数据和链表。
• 缺点：空间复杂度较高（数组实现时为 $O(n)$），不适合内存极度受限场景。

代码示例（数组版）：

function mergeSort(arr) {
   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, right) {
   const result = [];
   let i = 0, 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.concat(left.slice(i)).concat(right.slice(j));
}
// mergeSort([3,1,4,2]) => [1,2,3,4]

实际应用：

• 大型文件排序、日志归并、链表排序、分布式数据归并等。
• 前端分页、数据分块处理、需要稳定排序的业务场景。

How to implement linked list reversal? What are the common methods?

考察点：链表操作。

答案：

链表反转是面试常见题，主要有两种实现方式：迭代法和递归法。

1. 迭代法（推荐）：通过三个指针依次遍历链表，将每个节点的 next 指向前一个节点。

function reverseList(head) {
   let prev = null, curr = head;
   while (curr) {
      const next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
   }
   return prev;
}
// 适用于单链表，时间复杂度 O(n)，空间复杂度 O(1)

2. 递归法：递归到链表尾部，逐步反转指向。

function reverseList(head) {
   if (!head || !head.next) return head;
   const newHead = reverseList(head.next);
   head.next.next = head;
   head.next = null;
   return newHead;
}
// 递归法空间复杂度 O(n)（递归栈），适合理解递归思想

常见变体：

• 双向链表反转：需同时处理 prev 和 next 指针。
• 部分反转：如反转链表的前 k 个节点或区间反转。

实际应用：

• 链表反转常用于算法题、数据结构处理、前端虚拟列表等。
• 推荐迭代法，代码简洁且空间效率高。

How to implement string permutation?

考察点：全排列算法实现。

答案：

字符串全排列是经典回溯算法题，常见实现方式为递归回溯。

1. 递归回溯法（推荐）：通过交换或标记已使用字符，递归生成所有排列。

function permute(str) {
   const res = [];
   const arr = str.split("");
   const used = Array(arr.length).fill(false);
   function backtrack(path) {
      if (path.length === arr.length) {
         res.push(path.join(""));
         return;
      }
      for (let i = 0; i < arr.length; i++) {
         if (used[i]) continue;
         used[i] = true;
         path.push(arr[i]);
         backtrack(path);
         path.pop();
         used[i] = false;
      }
   }
   backtrack([]);
   return res;
}
// permute("abc") => ["abc", "acb", "bac", "bca", "cab", "cba"]
// 时间复杂度 O(n!)，空间复杂度 O(n)

2. 交换法（原地递归）：通过交换字符位置，递归生成排列。

function permute(str) {
   const res = [];
   const arr = str.split("");
   function dfs(index) {
      if (index === arr.length - 1) {
         res.push(arr.join(""));
         return;
      }
      for (let i = index; i < arr.length; i++) {
         [arr[index], arr[i]] = [arr[i], arr[index]];
         dfs(index + 1);
         [arr[index], arr[i]] = [arr[i], arr[index]];
      }
   }
   dfs(0);
   return res;
}
// permute("abc") => ["abc", "acb", "bac", "bca", "cab", "cba"]
// 适合原地操作，空间复杂度更优

常见变体：

• 含重复字符的全排列：需去重，可用排序+剪枝或Set辅助。
• 数组全排列、对象属性全排列等。

实际应用：

• 全排列常用于组合、搜索、密码破解、前端组件排列等。
• 推荐递归回溯法，代码易理解，扩展性强。

How to determine if two strings are anagrams?

考察点：异位词判断。

答案：

异位词（Anagram）是指两个字符串包含的字符及出现次数完全相同，但顺序不同。

1. 排序法（推荐）：将两个字符串排序后比较是否相等。

function isAnagram(s, t) {
   return s.split("").sort().join("") === t.split("").sort().join("");
}
// isAnagram("abc", "bca") => true
// isAnagram("aab", "abb") => false
// 时间复杂度 O(nlogn)，空间复杂度 O(n)

2. 哈希计数法：统计每个字符出现次数，最后比较计数是否一致。

function isAnagram(s, t) {
   if (s.length !== t.length) return false;
   const count = {};
   for (const ch of s) {
      count[ch] = (count[ch] || 0) + 1;
   }
   for (const ch of t) {
      if (!count[ch]) return false;
      count[ch]--;
   }
   return Object.values(count).every(v => v === 0);
}
// isAnagram("abc", "bca") => true
// isAnagram("aab", "abb") => false
// 时间复杂度 O(n)，空间复杂度 O(k)

常见变体：

• 判断多个字符串是否互为异位词。
• 支持 Unicode 字符、区分大小写等。

实际应用：

• 异位词判断常用于字符串处理、数据去重、前端搜索优化等。
• 推荐排序法，代码简洁；哈希法适合大数据或需高性能场景。

What is the basic principle of LRU cache algorithm?

考察点：LRU算法机制。

答案：
LRU（Least Recently Used，最近最少使用）缓存是一种常见的淘汰策略，用于在空间有限时优先移除最久未被访问的数据。

核心思想：

• 每次访问或插入数据时，将其标记为“最近使用”；
• 当缓存满时，移除“最久未使用”的数据。

常见实现方式：

1. 哈希表 + 双向链表（推荐）：哈希表用于 O(1) 查找，双向链表维护访问顺序。

class LRUCache {
   constructor(capacity) {
      this.capacity = capacity;
      this.map = new Map();
   }
   get(key) {
      if (!this.map.has(key)) return -1;
      const value = this.map.get(key);
      this.map.delete(key);
      this.map.set(key, value); // 重新插入，变为最新
      return value;
   }
   put(key, value) {
      if (this.map.has(key)) this.map.delete(key);
      this.map.set(key, value);
      if (this.map.size > this.capacity) {
         // 移除最旧的
         const oldestKey = this.map.keys().next().value;
         this.map.delete(oldestKey);
      }
   }
}
// let cache = new LRUCache(2);
// cache.put(1,1); cache.put(2,2); cache.get(1); cache.put(3,3);
// 时间复杂度 O(1)，空间复杂度 O(n)

2. 数组实现（仅适合小容量）：每次访问移动元素，插入时判断容量。

常见变体：

• LFU（最不经常使用）、FIFO（先进先出）等其他缓存淘汰策略。
• 支持异步淘汰、分布式缓存等。

实际应用：

• LRU广泛用于浏览器缓存、图片资源管理、前端虚拟列表、接口数据缓存等。
• 推荐哈希表+链表实现，性能高且易扩展。

How to implement array random shuffling?

考察点：洗牌算法。

答案：

数组随机洗牌常用算法是“Fisher-Yates 洗牌算法”，可高效生成均匀分布的随机排列。

1. Fisher-Yates 洗牌（推荐）：从后往前遍历，每次随机选一个位置交换。

function shuffle(arr) {
   for (let i = arr.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [arr[i], arr[j]] = [arr[j], arr[i]];
   }
   return arr;
}
// shuffle([1,2,3,4]) => [2,4,1,3]（结果随机）
// 时间复杂度 O(n)，空间复杂度 O(1)

2. 排序法（不推荐）：用 sort + Math.random()，但分布不均匀。

arr.sort(() => Math.random() - 0.5);
// 仅适合小数据量或非严格场景

常见变体：

• 洗牌后抽取前 k 个元素（洗牌抽样）。
• 多维数组洗牌、对象数组洗牌等。

实际应用：

• 随机抽奖、游戏洗牌、前端数据随机展示等。
• 推荐 Fisher-Yates 算法，结果均匀且高效。

What are the differences between preorder, inorder, and postorder traversal of binary trees?

考察点：树遍历方式。

答案：

二叉树遍历分为前序、中序、后序三种方式，区别在于访问节点的顺序。

1. 前序遍历（Preorder）：先访问根节点，再遍历左子树，最后遍历右子树。

   • 访问顺序：根 → 左 → 右
   • 代码示例：

   function preorder(root) {
      if (!root) return;
      console.log(root.val);
      preorder(root.left);
      preorder(root.right);
   }
   

2. 中序遍历（Inorder）：先遍历左子树，再访问根节点，最后遍历右子树。

   • 访问顺序：左 → 根 → 右
   • 代码示例：

   function inorder(root) {
      if (!root) return;
      inorder(root.left);
      console.log(root.val);
      inorder(root.right);
   }
   

3. 后序遍历（Postorder）：先遍历左子树，再遍历右子树，最后访问根节点。

   • 访问顺序：左 → 右 → 根
   • 代码示例：

   function postorder(root) {
      if (!root) return;
      postorder(root.left);
      postorder(root.right);
      console.log(root.val);
   }
   

区别总结：

• 前序适合用于复制树结构、表达式树前缀遍历。
• 中序常用于二叉搜索树（BST）升序输出所有节点。
• 后序适合用于删除树结构、表达式树后缀遍历。

实际应用：

• 遍历方式选择取决于具体业务需求，如序列化/反序列化、表达式计算、结构操作等。
• 三种遍历均可递归或迭代实现，递归代码更简洁，迭代适合大树或需控制栈空间场景。

How to implement throttling and debouncing? What are their applicable scenarios?

考察点：节流防抖原理。

答案：

节流（throttle）和防抖（debounce）是前端高频事件优化常用技术。

1. 防抖（debounce）：事件触发后，只有在指定时间内未再次触发，才执行一次。

   • 适合输入框实时搜索、窗口 resize、表单验证等场景。
   • 代码实现：

   function debounce(fn, delay) {
      let timer = null;
      return function(...args) {
         clearTimeout(timer);
         timer = setTimeout(() => fn.apply(this, args), delay);
      };
   }
   // 用法：window.addEventListener('resize', debounce(fn, 300));
   

2. 节流（throttle）：事件触发后，规定时间内只执行一次。

   • 适合滚动监听、页面滚动加载、动画、拖拽等场景。
   • 代码实现：

   function throttle(fn, delay) {
      let last = 0;
      return function(...args) {
         const now = Date.now();
         if (now - last > delay) {
            last = now;
            fn.apply(this, args);
         }
      };
   }
   // 用法：window.addEventListener('scroll', throttle(fn, 200));
   

区别总结：

• 防抖：高频触发只执行最后一次，适合输入、搜索等场景。
• 节流：高频触发按间隔执行，适合滚动、动画等场景。

实际应用：

• 优化性能，减少无效请求和渲染。
• 推荐根据业务场景选择合适方案，防抖适合输入类，节流适合滚动类。

What are the differences between dynamic programming and divide-and-conquer algorithms?

考察点：算法思想对比。

答案：

动态规划（DP）和分治算法（Divide and Conquer）都是常见的算法思想，核心区别在于子问题之间的关系和解题方式。

1. 分治算法：将大问题拆分为若干独立的子问题，分别求解后合并结果。

   • 子问题之间互不影响，无重叠。
   • 典型应用：归并排序、快速排序、二分查找、树形递归等。
   • 代码示例：

   // 归并排序
   function mergeSort(arr) {
      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);
   }
   

2. 动态规划：将大问题拆分为有重叠的子问题，通过保存子问题结果（记忆化或表格），避免重复计算。

   • 子问题之间有重叠，需保存和复用。
   • 典型应用：斐波那契数列、背包问题、最长公共子序列、路径规划等。
   • 代码示例：

   // 斐波那契数列（DP版）
   function fib(n) {
      if (n <= 1) return n;
      const dp = [0, 1];
      for (let i = 2; i <= n; i++) {
         dp[i] = dp[i - 1] + dp[i - 2];
      }
      return dp[n];
   }
   

区别总结：

• 分治适合无重叠子问题，递归拆分、合并结果。
• 动态规划适合有重叠子问题，通过保存结果提升效率。
• 分治空间复杂度低，动态规划时间效率高但空间消耗大。

实际应用：

• 分治常用于排序、查找、树结构等。
• 动态规划常用于最优解、计数、路径等问题。
• 面试中需根据问题特性选择合适思想。

How to detect if there is a cycle in a linked list?

考察点：链表环检测。

答案：

判断链表是否有环，最常用的方法是快慢指针法（Floyd判圈算法），也可用哈希表辅助。

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;
}
// 时间复杂度 O(n)，空间复杂度 O(1)

2. 哈希表法：遍历链表，用哈希表记录已访问节点。如果遇到已访问过的节点，则有环。

function hasCycle(head) {
   const visited = new Set();
   let curr = head;
   while (curr) {
      if (visited.has(curr)) return true;
      visited.add(curr);
      curr = curr.next;
   }
   return false;
}
// 时间复杂度 O(n)，空间复杂度 O(n)

常见变体：

• 找到环的入口节点：快慢指针相遇后，慢指针回到头部，两个指针每次走一步，再次相遇即为环入口。
• 计算环的长度：快慢指针相遇后，继续遍历直到再次相遇，统计步数即为环长度。

实际应用：

• 链表环检测常用于内存泄漏排查、数据结构安全性校验、面试算法题。
• 推荐快慢指针法，空间效率高，代码简洁。

What problems are greedy algorithms suitable for solving?

考察点：贪心算法应用。

答案：

贪心算法是一种在每一步选择中都采取当前最优（最有利）策略的算法思想，期望通过局部最优达到全局最优。贪心算法适合解决具有“贪心选择性质”和“最优子结构”的问题。

典型应用场景：

1. 区间调度/活动选择问题：如会议室安排、最大不重叠区间数量。
2. 最小生成树：如 Kruskal、Prim 算法。
3. 哈夫曼编码：构建最优前缀编码树。
4. 零钱兑换问题（部分场景）：如硬币面值满足贪心性质时。
5. 分配资源/任务调度：如分糖果、分配工作。
6. 区间覆盖、跳跃游戏、加油站问题等。

代码示例：区间调度问题（选最多不重叠区间）

function maxNonOverlap(intervals) {
   intervals.sort((a, b) => a[1] - b[1]); // 按结束时间升序
   let count = 0, end = -Infinity;
   for (const [start, finish] of intervals) {
      if (start >= end) {
         count++;
         end = finish;
      }
   }
   return count;
}
// 时间复杂度 O(nlogn)，空间复杂度 O(1)

贪心算法的特点：

• 每一步都做出当前最优选择，不回溯。
• 适用于问题满足贪心选择性质和最优子结构。
• 不一定总能得到全局最优解，需证明贪心策略的正确性。

常见变体：

• 最短路径问题（如 Dijkstra 算法，部分场景可用贪心）。
• 区间覆盖、跳跃游戏、加油站问题等。

实际应用：

• 贪心算法广泛用于调度、编码、资源分配、前端布局优化等。
• 面试中常见如区间调度、分配任务、字符串拼接等。
• 推荐在问题满足贪心性质时优先考虑，代码简洁高效。

How to implement a simple priority queue?

考察点：队列结构。

答案：

优先队列是一种特殊的队列结构，出队时总是优先返回“优先级最高”的元素。常见实现方式有数组排序和二叉堆。

1. 数组排序实现（适合小数据量）：每次插入后排序，出队时取首元素。

class PriorityQueue {
   constructor(compare) {
      this.data = [];
      this.compare = compare || ((a, b) => b - a); // 默认大顶堆
   }
   enqueue(item) {
      this.data.push(item);
      this.data.sort(this.compare); // 保证优先级顺序
   }
   dequeue() {
      return this.data.shift(); // 取优先级最高的元素
   }
   peek() {
      return this.data[0];
   }
   size() {
      return this.data.length;
   }
}
// let pq = new PriorityQueue(); pq.enqueue(3); pq.enqueue(1); pq.enqueue(5); pq.dequeue(); // 5
// 时间复杂度：插入 O(nlogn)，出队 O(1)

2. 二叉堆实现（推荐，适合大数据量）：用堆结构维护优先级，插入和删除均为 O(log n)。

class HeapPriorityQueue {
   constructor(compare) {
      this.data = [];
      this.compare = compare || ((a, b) => b - a); // 默认大顶堆
   }
   enqueue(item) {
      this.data.push(item);
      this._siftUp(this.data.length - 1);
   }
   dequeue() {
      if (this.data.length === 0) return undefined;
      const top = this.data[0];
      const last = this.data.pop();
      if (this.data.length) {
         this.data[0] = last;
         this._siftDown(0);
      }
      return top;
   }
   peek() {
      return this.data[0];
   }
   size() {
      return this.data.length;
   }
   _siftUp(idx) {
      while (idx > 0) {
         const parent = Math.floor((idx - 1) / 2);
         if (this.compare(this.data[idx], this.data[parent]) > 0) {
            [this.data[idx], this.data[parent]] = [this.data[parent], this.data[idx]];
            idx = parent;
         } else break;
      }
   }
   _siftDown(idx) {
      const n = this.data.length;
      while (true) {
         let largest = idx;
         const left = 2 * idx + 1, right = 2 * idx + 2;
         if (left < n && this.compare(this.data[left], this.data[largest]) > 0) largest = left;
         if (right < n && this.compare(this.data[right], this.data[largest]) > 0) largest = right;
         if (largest !== idx) {
            [this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
            idx = largest;
         } else break;
      }
   }
}
// let pq = new HeapPriorityQueue(); pq.enqueue(3); pq.enqueue(1); pq.enqueue(5); pq.dequeue(); // 5
// 时间复杂度：插入/出队均为 O(log n)

常见变体：

• 支持自定义优先级（如任务调度、事件队列）。
• 最小优先队列（小顶堆）、最大优先队列（大顶堆）。

实际应用：

• 优先队列广泛用于任务调度、事件驱动、A*搜索、定时器、前端动画、数据流合并等。
• 推荐二叉堆实现，性能高且易扩展。

What are the string matching algorithms? What are their advantages and disadvantages?

考察点：字符串匹配。

答案：

字符串匹配算法用于在主串中查找子串，常见算法有：

1. 暴力匹配（Brute Force）

   • 思路：主串每个位置都尝试与子串逐字符比较。
   • 优点：实现简单，易理解。
   • 缺点：效率低，最坏时间复杂度 $O(mn)$（m为主串长度，n为模式串长度）。
   • 代码示例：

   function bruteForce(str, pattern) {
      for (let i = 0; i <= str.length - pattern.length; i++) {
         let j = 0;
         while (j < pattern.length && str[i + j] === pattern[j]) j++;
         if (j === pattern.length) return i;
      }
      return -1;
   }
   // bruteForce('abcdef', 'cd') => 2
   

2. KMP算法（Knuth-Morris-Pratt）

   • 思路：利用部分匹配表（next数组）跳过已匹配的字符，避免重复比较。
   • 优点：最坏时间复杂度 $O(m+n)$，适合大数据量和多次匹配场景。
   • 缺点：实现复杂，需构建next数组。
   • 代码示例：

   function kmp(str, pattern) {
      function getNext(p) {
         const next = Array(p.length).fill(0);
         let j = 0;
         for (let i = 1; i < p.length; i++) {
            while (j > 0 && p[i] !== p[j]) j = next[j - 1];
            if (p[i] === p[j]) j++;
            next[i] = j;
         }
         return next;
      }
      const next = getNext(pattern);
      let j = 0;
      for (let i = 0; i < str.length; i++) {
         while (j > 0 && str[i] !== pattern[j]) j = next[j - 1];
         if (str[i] === pattern[j]) j++;
         if (j === pattern.length) return i - j + 1;
      }
      return -1;
   }
   // kmp('abcdef', 'cd') => 2
   

3. Boyer-Moore算法

   • 思路：从模式串末尾开始匹配，利用坏字符规则和好后缀规则大步跳跃。
   • 优点：实际效率极高，适合长主串和复杂模式。
   • 缺点：实现复杂，需构建多种跳跃表。
   • 时间复杂度：最坏 $O(mn)$，平均远优于暴力法。

4. Rabin-Karp算法

   • 思路：用哈希值快速判断子串是否可能匹配，哈希冲突时再逐字符比较。
   • 优点：适合多模式串匹配，平均时间复杂度 $O(m+n)$。
   • 缺点：哈希冲突可能导致最坏 $O(mn)$，需设计高效哈希函数。

优缺点总结：

• 暴力法：实现最简单，效率最低。
• KMP：效率高，适合多次匹配，代码复杂。
• Boyer-Moore：实际效率极高，适合长串，代码复杂。
• Rabin-Karp：适合多模式串，哈希冲突需处理。

实际应用：

• 文本编辑器查找、前端搜索、敏感词过滤、日志分析等。
• 前端常用 indexOf、includes、正则表达式等内置方法，底层多用KMP或Boyer-Moore优化。

How to implement large number addition? What are the common scenarios?

考察点：大数运算。

答案：

大数相加是指对超出语言数值范围的两个大整数进行加法运算，常见于金融、区块链、科学计算等场景。原理是模拟手工加法，从最低位逐位相加，处理进位。

实现方法：

1. 字符串模拟加法（推荐）

function addBigNumber(a, b) {
   let i = a.length - 1, j = b.length - 1, carry = 0, res = '';
   while (i >= 0 || j >= 0 || carry) {
      const x = i >= 0 ? +a[i] : 0;
      const y = j >= 0 ? +b[j] : 0;
      const sum = x + y + carry;
      res = (sum % 10) + res;
      carry = Math.floor(sum / 10);
      i--; j--;
   }
   return res;
}
// addBigNumber('12345678901234567890', '98765432109876543210') => '111111111011111111100'
// 时间复杂度 O(n)，空间复杂度 O(n)

2. 数组模拟加法：将字符串转为数组，逆序遍历，适合处理更复杂的大数运算。

常见场景：

• 金融、支付、区块链等需要高精度运算的场景。
• 科学计算、天文、密码学等超大数值处理。
• 前端处理超长订单号、ID、验证码等。

常见变体：

• 大数减法、乘法、除法、幂运算。
• 支持负数、浮点数、进制转换等。

实际应用：

• 前端常用字符串或数组模拟大数运算，后端可用大数库（如 BigInt、bignumber.js）。
• 推荐字符串逆序遍历，代码简洁且易扩展。

How to implement virtual scrolling for front-end lists?

考察点：虚拟滚动原理。

答案：

虚拟滚动（Virtual Scrolling）是一种前端性能优化技术，适用于渲染超长列表时只显示可视区域内的少量元素，显著减少 DOM 数量和内存消耗。

核心原理：

• 只渲染当前可视区域的列表项，未显示部分不渲染或用占位元素代替。
• 通过计算滚动位置，动态更新可视区数据和偏移量。
• 保持滚动条长度与真实列表一致，用户体验无差异。

实现思路：

1. 计算可视区能显示的元素数量（如 height / itemHeight）。
2. 监听滚动事件，计算当前起始索引和结束索引。
3. 只渲染当前区间的数据，顶部和底部用空白占位撑开总高度。

代码示例（简化版）：

// 假设每项高度固定 itemHeight
function getVisibleData(list, scrollTop, itemHeight, visibleCount) {
   const start = Math.floor(scrollTop / itemHeight);
   const end = start + visibleCount;
   return list.slice(start, end);
}
// React/Vue 通用思路
// <div style={{height: totalHeight}}>
//   <div style={{height: start * itemHeight}}></div>
//   {visibleData.map(...)}
//   <div style={{height: (list.length - end) * itemHeight}}></div>
// </div>

复杂度分析：

• 渲染复杂度 $O(k)$（k为可视区元素数），远优于 $O(n)$。
• 滚动事件处理为 $O(1)$，内存消耗极低。

常见场景：

• 超长列表、表格、聊天记录、日志、文件管理等。
• 前端组件库如 Element、Ant Design、React-Virtualized、Vue-Virtual-Scroller 等均有虚拟滚动实现。

常见变体：

• 动态高度虚拟列表：需提前测量或缓存每项高度。
• 横向虚拟滚动、虚拟表格、无限滚动加载等。

实际应用：

• 虚拟滚动显著提升前端性能，适合大数据量渲染。
• 推荐结合组件库或自定义实现，注意滚动体验和兼容性。

How to implement a quick sort by hand? What boundary cases should be considered?

考察点：算法实现与边界处理。

答案：

快速排序是一种分治思想的高效排序算法。核心思想是选定一个“基准”元素，将数组分为小于和大于基准的两部分，递归排序后合并。

手写实现（原地分区法，推荐）：

function quickSort(arr, left = 0, right = arr.length - 1) {
   if (left >= right) return;
   let pivot = arr[left], i = left, j = right;
   while (i < j) {
      while (i < j && arr[j] >= pivot) j--;
      arr[i] = arr[j];
      while (i < j && arr[i] <= pivot) i++;
      arr[j] = arr[i];
   }
   arr[i] = pivot;
   quickSort(arr, left, i - 1);
   quickSort(arr, i + 1, right);
}
// let arr = [3,1,4,2]; quickSort(arr); // arr => [1,2,3,4]
// 时间复杂度：平均 O(nlogn)，最坏 O(n^2)
// 空间复杂度：O(logn)（递归栈）

边界情况注意点：

1. 数组为空或只有一个元素时直接返回。
2. 基准选择不当（如总选最大/最小）会退化为 O(n^2)，可随机选基准优化。
3. 有重复元素时，分区要保证不会死循环。
4. 递归出口条件要写对，避免无限递归。
5. 原地分区法需注意索引越界和赋值顺序。

实际应用：

• 快速排序适合大数据量场景，是实际应用最广泛的排序算法之一。
• 前端数组排序、数据处理、分页等常用。
• 推荐原地分区法，空间效率高，注意边界处理和递归出口。

How to implement a Trie data structure? What application scenarios is it suitable for?

考察点：高级数据结构。

答案：

Trie（字典树/前缀树）是一种用于高效存储和查找字符串集合的数据结构，特别适合前缀相关的查询。

核心原理：

• 每个节点代表一个字符，根节点为空。
• 从根到某节点的路径组成一个前缀。
• 每个节点可有多个子节点，通常用对象或数组存储。
• 通过标记节点是否为单词结尾，实现完整单词的查找。

基本操作：

1. 插入（insert）：逐字符遍历，若无则新建节点，最后标记单词结尾。
2. 查找（search）：逐字符查找，最后判断是否为单词结尾。
3. 前缀查找（startsWith）：逐字符查找，只需判断路径是否存在。

代码示例（JS版）：

class Trie {
   constructor() {
      this.children = {};
      this.isEnd = false;
   }
   insert(word) {
      let node = this;
      for (const ch of word) {
         if (!node.children[ch]) node.children[ch] = new Trie();
         node = node.children[ch];
      }
      node.isEnd = true;
   }
   search(word) {
      let node = this;
      for (const ch of word) {
         if (!node.children[ch]) return false;
         node = node.children[ch];
      }
      return node.isEnd;
   }
   startsWith(prefix) {
      let node = this;
      for (const ch of prefix) {
         if (!node.children[ch]) return false;
         node = node.children[ch];
      }
      return true;
   }
}
// 用法示例：
// const trie = new Trie();
// trie.insert('apple');
// trie.search('apple'); // true
// trie.startsWith('app'); // true

复杂度分析：

• 插入/查找/前缀查找：$O(L)$，L为字符串长度。
• 空间复杂度：$O(N \times L)$，N为单词数，L为平均长度。

应用场景：

• 前缀匹配（如自动补全、搜索建议）。
• 敏感词过滤。
• 拼写检查、词频统计。
• IP路由、字符串集合去重。
• LeetCode、面试常见高频题。

实际应用：

• Trie适合大量字符串、频繁前缀查找的场景。
• 前端如输入框智能提示、后端如搜索引擎、词库管理等。
• 可结合压缩Trie（如双数组Trie、字典压缩）进一步优化空间。

How does the front-end efficiently handle rendering of massive data?

考察点：前端性能优化。

答案：

前端高效渲染海量数据，核心在于减少 DOM 操作、控制渲染区域、按需加载和合理分片。常见技术包括虚拟滚动、懒加载、分批渲染、列表分区等。通过只渲染可视区域的数据，显著降低内存和性能压力。

主要步骤：

1. 计算可视区能显示的元素数量（如 height / itemHeight）。
2. 监听滚动事件，动态计算当前起始和结束索引。
3. 只渲染当前区间的数据，顶部和底部用空白占位撑开总高度。
4. 对于超大数据，结合懒加载和分批渲染，避免一次性加载全部数据。

常见实现方法：

1. 虚拟滚动（Virtual Scrolling）：

   // 假设每项高度固定 itemHeight
   function getVisibleData(list, scrollTop, itemHeight, visibleCount) {
      const start = Math.floor(scrollTop / itemHeight);
      const end = start + visibleCount;
      return list.slice(start, end);
   }
   // React/Vue 通用思路
   // <div style={{height: totalHeight}}>
   //   <div style={{height: start * itemHeight}}></div>
   //   {visibleData.map(...)}
   //   <div style={{height: (list.length - end) * itemHeight}}></div>
   // </div>
   

2. 分批渲染（Chunk Rendering）：

   function renderChunks(list, chunkSize, renderFn) {
      let index = 0;
      function nextChunk() {
         const chunk = list.slice(index, index + chunkSize);
         renderFn(chunk);
         index += chunkSize;
         if (index < list.length) {
            setTimeout(nextChunk, 0); // 利用事件循环分批渲染
         }
      }
      nextChunk();
   }
   // renderChunks(hugeList, 100, renderToDOM)
   

复杂度分析：

• 渲染复杂度：$O(k)$，k为可视区元素数，远优于 $O(n)$。
• 滚动事件处理为 $O(1)$，内存消耗极低。
• 分批渲染可避免主线程阻塞，提升页面响应速度。

适用场景：

• 超长列表、表格、聊天记录、日志、文件管理等。
• 前端组件库如 Element、Ant Design、React-Virtualized、Vue-Virtual-Scroller 等均有虚拟滚动实现。
• 大型数据展示、实时数据流、前端监控面板等。

实际应用：

• 虚拟滚动显著提升前端性能，适合大数据量渲染。
• 分批渲染适合首屏快速展示和渐进式加载。
• 推荐结合组件库或自定义实现，注意滚动体验和兼容性。

How to implement Union-Find? What are its practical applications in front-end development?

考察点：并查集算法应用。

答案：

并查集（Union-Find）是一种用于处理集合合并与查询的数据结构，常用于判断元素是否属于同一集合、连通性问题等。其核心思想是通过“路径压缩”和“按秩合并”优化集合查找和合并效率。

主要步骤：

1. 初始化每个元素为独立集合（父节点指向自身）。
2. 查找（find）：递归或迭代查找根节点，并路径压缩。
3. 合并（union）：将两个集合的根节点合并，按秩优化。

常见实现方法：

1. 数组实现（路径压缩 + 按秩合并）：

   class UnionFind {
      constructor(n) {
         this.parent = Array(n).fill(0).map((_, i) => i);
         this.rank = Array(n).fill(1);
      }
      find(x) {
         if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]); // 路径压缩
         }
         return this.parent[x];
      }
      union(x, y) {
         let rootX = this.find(x);
         let rootY = this.find(y);
         if (rootX === rootY) return;
         if (this.rank[rootX] < this.rank[rootY]) {
            this.parent[rootX] = rootY;
         } else if (this.rank[rootX] > this.rank[rootY]) {
            this.parent[rootY] = rootX;
         } else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
         }
      }
      connected(x, y) {
         return this.find(x) === this.find(y);
      }
   }
   // 用法示例：
   // const uf = new UnionFind(5);
   // uf.union(0, 1); uf.union(1, 2); uf.connected(0, 2); // true
   

复杂度分析：

• 单次查找/合并均摊时间复杂度为 $O(\alpha(n))$，$\alpha$ 为阿克曼函数的反函数，几乎可视为常数。
• 空间复杂度：$O(n)$。

适用场景：

• 连通性判定（如图的连通分量、社交网络分组）。
• 动态分组、权限管理、前端组件分区。
• 前端可用于拖拽分组、可视化连线、图结构处理等。

实际应用：

• 前端算法题如岛屿数量、朋友圈分组、动态连通性等。
• 可用于 Web 可视化编辑器、流程图、关系图等场景。
• 推荐数组实现，代码简洁且性能高。

How to analyze and optimize the space complexity of algorithms?

考察点：空间复杂度优化策略。

答案：

空间复杂度是衡量算法运行时所需额外内存资源的指标，分析空间复杂度有助于优化程序性能、降低资源消耗。常见优化策略包括原地操作、数据结构选择、复用变量等。

主要步骤：

1. 明确输入规模和算法中用到的额外数据结构。
2. 统计所有辅助空间（如数组、栈、队列、递归栈等）。
3. 计算空间复杂度表达式，常见有 $O(1)$、$O(n)$、$O(n^2)$ 等。
4. 优化空间占用，如原地修改、懒加载、分块处理、数据压缩等。

常见实现方法：

1. 原地操作（In-place）：

   // 交换数组元素，无需额外空间
   function reverseArr(arr) {
      let left = 0, right = arr.length - 1;
      while (left < right) {
         [arr[left], arr[right]] = [arr[right], arr[left]];
         left++;
         right--;
      }
      return arr;
   }
   // reverseArr([1,2,3]) => [3,2,1]
   // 空间复杂度 O(1)
   

2. 递归转迭代：

   // 递归版斐波那契，空间 O(n)
   function fibRec(n) {
      if (n <= 1) return n;
      return fibRec(n-1) + fibRec(n-2);
   }
   // 迭代版斐波那契，空间 O(1)
   function fibIter(n) {
      let a = 0, b = 1;
      for (let i = 2; i <= n; i++) {
         [a, b] = [b, a + b];
      }
      return b;
   }
   // fibIter(5) => 5
   

复杂度分析：

• 空间复杂度常见为 $O(1)$（原地）、$O(n)$（线性）、$O(n^2)$（二维数组/矩阵）。
• 优化后可显著降低内存消耗，提升大数据场景下的性能。

适用场景：

• 大数据处理、前端列表渲染、图/树结构遍历。
• 算法题如原地排序、动态规划空间优化、递归转迭代等。
• 前端性能优化、移动端低内存场景。

实际应用：

• 原地排序（如快排、冒泡）、空间压缩的 DP、懒加载等。
• 推荐优先考虑空间复杂度，合理选择数据结构和算法实现。

How to implement the KMP string matching algorithm?

考察点：高级字符串算法。

答案：

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，核心思想是利用部分匹配表（next数组）跳过已匹配的字符，避免重复比较，从而提升匹配效率。

主要步骤：

1. 构建模式串的 next 数组，记录每个位置前缀和后缀的最长公共长度。
2. 主串和模式串逐字符比较，遇到不匹配时根据 next 数组跳转。
3. 匹配成功返回起始索引，未匹配返回 -1。

常见实现方法：

1. KMP算法实现（JS版）：

   function getNext(pattern) {
      const next = Array(pattern.length).fill(0);
      let j = 0;
      for (let i = 1; i < pattern.length; i++) {
         while (j > 0 && pattern[i] !== pattern[j]) j = next[j - 1];
         if (pattern[i] === pattern[j]) j++;
         next[i] = j;
      }
      return next;
   }
   
   function kmp(str, pattern) {
      const next = getNext(pattern);
      let j = 0;
      for (let i = 0; i < str.length; i++) {
         while (j > 0 && str[i] !== pattern[j]) j = next[j - 1];
         if (str[i] === pattern[j]) j++;
         if (j === pattern.length) return i - j + 1;
      }
      return -1;
   }
   // kmp('abcdef', 'cd') => 2
   // kmp('abcabc', 'cab') => 2
   

复杂度分析：

• 构建 next 数组时间复杂度 $O(m)$，m为模式串长度。
• 匹配过程时间复杂度 $O(n)$，n为主串长度。
• 总体复杂度 $O(n + m)$，空间复杂度 $O(m)$。

适用场景：

• 文本编辑器查找、前端搜索、敏感词过滤、日志分析等。
• 适合大数据量和多次匹配场景。
• 前端常用 indexOf、includes、正则表达式等内置方法，底层多用KMP或Boyer-Moore优化。

实际应用：

• KMP广泛用于字符串查找、敏感词检测、代码编辑器高亮等。
• 推荐KMP算法，效率高且适合多次匹配。

How to design a high-performance front-end deduplication algorithm?

考察点：前端性能算法设计。

答案：

前端高性能去重算法的核心在于利用哈希结构（如对象、Set、Map）实现 $O(n)$ 级别的去重，避免嵌套循环导致的性能瓶颈。针对不同数据类型（基础类型、对象数组）可选用不同方案。

主要步骤：

1. 明确去重目标（基础类型、对象、复杂结构）。
2. 选择合适的数据结构（Set、Map、对象哈希）。
3. 遍历原数组，判断元素是否已存在，未存在则加入结果集。

常见实现方法：

1. 基础类型去重（Set法，推荐）：

   function dedupe(arr) {
      return Array.from(new Set(arr));
   }
   // dedupe([1,2,2,3]) => [1,2,3]
   // 时间复杂度 O(n)，空间复杂度 O(n)
   

2. 对象数组去重（Map法）：

   function dedupeByKey(arr, key) {
      const map = new Map();
      arr.forEach(item => {
         if (!map.has(item[key])) map.set(item[key], item);
      });
      return Array.from(map.values());
   }
   // dedupeByKey([{id:1},{id:2},{id:1}], 'id') => [{id:1},{id:2}]
   

3. 复杂结构去重（序列化法）：

   function dedupeComplex(arr) {
      const set = new Set();
      return arr.filter(item => {
         const key = JSON.stringify(item);
         if (set.has(key)) return false;
         set.add(key);
         return true;
      });
   }
   // dedupeComplex([{a:1},{a:1},{a:2}]) => [{a:1},{a:2}]
   

复杂度分析：

• 哈希结构去重时间复杂度 $O(n)$，空间复杂度 $O(n)$。
• 嵌套循环法时间复杂度 $O(n^2)$，不推荐。

适用场景：

• 基础类型数组、对象数组、复杂结构去重。
• 前端数据展示、表格处理、接口数据合并等。
• 大数据量去重、实时数据流处理。

实际应用：

• 推荐 Set/Map 法，语法简洁且性能高。
• 对象数组和复杂结构可结合 Map 或序列化辅助。
• 前端常见如去重列表、合并数据、表格唯一值筛选等。

How to implement depth-first search and breadth-first search for graphs?

考察点：图算法实现。

答案：

图的遍历主要有两种方式：深度优先遍历（DFS）和广度优先遍历（BFS）。DFS适合递归搜索、路径查找，BFS适合层级遍历、最短路径查找。两者均可用于无向图和有向图。

主要步骤：

1. DFS：递归或用栈实现，优先访问未访问的邻居，直到所有节点遍历完毕。
2. BFS：用队列实现，按层级依次访问所有邻居。

常见实现方法：

1. 深度优先遍历（DFS，递归/栈）：

   // 邻接表表示图
   function dfs(graph, start, visited = new Set()) {
      if (visited.has(start)) return;
      visited.add(start);
      // 处理节点 start
      for (const neighbor of graph[start]) {
         dfs(graph, neighbor, visited);
      }
   }
   // 用法：dfs({0:[1,2],1:[2],2:[0,3],3:[3]}, 2)
   

2. 广度优先遍历（BFS，队列）：

   function bfs(graph, start) {
      const visited = new Set();
      const queue = [start];
      while (queue.length) {
         const node = queue.shift();
         if (visited.has(node)) continue;
         visited.add(node);
         // 处理节点 node
         for (const neighbor of graph[node]) {
            if (!visited.has(neighbor)) queue.push(neighbor);
         }
      }
   }
   // 用法：bfs({0:[1,2],1:[2],2:[0,3],3:[3]}, 2)
   

复杂度分析：

• 时间复杂度均为 $O(V+E)$，V为节点数，E为边数。
• 空间复杂度 $O(V)$，主要用于 visited 集合和递归/队列。

适用场景：

• 路径查找、连通分量、环检测、拓扑排序、最短路径等。
• 前端如流程图、关系图、依赖分析、页面路由等。
• 算法题如岛屿数量、迷宫寻路、社交网络分组等。

实际应用：

• 推荐BFS用于最短路径、层级遍历，DFS用于路径搜索、连通性分析。
• 前端可用于图可视化、依赖分析、数据结构处理等。

What are the commonly used algorithmic design patterns in front-end architecture?

考察点：算法与架构设计。

答案：

前端架构常用的算法设计模式有助于提升代码复用性、可维护性和性能。常见模式包括单例模式、观察者模式、工厂模式、策略模式、发布订阅、装饰器、缓存等。

主要步骤：

1. 分析业务场景，确定适合的设计模式。
2. 结合算法思想优化数据处理、状态管理、事件流转等。
3. 通过模式封装复杂逻辑，提升架构可扩展性。

常见实现方法：

1. 单例模式（Singleton）：

   class Store {
      static instance;
      constructor() {
         if (Store.instance) return Store.instance;
         Store.instance = this;
      }
   }
   // const s1 = new Store(); const s2 = new Store(); s1 === s2 // true
   

2. 观察者模式（Observer）：

   class EventEmitter {
      constructor() { this.events = {}; }
      on(type, fn) { (this.events[type] ||= []).push(fn); }
      emit(type, ...args) { (this.events[type]||[]).forEach(fn => fn(...args)); }
   }
   // 用于事件总线、数据流监听
   

3. 策略模式（Strategy）：

   const strategies = {
      add: (a, b) => a + b,
      mul: (a, b) => a * b
   };
   function calc(type, a, b) { return strategies[type](a, b); }
   // calc('add', 1, 2) => 3
   

复杂度分析：

• 设计模式本身不影响算法复杂度，但能优化架构和数据流。
• 合理应用可降低耦合、提升性能和扩展性。

适用场景：

• 状态管理、事件驱动、组件通信、缓存优化、数据处理等。
• 前端框架（如Vue/React）内部大量用到设计模式。
• 复杂业务逻辑、可扩展架构、插件系统等。

实际应用：

• 推荐结合算法与设计模式，提升前端架构质量。
• 常见如单例数据仓库、事件总线、策略切换、装饰器增强等。

How to implement a weighted random lottery algorithm?

考察点：概率算法设计。

答案：

带权重的随机抽奖算法用于根据不同奖项的权重概率进行抽取，核心思想是将权重转为区间，通过随机数命中区间实现概率分布。

主要步骤：

1. 计算所有奖项的权重总和。
2. 构建权重前缀和数组，将每个奖项映射到一个区间。
3. 生成一个 $[0, \text{总权重})$ 的随机数，找到其落在哪个区间。

常见实现方法：

1. 前缀和+二分查找法（推荐）：

   function weightedRandom(items) {
      // items: [{name, weight}]
      const prefixSum = [];
      let sum = 0;
      for (const item of items) {
         sum += item.weight;
         prefixSum.push(sum);
      }
      const rand = Math.random() * sum;
      let idx = prefixSum.findIndex(v => rand < v);
      return items[idx].name;
   }
   // weightedRandom([{name:'A',weight:1},{name:'B',weight:3},{name:'C',weight:6}])
   

2. 二分查找优化（适合奖项多）：

   function weightedRandomBinary(items) {
      const prefixSum = [];
      let sum = 0;
      for (const item of items) {
         sum += item.weight;
         prefixSum.push(sum);
      }
      const rand = Math.random() * sum;
      let left = 0, right = prefixSum.length - 1;
      while (left < right) {
         const mid = Math.floor((left + right) / 2);
         if (rand < prefixSum[mid]) right = mid;
         else left = mid + 1;
      }
      return items[left].name;
   }
   

复杂度分析：

• 构建前缀和 $O(n)$，抽奖查找 $O(n)$ 或 $O(\log n)$（二分）。
• 空间复杂度 $O(n)$。

适用场景：

• 抽奖、转盘、概率分布采样、广告投放、推荐系统等。
• 前端活动抽奖、游戏掉落、内容分发等。

实际应用：

• 推荐前缀和+二分查找法，性能高且易扩展。
• 前端抽奖、概率采样、内容推荐等场景广泛应用。

How to analyze performance bottlenecks in front-end algorithms?

考察点：性能瓶颈分析方法。

答案：

前端算法性能瓶颈分析旨在定位影响页面响应速度和资源消耗的关键环节，常用方法包括代码 profiling、复杂度分析、数据量测试和工具辅助定位。

主要步骤：

1. 明确算法的输入规模和核心流程。
2. 通过时间复杂度和空间复杂度分析，找出高消耗环节。
3. 利用浏览器性能分析工具（如 Chrome DevTools）进行代码 profiling，定位慢点。
4. 结合数据量测试，观察算法在不同规模下的表现。
5. 优化热点代码，如减少循环嵌套、避免重复计算、合理缓存等。

常见实现方法：

1. 复杂度分析法：

   • 通过 Big-O 分析，找出 $O(n^2)$、$O(2^n)$ 等高复杂度环节。

2. 性能分析工具：

   // Chrome DevTools Performance 面板
   // 1. 录制页面操作
   // 2. 查看函数耗时、调用栈
   // 3. 定位慢点和内存泄漏
   

3. 数据量测试法：

   function testPerf(fn, arr) {
     const t0 = performance.now();
     fn(arr);
     const t1 = performance.now();
     console.log('耗时(ms):', t1 - t0);
   }
   // testPerf(sortFn, bigArr)
   

复杂度分析：

• 性能瓶颈常见于高复杂度算法、频繁 DOM 操作、大数据量处理等。
• 优化后可显著提升页面响应速度和资源利用率。

适用场景：

• 大数据渲染、复杂计算、动画、实时数据流等。
• 前端性能优化、交互响应、移动端低性能场景。

实际应用：

• 推荐结合复杂度分析和工具定位，优先优化热点代码。
• 前端常见如列表渲染、排序、筛选、动画等性能瓶颈。

How to implement an efficient eviction mechanism for LRU cache?

考察点：缓存算法优化。

答案：

LRU（Least Recently Used，最近最少使用）缓存淘汰机制用于在空间有限时优先移除最久未被访问的数据。高效实现需保证插入、访问、淘汰均为 $O(1)$。

主要步骤：

1. 每次访问或插入数据时，将其标记为“最近使用”。
2. 当缓存满时，移除“最久未使用”的数据。
3. 结合哈希表和双向链表，实现高效查找和顺序维护。

常见实现方法：

1. 哈希表 + 双向链表（推荐）：

   class LRUCache {
      constructor(capacity) {
         this.capacity = capacity;
         this.map = new Map();
      }
      get(key) {
         if (!this.map.has(key)) return -1;
         const value = this.map.get(key);
         this.map.delete(key);
         this.map.set(key, value); // 移到最新
         return value;
      }
      put(key, value) {
         if (this.map.has(key)) this.map.delete(key);
         this.map.set(key, value);
         if (this.map.size > this.capacity) {
            // 淘汰最久未使用
            this.map.delete(this.map.keys().next().value);
         }
      }
   }
   // let cache = new LRUCache(2);
   // cache.put(1,1); cache.put(2,2); cache.get(1); cache.put(3,3);
   // 时间复杂度 O(1)，空间复杂度 O(n)
   

2. 数组实现（仅适合小容量）：

   • 每次访问移动元素，插入时判断容量。

复杂度分析：

• 插入、访问、淘汰均为 $O(1)$（哈希表+链表）。
• 空间复杂度 $O(n)$。

适用场景：

• 浏览器缓存、图片资源管理、前端虚拟列表、接口数据缓存等。
• 适合高频访问、空间有限的缓存场景。

实际应用：

• 推荐哈希表+链表实现，性能高且易扩展。
• 前端常见如页面缓存、图片懒加载、接口数据缓存等。

How to combine algorithms to optimize front-end architecture design?

考察点：算法驱动的架构思维。

答案：

结合算法优化前端架构设计，能提升系统性能、扩展性和可维护性。通过合理选用数据结构、算法模式和性能优化策略，解决复杂业务和高并发场景。

主要步骤：

1. 分析业务需求，识别性能瓶颈和数据流动关键点。
2. 选用合适的数据结构（如哈希表、队列、树、图等）提升数据处理效率。
3. 应用算法设计模式（如缓存、分治、动态规划、贪心等）优化核心流程。
4. 结合异步处理、懒加载、虚拟滚动等前端专用算法提升用户体验。

常见实现方法：

1. 缓存优化（LRU/本地存储）：

   // 页面数据缓存，减少接口请求
   class Cache {
     constructor() { this.map = new Map(); }
     get(key) { return this.map.get(key); }
     set(key, val) { this.map.set(key, val); }
   }
   

2. 虚拟滚动/分块渲染：

   • 只渲染可视区数据，提升大数据列表性能。

3. 分治/动态规划优化：

   • 复杂业务如表格合并、路径规划、数据聚合等。

复杂度分析：

• 算法优化可显著降低时间和空间复杂度，提升系统响应速度。
• 合理架构设计可降低耦合、提升可维护性。

适用场景：

• 大型前端项目、复杂数据处理、实时交互、性能敏感场景。
• 组件库、数据可视化、前端中台、低代码平台等。

实际应用：

• 推荐结合算法与架构设计，前端常见如缓存、虚拟列表、分治处理、异步优化等。
• 通过算法驱动架构，提升整体性能和用户体验。

How to implement serialization and deserialization of complex data structures?

考察点：数据结构序列化策略。

答案：

复杂数据结构的序列化是将对象、树、图等结构转为字符串或二进制，便于存储、传输和还原。反序列化则是将字符串/二进制还原为原始结构。常见方法有递归遍历、标记空节点、层序编码等。

主要步骤：

1. 明确数据结构类型（如树、图、链表、嵌套对象等）。
2. 设计序列化格式（如 JSON、层序、前序、特殊分隔符等）。
3. 递归或迭代遍历结构，按格式输出字符串。
4. 反序列化时按格式解析字符串，重建原始结构。

常见实现方法：

1. 二叉树前序序列化/反序列化（递归法）：

   // 序列化
   function serialize(root) {
      if (!root) return '#,';
      return root.val + ',' + serialize(root.left) + serialize(root.right);
   }
   // 反序列化
   function deserialize(data) {
      const arr = data.split(',');
      function build() {
         const val = arr.shift();
         if (val === '#' || val === '') return null;
         const node = { val };
         node.left = build();
         node.right = build();
         return node;
      }
      return build();
   }
   // 用法：serialize(root)，deserialize(str)
   

2. 对象/数组序列化（JSON法）：

   const obj = { a: 1, b: [2, 3], c: { d: 4 } };
   const str = JSON.stringify(obj);
   const newObj = JSON.parse(str);
   // 适合无循环引用的结构
   

复杂度分析：

• 序列化/反序列化时间复杂度 $O(n)$，n为节点/元素数。
• 空间复杂度 $O(n)$。

适用场景：

• 前端本地存储、接口传输、数据持久化、页面缓存等。
• 树结构、图结构、嵌套对象、链表等。

实际应用：

• 推荐递归法处理树/图结构，JSON法处理对象/数组。
• 前端常见如表单缓存、页面快照、数据同步等。