前端面试手撕JS代码系列（五）

算法对于前后端开发都非常重要，即便在不笔试的情况下，面试官还是喜欢检验我们的算法功底，以及通过让你说程序的运行结果考察我们对知识点的掌握程度，这样就会立刻看出你的情况，整理了一下最近在面试中遇到的手写代码题目，包含前端基础题和算法题。

考点总结： 排序、 树的遍历、随机生成、this指向（bind、call、apply）、异步、Promise、深拷贝、事件流、防抖和节流

算法题

数组两元素之和

场景： 蚂蚁金服二面
考点： 排序、双指针

找出一个升序数组中，和为sum的两个元素，要求时间复杂度小于O(n*n)
比较简单，left + right > sum , right -- ; left + right < sum, left ++

var findIndex = function(arr, sum){
  let i = 0,j = arr.length-1
  while(i !== j){
    let tmpSum = arr[i] + arr[j]
    if(tmpSum < sum){
      i++
    }else if(tmpSum > sum){
      j--
    }else{
      return arr[i],arr[j]
    }
  }
}

延伸扩展——找出一个数组中两个和为targetNumber的元素的索引[i,j]，数组为无序数组（美团二面）。
这个开始我有点头大，因为输出的是索引，后来面试官真的很好，一直耐心引导我，我的思维便不再受排序牵制，然后利用Map解决了这个问题，但不同的是由于map中的has方法只能针对key进行判断（例如：map.has('name')），所以我们要一反常规，把数值arr[i]作为key，把索引index作为value，这样就可不使用Array.indexOf遍历就能获取索引，同时但又能查询数组中是否包含某数值。

var findIndex = function(arr, target){
  var map = new Map()
  // 初始化Map
  arr.forEach((item,index) =>{
    map.set(item,index) // item作为key,index作为value
  })
  // 遍历查询
  arr.forEach((item,i)=>{
    let tmp = target-item
    if(map.has(tmp)){ // 判断Map中是否有恰好合适的值
      return [i,map.get(tmp)]
    }
  })
}

数组的去重

场景： 蚂蚁金服一面
考点： 数组的操作，连带考察Array的方法

这个在之前 JS刷题小结（一） 中有讲，不再重复声明，要考虑是否改变原数组，以及不同时间和空间复杂度的限制情况

除了使用排序和indexOf,在此补充几种去重：

1. 利用Object属性不同去重

var removeDuplicates = function(arr){
  let obj = {}
  let newArray = []
  arr.forEach((item) =>{
    if(!obj[item]){
      obj[item] = 1
      newArray.push(item)
    }
  })
  return newArray
}

2. splice删除元素,改变原数组

var removeDuplicates = function(arr){
  let len = arr.length
  for(let i = 0; i < len; i++){
    for(let j = i+1; j < len; j++){
      if(arr[i] === arr[j]){
        arr.splice(j,1)
        len --
        j --
      }
    }
  }
  return arr
}

3. 利用ES6的Set特性——成员唯一性

var removeDuplicates = function(arr){
  return Array.from(new Set(arr))
}

js洗牌函数

场景： 蚂蚁金服二面

你来设计一个算法，打乱一副扑克牌[0,53]的顺序
思路： 在不修改原数组的情况下，打乱新的顺序，随机生成索引和当前互换

var shuffleCards = function(arr){
  let arrCopy = arr.slice()
  for(let i = 0; i < arr.length; i++){
    let j = getRandom(0,i) // 生成随机索引
    let temp = arrCopy[i]
    arrCopy[i] = arrCopy[j]
    arrCopy[j] = temp
  }
  return arrCopy
}
//随机函数（min,max）之间的随机整数
function getRandom(min, max){
  return Math.floor(Math.random()*(max-min+1) + min)
}

爬梯子问题

场景： 字节跳动一面
考点： leetcode青蛙跳台阶，递归及非递归实现

