最佳（中高级）前端面试题（来自一个前端工程师）

原文链接：The Best Frontend JavaScript Interview Questions (written by a Frontend Engineer)
原文作者：Boris Cherny

[译者注:]
本文偏向很多算法的内容，并不很适合前端的初学者。如果你有2-3年的开发经验，且希望向架构、全栈等方向发展，这篇文章会很适合你。
PS: 没有答案！
关注的小伙伴们多的话我会写个不一定是最佳实践的答案供大家参考。😝😝😝

---

前言

“我前几天在旧金山参加了Free Code Camp 的见面会（meetup ），（给不熟悉的同学们介绍一下，Free Code Camp是一个供人们聚在一起学习JavaScript一类的web开发的组织），有几位朋友正在应聘前端工程师，他们在准备关于JavaScript的前端面试题。搜索了google之后我并没有找到合适的知识点清单，一个能让她“看懂了就能过面试”的万金油清单。找到了下面这些清单：
有 的 凑 合，有 的 好蠢。
它们中要么不完整，要么只写了一些真实面试中不会问的问题。

所以呢，基于我面试别人和被别人面试的经验，我将整理一份清单。我面别人也好别人面我也好，都有一些总会被提及的问题。要记住，有些公司（比如Google）更加关注你是否可以做出高效的算法设计，所以如果你想去那儿工作，除了我下面列出的问题外，你还需要多加练习past CodeJam problems 。如果你对我下面给出的清单内容有疑问（或者是我某些地方写错了），请邮件联系我。”

我会在这里添加或是更新这些问题的答案（欢迎你提出有建设性的需求！）
我将问题分为以下几个大类：

• 概念
• 编码
• 改错
• 系统设计

---

概念

请用清晰准确的语句解释如下名词（不需要编码）：

1. 什么是“大O”符号，它被用来表示什么？
2. 什么是DOM?
3. 什么是时间循环？
4. 什么是闭包？
5. 原型继承是怎样的，如何工作，它和普通的继承有什么区别？(这个问题没啥意义，但很多面试官都爱问)
6. this 如何工作，代表什么?
7. 什么是事件冒泡，它是如何工作的？（这也不是个好问题，同样的很多面试官很喜欢问。）
8. 描述几种服务器和客户端之间的通信方式。描述一些网络协议是工作的（IP、TCP、http/S/2、UDP、RTC、DNS等）
9. REST是什么, 为什么使用它?
10. 网页加载的很慢，诊断原因且修复它。如何进行性能优化，什么时候应该进行性能优化？
11. 你用过什么前端框架？它们各有什么优缺点？为什么我们要使用框架？框架能为我们解决什么问题？

编码

实现以下功能：

简单：

1. isPrime - 返回true或false, 表示输入的数是否为质数：

isPrime(0)                          // false
isPrime(1)                          // false
isPrime(17)                         // true
isPrime(10000000000000)             // false

2. factorial - 返回给定数的阶乘的值：

factorial(0)                        // 1
factorial(1)                        // 1
factorial(6)                        // 720

3. fib -返回斐波那契数列的前n项的和（n为给定） 斐波那契数列.

fib(0)                              // 0
fib(1)                              // 1
fib(10)                             // 55
fib(20)                             // 6765

4. isSorted - 返回true或false，表示给定的数组是否被排序过：

isSorted([])                        // true
isSorted([-Infinity, -5, 0, 3, 9])  // true
isSorted([3, 9, -3, 10])            // false

5. filter - 实现过滤器功能.

filter([1, 2, 3, 4], n => n < 3)    // [1, 2]

6. reduce- 实现reduce 函数.

reduce([1, 2, 3, 4], (a, b) => a + b, 0) // 10

7. reverse- 反转给定字符串 (用已封装好的 reverse 是一个cheat，要自己实现).

reverse('')                         // ''
reverse('abcdef')                   // 'fedcba'

8. indexOf - 实现数组的 indexOf方法.

indexOf([1, 2, 3], 1)               // 0
indexOf([1, 2, 3], 4)               // -1

9. isPalindrome - 返回true或false判断给定字符串是否是一个回文(palindrome)（大小写不敏感）

isPalindrome('')                                // true
isPalindrome('abcdcba')                         // true
isPalindrome('abcd')                            // false
isPalindrome('A man a plan a canal Panama')     // true

10. missing - 一个数字1至n不重复且未排序过的数字组成的数组，从数字1至数字n选取出不重复且未排序过的数字组成数组（n为最大的数），调用方法后补全数组里缺失的数字。是否可以设计出时间复杂度为O(n)的算法？提示：有个聪明的方法供你使用。

