30 Seconds of Interviews用 Array.reduce 生成斐波那契数列数组的 JavaScript 实现与面试拆解【免费下载链接】30-seconds-of-interviewsA curated collection of common interview questions to help you prepare for your next interview.项目地址: https://gitcode.com/gh_mirrors/30/30-seconds-of-interviews导读本文围绕 30 Seconds of Interviews 面试题库中的经典 JavaScript 算法题——「生成包含斐波那契数列、截至第 n 项的数组」展开逐行拆解其基于Array.prototype.reduce()的声明式实现并对比递归、记忆化等常见解法。读完你将掌握reduce()的累加器模型、稀疏数组与concat的配合技巧以及如何在大 O 视角下向面试官论证该算法的时空复杂度为算法类面试题提供一套可复用的分析话术。一、题目本身要求与考点原题出自本仓库的 questions/fibonacci.mdGenerate an array, containing the Fibonacci sequence, up until the nth term.生成一个数组包含截至第 n 项的斐波那契数列。这是典型的「用高阶函数实现经典序列」类问题expertise标记为 1intermediate 难度归属javascript标签。它的考察重点不在「是否知道斐波那契定义」而在于能否用声明式函数式风格替代常见的for循环是否真正理解Array.prototype.reduce()的累加器机制能否正确处理前两项的特殊性数列中第 0、1 项没有「前两项之和」可加。二、官方参考答案一行 reduce 的声明式实现原文档给出的答案如下const fibonacci n [...Array(n)].reduce( (acc, val, i) acc.concat(i 1 ? acc[i - 1] acc[i - 2] : i), [] )思路概括原文档原话初始化一个长度为n的空数组用Array.prototype.reduce()向数组中追加值——从第三项开始取累加数组中最后两个值的和前两项则直接使用索引i本身。逐行拆解执行过程Array(n)创建稀疏数组长度为n、没有任何元素所有槽位为empty[...Array(n)]借助数组展开语法把稀疏数组「摊开」为[undefined, undefined, ..., undefined]共n个元素。这一步是reduce()能够逐槽遍历的前提——reduce会跳过空槽位若不展开回调根本不会执行reduce((acc, val, i) ..., [])以空数组[]为初始累加器遍历n个槽位回调的第三个参数i恰好就是当前项在序列中的位置0 ~ n-1acc.concat(i 1 ? acc[i - 1] acc[i - 2] : i)是核心逻辑当i 1时取累加数组中倒数第一、第二项求和后追加concat返回新数组不修改原累加器当i 0时追加0i 1时追加1——这两项是斐波那契序列的种子无法由前两项推导最终reduce返回的数组即[0, 1, 1, 2, 3, 5, 8, ...]。验证各 n 值下的输出fibonacci(1) // [0] fibonacci(2) // [0, 1] fibonacci(5) // [0, 1, 1, 2, 3] fibonacci(10) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]注意题目要求「up until the nth term」因此fibonacci(n)返回的是前 n 项索引 0 到 n-1而非斐波那契定义中的「第 n 个斐波那契数」F(n)。两者在面试沟通中务必先说清楚约定否则容易产生歧义。三、为什么选concat而不是push这道题最容易被追问的细节就是累加器追加元素为什么用concat而不用push原因在于reduce回调的返回值会成为下一次回调的累加器// push 会原地修改并返回新长度破坏累加器语义 const bad n [...Array(n)].reduce((acc, val, i) { acc.push(i 1 ? acc[i - 1] acc[i - 2] : i) return acc // 必须手动返回 acc否则下一次拿到 undefined }, []) // concat 返回新数组天然符合「返回新累加器」的约定 const good n [...Array(n)].reduce( (acc, val, i) acc.concat(i 1 ? acc[i - 1] acc[i - 2] : i), [] )concat的不可变immutable风格也与本仓库其他题目强调的函数式理念一致例如 questions/for-each-map.md 指出map()将每个元素映射到新数组、保持数据不可变是常见的函数式编程手法questions/pure-functions.md 对纯函数的定义也要求「同样的输入必然得到同样的输出且不产生副作用」。concat版本天然满足纯函数要求而push版本则引入了外部可变状态。四、面试进阶与其他解法的对比4.1 经典 for 循环版本function fibonacci(n) { const arr [0, 1] for (let i 2; i n; i) { arr[i] arr[i - 1] arr[i - 2] } return arr.slice(0, n) }命令式版本胜在直观但面试官往往会要求你用高阶函数改写考察你对reduce的熟练度。4.2 递归版本与性能陷阱const fib n (n 2 ? n : fib(n - 1) fib(n - 2))本仓库的 questions/recursion.md 指出递归是函数反复调用自身、直到命中 base condition 的过程。斐波那契天然适合递归表述但朴素递归存在严重的重复计算fib(5)会反复计算fib(3)、fib(2)多次指数级膨胀。若面试官追问「如何优化递归版斐波那契」可顺势引出记忆化memoization——这正是仓库中另一道独立考题 questions/memoize.md 的主题缓存函数调用结果使相同输入的后续调用直接命中缓存const memoize fn { const cache new Map() return value { const cachedResult cache.get(value) if (cachedResult ! undefined) return cachedResult const result fn(value) cache.set(value, result) return result } } const fastFib memoize(n (n 2 ? n : fastFib(n - 1) fastFib(n - 2)))不过要如实向面试官说明memoize 版第一调用仍有额外开销检查缓存、写入缓存且返回的是单个斐波那契数而非整段序列若目标是整段数组reduce 版一次遍历即可同时产出所有项无需缓存。五、复杂度分析用 Big O 语言论证面试中回答完实现后标准动作是给出时间/空间复杂度。可借用本仓库 questions/big-o-notation.md 的分析框架版本时间复杂度空间复杂度说明reduce concat本文主角O(n²)O(n)每次concat复制当前累加器长度 0..n-1总复制量为 12...nfor 循环 索引赋值O(n)O(n)每次迭代常数时间写入新槽位朴素递归 fib(n)O(2ⁿ)O(n)调用栈大量重复子问题记忆化递归O(n)O(n)每个子问题只算一次由此可以给出一个诚实的结论reduceconcat 版胜在声明式与不可变但它不是性能最优解在 n 较大时应改用索引赋值或push版本这也呼应了 big-o 文档中「警惕嵌套循环导致执行时间指数/平方级上升」的告诫。能在面试中主动指出这一点往往比只会背诵答案更能加分。六、仓库视角这份答案在项目中如何被组织与消费作为 30 Seconds of Interviews 的一则条目questions/fibonacci.md遵循仓库统一的题面模板参见 question-template.md### 题目→ 可选示例代码 →#### Answer→#### Good to hear→##### Additional links→ 元数据注释tags、expertise。这套结构化格式并非摆设。仓库通过 scripts/util.js 中的readQuestions()读取questions/目录下全部.md文件再以getSection(#### Answer, contents)等函数按标题切片提取题面、答案、要点与链接随后 scripts/extract.js 将这些片段组装为 JSON 条目含name、question、answer、goodToHear、links、tags、expertise、questionCodeBlocks、answerCodeBlocks最终写入 data/questions.json 供前端站点渲染。这意味着「答案代码块能否被正则正确识别」直接决定展示质量——本文主角fibonacci的答案代码块正是被getCodeBlocks()以围栏正则提取的典型样例。七、附原文档的 Good to hear 与扩展阅读指引原文档在#### Good to hear之后、##### Additional links中给出了一条外部链接指向 30-seconds-of-code 归档中的fibonacciUntilNum.md。根据本任务对仓库链接的规范此处不再展开外部链接内容建议继续研读仓库内同主题的相邻文档以构建知识网络questions/recursion.md——递归的适用场景与基准条件base conditionquestions/memoize.md——记忆化缓存的完整实现与权衡questions/big-o-notation.md——O(1)/O(N)/O(N²)/O(N!) 的直观量级对照questions/pipe.md——同样基于reduce的函数组合题可与本题互相印证 reduce 的多种用法。小结[...Array(n)].reduce((acc, _, i) acc.concat(i 1 ? acc[i-1] acc[i-2] : i), [])以一行代码完成了斐波那契前 n 项的声明式生成。它同时考察了三层能力对稀疏数组与展开语法的理解、对reduce累加器契约的把握、对前两项种子条件的处理。面试时建议按「实现 → 逐行解释 → 复杂度 → 与其他解法对比」的顺序作答并坦诚指出 concat 的 O(n²) 代价与替代方案这样的回答既有深度又不失严谨。【免费下载链接】30-seconds-of-interviewsA curated collection of common interview questions to help you prepare for your next interview.项目地址: https://gitcode.com/gh_mirrors/30/30-seconds-of-interviews创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考