// 递归实现
var jumpStage = function(n){
  if(n <= 2)  return n
  return jumpStage(n-1) + jumpStage(n-2)
}
// 非递归实现
var jumpStage = function(n){
  if(n <= 2)  return n
  let pre = 1
  let next = 2
  for(let i = 3; i <= n; i++){
    let tmp = next
    next += pre
    pre = tmp
  }
  return next
}

生成随机数组

场景： 字节跳动二面
考察：随机数的生成、去重

请写出一个可以生成整形随机数数组(内部元素不重复)的函数，并可以根据参数设置随机数生成的范围和数量，例如：函数madeRandomList(a, b, c)，可以生成 [a, b] 范围内，长度为 c 的随机数数组

var madeRandomList = function(a,b,c){
  let randomList = []
  let cnt = 0 // 生成的随机数的个数
  while(cnt < c){
    let r = Math.floor(Math.random()*(b-a+1) + a)
    if(randomList.indexOf(r) === -1){ // 未生成过这个随机数字
      randomList.push(r)
      cnt ++
    }
  }
  return randomList
}

求和函数

场景： 腾讯WXG一面
考点：柯里化、arguments、toString()
题目：实现sum函数，结果如下

sum().result = 0
sum(2,3).result = 5
sum(1,2)(3).result = 6
sum(1,2)(3,4).result = 10
sum(1,2)(3,4)(5).result = 15

之前没有研究过柯里化，所以手撕代码这道题直接铺gai，不得不说鹅厂WXG的题真的是有些难度的，从来没想过会败给sum函数，原因还是自己没有深入了解吧

柯里化

柯里化（Currying）：把接受多个参数的函数变换成接受一个单一参数(最初函数的第一个参数)的函数，并且返回接受余下的参数且返回结果的新函数的技术

一般情况下，简单的两个参数的例子可以直接写：

function curry(sum, a){
  return function(b){
    return sum(a+b)
  }
}

但如果参数增多呢?总不能无限嵌套下去吧… …于是，我们可以使用闭包思想改造一下！

function curry(fn, ...args){
  var length = fn.length // fn中的参数数量
  return function(...nextArgs){
    var allArgs = [...args,...nextArgs] // 收集参数
    if(allArgs.length >= length)
      return fn.apply(null,allArgs) // 参数足够调用原参数
    return curry(fn, ...allArgs) // 不够参数，继续递归调用
  }
}
var currySum = curry(sum)
currySum(1,2,3)(4)(5)

把上一批参数和下一批参数结合在一起，然后返回一个函数，继续相同的模式。
上述情况下参数是固定的,而在真实的需求中，我们参数的数量往往是未知且不固定的。我们可以把上面根据参数数量结束的条件删减掉，返回一个函数

function curry(fn, ...args){
  return function(...nextArgs){
    var allArgs = [...args, ...nextArgs]
    return curry(fn, ...allArgs)
  }
}

最后修改为符合题目要求的代码，还需要添加result获取值

function sum(...args){
  var f = function(...nextArgs){
    var allArgs = [...args, ...nextArgs]
    return sum(...allArgs)
  }
  // 定义sum值
  f.res = args.length !== 0 ? args.reduce((a,b) => a+b) : 0
  return f
}
console.log(sum(1,2,3)(4,5)(6).result)

好啦，小功告成！

连续子数组

场景：腾讯WXG一面
考点：数组遍历
题目：寻找和最大的连续子数组，输出最大和

var findMaxSum = function(nums){
  if(nums.length <= 0)  return 0
  var tempSum = nums[0]
  var maxSum = nums[0]
  num.forEach((item) = >{
    if(tempSum < 0){ // 之前的和为负数，弃掉
      tempSum = nums[i]
    }else{ // 继续累加
      tempSum += nums[i] 
    }
    // 更新最大的sum
    maxSum = Math.max(tempSum, maxSum)
  })
  return maxSum
}

前端技术的手写题：