missing([])                         // undefined
missing([1, 4, 3])                  // 2
missing([2, 3, 4])                  // 1
missing([5, 1, 4, 2])               // 3
missing([1, 2, 3, 4])               // undefined

11. isBalanced - 用true或false表示给定的字符串的花括号是否平衡（一一对应）

isBalanced('}{')                      // false
isBalanced('{{}')                     // false
isBalanced('{}{}')                    // true
isBalanced('foo { bar { baz } boo }') // true
isBalanced('foo { bar { baz }')       // false
isBalanced('foo { bar } }')           // false

---

中级：

1. fib2 - 实现像上面的fib函数一样的功能，但是要能够算出数列中前50位以上的数的和。(小提示: 从内存中查询).

fib2(0)                               // 0
fib2(1)                               // 1
fib2(10)                              // 55
fib2(50)                              // 12586269025

2. isBalanced2 - 实现同上面的isBalanced函数相同的功能，但是要支持三种类型的括号{}，[]，和()。带有交错括号的字符串应该返回false。

isBalanced2('(foo { bar (baz) [boo] })') // true
isBalanced2('foo { bar { baz }')         // false
isBalanced2('foo { (bar [baz] } )')      // false

3. uniq - 选取一个由数字组成的数组，为其去重，返回去重后的数组。可以实现出时间复杂度为O(n)的算法吗？

uniq([])                              // []
uniq([1, 4, 2, 2, 3, 4, 8])           // [1, 4, 2, 3, 8]

4. intersection - 算出两个数组的交集（公共部分）。可以实现时间复杂度为O(M+N)（M和N为两个数组的长度）的方法吗？

intersection([1, 5, 4, 2], [8, 91, 4, 1, 3])    // [4, 1]
intersection([1, 5, 4, 2], [7, 12])             // []

5. sort -实现 sort 方法，用于排序元素为数字的数组， 且时间复杂度为O(N×log(N)).

sort([])                              // []
sort([-4, 1, Infinity, 3, 3, 0])      // [-4, 0, 1, 3, 3, Infinity]

6. includes - 判断给定的数字是否出现在给定的已排列好的数组中，返回true或false。是否能设计出时间复杂度为O(log(N))的算法？

includes([1, 3, 8, 10], 8)            // true
includes([1, 3, 8, 8, 15], 15)        // true
includes([1, 3, 8, 10, 15], 9)        // false

7. assignDeep- 仿照 Object.assign, 但是要深度合并对象。为了简单起见，可以假设对象只包含数字或是什么别的（而不是数组、函数等）。

assignDeep({ a: 1 }, {})              // { a: 1 }
assignDeep({ a: 1 }, { a: 2 })        // { a: 2 }
assignDeep({ a: 1 }, { a: { b: 2 } }) // { a: { b: 2 } }
assignDeep({ a: { b: { c: 1 }}}, { a: { b: { d: 2 }}, e: 3 })
// { a: { b: { c: 1, d: 2 }}, e: 3 }

8. reduceAsync- 仿照reduce 你在“简单”部分中完成了，但每个条目都必须在进行下一步之前被解决。

let a = () => Promise.resolve('a')
let b = () => Promise.resolve('b')
let c = () => new Promise(resolve => setTimeout(() => resolve('c'), 100))
await reduceAsync([a, b, c], (acc, value) => [...acc, value], [])
// ['a', 'b', 'c']
await reduceAsync([a, c, b], (acc, value) => [...acc, value], ['d'])
// ['d', 'a', 'c', 'b']

9. 用reduceAsync来实现seq。seq使用一个可返回 promise的函数体内使用数组的函数，然后逐一的解决。

let a = () => Promise.resolve('a')
let b = () => Promise.resolve('b')
let c = () => Promise.resolve('c')
await seq([a, b, c])                  // ['a', 'b', 'c']
await seq([a, c, b])                  // ['a', 'c', 'b']

---

困难：

注意：下面你要实现的数据结构问题，意不在让你记住它们，而只是希望你去查看给出的API，Google是怎么考虑且实现它们的，然后站在一个较高的角度去思考这些实现和其他数据结构相比如何。

1. permute - 返回一个字符串数组，包含给定的字符串的所有的排列。

permute('')             // []
permute('abc')          // ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

2. debounce - 实现 debounce 函数.

let a = () => console.log('foo')
let b = debounce(a, 100)
b()
b()
b() // only this call should invoke a()

3. 实现一个 LinkedList 类，不用 JavaScript的built-in 数组 ([]). 你的链表需要支持两种方法，add和has。

class LinkedList {...}
let list = new LinkedList(1, 2, 3)
list.add(4)                           // undefined
list.add(5)                           // undefined
list.has(1)                           // true
list.has(4)                           // true
list.has(6)                           // false