手写事件监听

场景： 字节跳动一面
考点： DOM操作，事件流
相关知识：
JS事件流——描述的是从页面中接收事件的顺序
三个阶段：事件捕获阶段、处于目标阶段、事件冒泡阶段
如何实现先冒泡后监听? 对同一个时间监听捕获和冒泡，分别处理响应的函数，监听到捕获时先暂缓执行，直到冒泡事件被捕获后再执行捕获。

const div1 = document.getElementById('div1')
div1.addEventListener('click', e =>{
  e.preventDefault() // 阻止默认的行为
  console.log('监听成功')
})

addEventListener是W3C DOM规范中提供的事件监听器方法，element.addEventListener(event, function, useCapture)

三个参数(String, fn, boolean)，第三个是可选参数
useCapture：false是默认值，表示事件句柄在冒泡阶段执行；true则表示在捕获阶段执行。
removeEventListener使用方法相同，IE8及以下不支持，解决：可以使用detachEvent()移除attachEvent()

使用addEventListener和直接元素上写事件attachEvent有区别吗？

• addEventListner能够添加多个事件绑定，按照顺序执行；attachEvent添加事件后不能绑定多个事件，后面的绑定会覆盖前面的
• addEventListner有可选参数useCapture支持在事件捕获阶段（true）或者冒泡阶段（false）绑定；attachEvent只能在时间冒泡阶段捕获
• addEventListner绑定之后还可以使用removeEventListner取消；而普通方式绑定事件之后，不能取消
• addEventListner不支持低版本的IE（attachEvent支持IE）；
• attachEvent的type使用"on"前缀，语法attachEvent(type, callback)

写一个通用的事件监听函数

// 通用的事件绑定函数(既能支持普通，也能支持事件代理)
function bindEvent(element, type, selector, fn){
  if(fn === null){
    // 三个参数的情况下，说明没有设置选择器
    fn = selector
    selector = null
  }
  element.addEventListener(type, e =>{
    const target = e.target
    if(target.matches(selector)){ 
    // 检查target触发事件的节点，是否与我们传入的selector匹配
      fn.call(target, e)
    }else{
      fn(e)
    }
  })
}
// 示例1：只给div1中的a标签绑定事件，其他不管
var div1 = document.getElementById('div1')
bindEvent(div1, 'click', 'a', function(e){
  e.preventDefault()
  console.log(this.innerHTML)
})
// 示例2：只某个id为p1的
标签绑定事件
bindEvent(p1, 'click', function(e){
  console.log('You have clicked this p label')
})

手写call、apply和bind函数

场景: 字节跳动一面
考点：this指向

先来思考： call可以被所有方法调用，所以必然定义在Function的原型上； 绑定函数被调用时，只传入第二个参数及之后的参数 显示绑定this如果调用者函数，被某一个对象所拥有，那么该函数在调用时，内部的this指向该对象。

Function.prototype._call = function(ctx) {
}
fn.call()
fn._call()

Function.prototype.call = function(context){
  const cxt = context || window
  // 将当前被调用的方法定义在cxt.fn上，（以对象调用的形式绑定this）
  cxt.fn = this
  // 获取实参
  const args = Array.from(arguments).slice(1)
  // 以对象调用的形式调用fn,此时的this指向cxt，也是传入的需要绑定的this指向
  const res = arguments.length > 1 ? cxt.fn(...args): cxt.fn()
  // 删除这个方法，避免对传入对象造成污染
  delete cxt.fn
  return res
}

延伸扩展——手写apply函数

除了从参数处理之外，基本和call相同

Function.prototype.apply = function(context){
  const cxt = context || window
  cxt.fn = this
  const res = arguments[1] ? cxt.fn(...arguments[1]) : cxt.fn()
  delete cxt.fn
  return res
}

延伸扩展——手写bind函数

Function.prototype._bind = function(){
  // 无法直接获取参数，利用arguments，将参数解析为数组
  const args = Array.propotype.slice.call(arguments)  
  const _this = args.shift()  // 获取this（数组第一项），剩余的是传递参数
  const self = this  // fn1._bind(...)中的fn1

  return function(){     
    return self.apply(_this, args)  // 执行原函数，返回结果
  }
}
// 示例:验证bind与原生的效果相同
const fn2 = fn1._bind({x:100,y:200},1,23,4)
const res = fn2()
console.log(res)
const fn3 = fn1.bind({x:100,y:200},1,23,4)
const res1 = fn3()
console.log(res1)

call、apply、bind的区别与联系：

• 三者都是改变this指向的函数，param1：this要指向的对象
• call 和 apply 借用其他对象方法，调用立即执行；bind会返回新的函数，不会立即调用
• apply与call的区别是apply第二个是参数组，call则是arg1,arg2,arg3这种形式
• 在确定的参数下，还是最好用call，它的效率会更高，但是在函数的延展性上使用apply更好

手写深拷贝

场景： 字节跳动一面
考点： 简单、复杂数据类型

function deepClone(obj){
  var newObj = obj instanceof Array?[]:{}
  for(var item in obj){
    var temp = typeof obj[item] === 'Object' ? deepClone(obj[item]): obj[item]
    newObj[item] = temp 
  }
  return newObj
}

浅拷贝 vs 深拷贝
浅拷贝智能拷贝一级元素，不能拷贝子元素，相当于仅仅是复制一份引用
深拷贝，则会复制变量值，对于非基本类型的变量，则递归到基本类型的变量之后，再复制。

数据类型判断

场景： 字节跳动一面
考点：typeOf，instance of，Object

console.log(typeOf []) // Object
console.log( [] instanceOf Object ) //true 
console.log( [] instanceOf Array) //true 

typeOf不能用于判断Array类型，返回的总是Object,无法判断是对象还是数组；因此涉及到对Array的判断肯定使用instanceOf

手写debounce和throttle函数

场景： 字节跳动一面
考点： 节流、防抖
题目：写一下项目中你写的节流函数（cc的项目是Vue）
防抖节流就是使用定时器实现我们的目的，防抖是持续触发一段时间后触发，节流是每隔一段时间触发

Vue项目中的防抖和节流（如果多处使用，放在public.js）

// 节流函数
function throttle(fn, delay = 200){
  let timer = null
  return function(){
    if(timer){
      return
    }
    timer = setTimeout(() => {
      fn.apply(this, arguments)
      timer = null
    },delay)
  }
}
// 示例
div.addEventListener('drag', throttle((e)=>{
  console.log(e.offsetX,e.offsetY)
},100))

// 防抖函数
function debounce(fn, delay = 200){ 
  let timer = null
  return function(){     
    if(timer){
      clearTimeout(timer)
    }
    timer = setTimeout(function(){
      timer = null
      fn.apply(this,arguments)
    }, delay)
  }
}
// 示例
input = document.getElementById('input1')
input.addEventListener('keyup', debounce(() => {
  cosole.log(input.value)
}),500)

手写闭包

考点：闭包、作用域
例题：手写一个闭包实现隐藏数据的效果

function createCache() {
  const data = {}
  return {
    set: function(key, value){
      data[key] = value
    }
    get: function(key){
      return data[key]
    }
  }
}
// 定义闭包对象，实现对闭包内部变量的隐藏，只能通过get和set访问
const c = createCache()
c.set('age', 24)
console.log('age:' + c.get('age'))

闭包的诸多应用：模仿块级作用域；保存外部函数的变量；封装私有变量；隐藏数据

var 和 let

场景： 蚂蚁金服一面、字节跳动一面
考点： let, var的区别，变量提升的理解

以下程序的运行结果是什么？为什么？

for(let i = 0; i < 5; i++){
  let i = 3
  console.log(i)
}

output:

3
3
3
3
3