4. 实现一个HashMap 类，不用JavaScript的built-in objects ({}) 方法或者是Maps方法。你需要提供一个hash()函数，传入一个字符串，返回一个数字（大多数情况下数字都是唯一的，有时候两个不同的字符串会返回一样的数字）：

function hash (string) {
  return string
    .split('')
    .reduce((a, b) => ((a << 5) + a) + b.charCodeAt(0), 5381)
}

你有的哈希表需要支持两种方法，get和set:

let map = new HashMap
map.set('abc', 123)                   // undefined
map.set('foo', 'bar')                 // undefined
map.set('foo', 'baz')                 // undefined
map.get('abc')                        // 123
map.get('foo')                        // 'baz'
map.get('def')                        // undefined

5. 实现一个BinarySearchTree（二叉搜索树）类，需要支持四种方法：add，has，remove， size：

let tree = new BinarySearchTree
tree.add(1, 2, 3, 4)
tree.add(5)
tree.has(2)                           // true
tree.has(5)                           // true
tree.remove(3)                        // undefined
tree.size()                           // 4

6. 实现一个BinaryTree（二叉树）类，广度优先搜索、中序排列、先序排列、后序遍历深度优先搜索功能。

let tree = new BinaryTree
let fn = value => console.log(value)
tree.add(1, 2, 3, 4)
tree.bfs(fn)                          // undefined
tree.inorder(fn)                      // undefined
tree.preorder(fn)                     // undefined
tree.postorder(fn)                    // undefined

---

改错

下面的每一个问题，先要弄明白为什么给出的代码块无法正常实现功能，然后想出解决方案，编写代码，正常实现功能：

1. 我想要代码打印出：“hey amy”，但是它打印的是“hey arnold”，为什么呢？

function greet(person) {
  if (person == { name: 'amy' }) {
    return 'hey amy'
  } else {
    return 'hey arnold'
  }
}
greet({ name: 'amy' })

2.我希望代码按顺序打印出数字0，1，2，3，但是现在并不是这样的输出（这一度被认为是一个小bug，很多人喜欢在面试的时候提问为什么）

for (var i = 0; i < 4; i++) {
  setTimeout(() => console.log(i), 0)
}

3. 我希望代码打印出“doggo”，但是现在打出来是undefined

let dog = {
  name: 'doggo',
  sayName() {
    console.log(this.name)
  }
}
let sayName = dog.sayName
sayName()

4. 我想要我的狗狗bark()，但是我得到的确实error，为什么呢？

function Dog(name) {
  this.name = name
}
Dog.bark = function() {
  console.log(this.name + ' says woof')
}
let fido = new Dog('fido')
fido.bark()

5. 为什么这个代码会返回这样结果？

function isBig(thing) {
  if (thing == 0 || thing == 1 || thing == 2) {
    return false
  }
  return true
}
isBig(1)    // false
isBig([2])  // false
isBig([3])  // true

---

系统设计

如果你不是很明白“系统设计”，你可以从这里开始学习。

1. 来聊聊看，如果想要做一个完整的自动补全的小程序(widget)。用户可以在其中输入文字，并从服务器得到返回结果。

• 你会如何设计一个支持以下功能的前端页面：
  • 从后台API获取数据
  • 以树形渲染结果（每个对象可以有父/子，而不是一个平铺的列表）
  • 支持checkbox, radio button, icon以及普通的列表项-列表项从很多的表单中得到
• 组件API是怎样的？
• 后端API是怎样的？
• 对于补全输入的行为还有什么会影响到性能的事是要额外考虑进去的？是否有一些边缘情况发生（比如如果用户输入速度快，网络速度慢）？
• 若要前端展现更加迅速，你会怎么设计网络部分以及架构后端？你的客户端和服务器是怎样通信的？后端的数据如何存储？当扩展到有大量数据和大量客户时，如何实现这些功能？

2. 谈谈如何实现Twitter的全栈构建（从我的朋友Michael Vu那窃来的题目，害羞）。

• 如何获取并渲染每条推特消息？
• 当有新的推文来了你该如何渲染？你如何知道啥时候来了新的推文？
• 你该如何设计搜索推文？如何按作者搜索推文？聊聊你的数据库、后台以及API设计。

---

更多资料

如果你这些都了解了想要了解更多知识，下面有一些我找到的更高质量的资源也许对你有帮助。

有帮助的项目：

• The Algorithm Design Manual
• Past CodeJam problems
• keon/algorithms

有帮助的书籍：

• The Algorithm Design Manual 算法设计手册
• JavaScript Allonge JavaScript附录
• You Don’t Know JS 你不知道的JavaScript
• Effective JavaScript 高效的JavaScript