for(var i = 0; i < 5; i++){
  let i = 3  
  console.log(i)  
}

同上

for(var i = 0; i < 5; i++){
  var i = 3
  console.log(i)
}

output : 无数个3

console.log(a)
var a = 5

output: undefined

知识回忆：
var不可以重复声明，var可以变量提升，作用域是全局，但只是变量声明的提升，赋值不会提升
let允许重复声明，let不会变量提升，只在声明后的块状作用域内有效

setTimeout函数

场景：字节跳动一、二面
考点： 观察程序结果、谈对异步的理解

for(var i = 0； i < 5; i++){
  setTimeout(function(){
    console.log(i)
  },1000)
}

结果是： 5 5 5 5 5
如果想输出： 0 1 2 3 4 , 将var改为let,考察变量的作用域

setTimeout(function(){
  console.log(5)
},1)
}

setTimeout的时间设置小于4ms的时候相当于没有延迟,不起作用

console.log('script start')
let promise1 = new Promise(function (resolve) {
  console.log('promise1')
  resolve()
  console.log('promise1 end')
  }).then(function () {
    console.log('promise2')}
  )
setTimeout(function(){
  console.log('settimeout')
}, 1000)
console.log('script end')

result:

script start
promise1
promise1 end
script end
promise2
settimeout

JS是单线程语言，同步会阻塞进程，异步则不会

DOM树的遍历

场景：字节跳动二面
考点：DOM、DFS
题目描述：打印DFS遍历的DOM数序列，
Output: [“div”, “span”, “a”, “div”, “a”, “span”, “p”]

DOM的属性和操作：

• 新增/插入节点 createElement('p') 、appendChild(p1)
• 获取子节点列表childNodes，获取父元素 parentNode
• 删除子节点, removeChild(node)

DOM性能的优化：

• 避免频繁地进行DO操作
• 对DOM的查询结果做缓存
• 将频繁的操作改为一次性操作

DFS遍历DOM树（递归&非递归）

// DFS遍历,递归
var res = []
var dfsDOM = function(node){
  if(node){
    res.push(node)
    let children = node.childrenNodes
    children.forEach((item)=>{
      dfsDOM(item)
    })
  }
}
// DFS遍历，非递归(栈)
var dfsDOM = function(node){
  var res = [] // 已遍历的节点
  if(node){
    var nodesList = [] // 待遍历的节点栈
    nodesList.push(node)
    while(nodesList.length > 0){
      let curNode = nodesList.pop() //弹出栈顶的元素，放入res,表示遍历过
      res.push(curNode)
      let children = curNode.childrenNodes
      // 逆序的把当前节点的孩子节点都放入栈中（保证弹出时顺序正确）
      for(let i = children.length-1; i >= 0; i--){
        nodeList.push(childen[i])
      }
    }
  }
  return res
}

BFS遍历DOM树（递归&非递归）

// BFS遍历,递归
var res = []
var bfsDOM = function(node){
  if(res.indexOf(node)===-1){
    res.push(node)
  }
  let children = node.childrenNodes
  children.forEach((item) => {
    if(item){
      res.push(item) // 存储当前节点的所有非空子节点，放入res表示遍历过
    }
  })
  // 继续对所有子节点的子节点进行递归遍历
  children.forEach((item) =>{
    bfsDOM(item)
  })
  return res
}
// BFS遍历，非递归（队列）
var bfsDOM = function(node){
  var res = [] // 已遍历
  var nodeList = [] // 待遍历
  nodeList.push(node)
  while(nodeList.length > 0){
    var curNode = nodeList.shift(0)
    res.push(curNode)
    let children = curNode.childrenNodes
    children.forEach((item) => {
      nodeList.push(item)
    })
  }
  return res
}

延伸扩展——如何高效的插入多个DOM节点，考虑性能
例题： 在name为list的div下面插入10个 li 列表项
思路： 逐个频繁插入是损耗DOM性能的，于是利用上面的第三点 将频繁的操作改为一次性的操作，先创建文档片段，作为一个临时的存储空间，创建多个li并放入，最后整体插入到DOM树中，这样就只需要执行一次DOM操作了。

const listDiv = document.getElementById('list')
// 创建文档片段，此时未插入dom树
const frag = document.createDocumentFragment()
// 执行插入
for(let i = 1; i <= 10; i++){
  const li = document.createElement('li')
  li.innerHTML = `List Item-${i}`
  frag.appendChild(li)
}
// 都加载完成之后，再将整个插入到DOM树
listDiv.appendChild(frag)

手写链式调用

场景： 美团二面
考点： 方法链
题目： 设计一个累加功能的方法链的封装，可以无限累加，并且可以获取累加的值

function continueAdd(){
  var a = 3
}
continueAdd.prototype.add = function(){
  a += arguments[0]
  return this
}
continueAss.prototype.get = function(){
  return a
}
// 示例
let n = new numberAdd()
console.log(n.add(5).add(8).add(1))
console.log(n.get())

原型与原型链

场景： 腾讯WXG一面
考点： OOP，原型及原型链__proto__
题目：实现一个 GoodMan类， 要求如下

1）GoodMan("Tom")

输出: I am Tom

2）GoodMan("Tom").rest(10).learn("computer")
输出:

I am Tom
//等待10秒
Start learning after 10 seconds
Learning computer

3）GoodMan("Tom").restFirst(5).learn("Chinese")
输出:

//等待5秒
Start learning after 5 seconds
I am Tom
Learning Chinese

具体实现如下：

// 构建GoodMan类
function GoodMan(name){
  var _this = {}
  _this.__proto__ = arguments.callee.prptotype
  _this.name = `I am ${name}`
  setTimeout(_this.setTimePrint.bind(_this))
  return _this
}
GoodMan.prototype.learn = function(subject){
  this._learn = subject
  return this
}
// 在学习学科之前的休息
Goodman.prptotype.rest = function(cnt){
  this._rest = cnt
  return this
}
// 自我介绍前的休息
GoodMan.prototype.restFirst = function(cnt){
  this._rest = 0
  this._restFirst = cnt
  return this
}
// 自定义restFirst执行时的延迟函数
GoodMan.prototype.delay = function(){
  const d  = new Date()
  const n = this._restFirst*1000
  for(let i = 0; i < d; i++){
    if(new Date() - d > n){
      return false
    }
  }
}
// 两个rest函数与其他操作的逻辑实现，输出顺序的控制
GoodMan.prototype.setTimePrint = function(){
  var { name, _learn, _rest, _restFirst } = this
  var cnt = _rest || _restFirst
  
  if(_restFirst !== undefined){
    this.delay()
  }else{
    console.log(name) // 自我介绍
  }
  
  if(cnt){
    // 延迟后执行的内容们
    console.log(`Start learning after ${cnt} seconds`)
    setTimeout(function(){
      if(_restFirst !== undefined){
        console.log(name)
      }
      if(_learn){
        console.log(`Learning ${_learn}`)
      }
    }, _rest*1000)
  }
}

编写查询函数

已知有两个接口[GET] /api/user/get?id= 根据 id 获取用户的年级和班级

• 传入用户 id
• 返回 json body: { id, name, grade, class }

[GET] /api/user/search?query=根据查询内容返回符合条件的用户列表

• 传入字符串 query
• 返回 json body: [{ id, name },…]

题目：要求编写一个查询函数，根据传入字符串 query 来返回满足条件的用户的详情列表即：返回 json body: [{ id,name, grade, class }, …]

vegetable-chicken cc 总结：

算法题一般都来源于我们的日常做题，而其他前端基础题虽然考察形式千变万化，但实际上都是知识点的形式迁移，只要掌握了知识点及相关原理，观察和分析程序的运行结果便不在话下。