关于javascript:面试题100道JS代码实现题

前言

前几个星期在找工作，刷了100多道题目，在这里总结一下

1. 实现curry

const join = (a, b, c) => {   return `${a}_${b}_${c}`}const curriedJoin = curry(join)curriedJoin(1, 2, 3) // '1_2_3'curriedJoin(1)(2, 3) // '1_2_3'curriedJoin(1, 2)(3) // '1_2_3'// 实现curryconst curry = (fn, ...initParams) => {  return (...args) => {    return ((params) => {      return params.length >= fn.length ? fn(...params) : curry(fn, ...params)     })([ ...initParams, ...args])  }}

2. 实现反对placeholder的curry()

/** * 合并参数（替换占位符） */function merge(params1, params2) {  for (let i = 0; i < params1.length; i += 1) {    if (params2.length) {      if (typeof params1[i] === 'symbol') {        const first = params2.shift()        params1[i] = first      }    } else {        break    }  }  return [...params1, ...params2]}/** * @param { (...args: any[]) => any } fn * @returns { (...args: any[]) => any } */function curry(fn, ...initParams) {  return (...args) => {    const params = merge([...initParams], [...args])    return ((params) => {      params = params.slice(0, fn.length)      // 判断是否能够执行      const isCall = params.filter((item) => typeof item !== 'symbol').length >= fn.length      return isCall ? fn(...params) : curry(fn, ...params)     })(params)  }}curry.placeholder = Symbol()

3. 实现Array.prototype.flat()

/** * @param { Array } arr * @param { number } depth * @returns { Array } */function flat(arr, depth = 1) {  const result = []  if (depth) {    let isExistArray = false;    for (let i = 0; i < arr.length; i += 1) {      const item = arr[i]      if (Array.isArray(item)) {        isExistArray = true        result.push(...item)      } else {        result.push(item)      }    }    if (isExistArray) {      return flat(result, depth - 1)    } else {      return result    }  } else {    return arr  }}

4. 手写throttle()

/** * @param {Function} func * @param {number} wait */function throttle(func, wait) {  let timer  let lastArgs  return function (...param) {    if (!timer) {      func.call(this, ...param)      timer = window.setTimeout(() => {        lastArgs && func.call(this, ...lastArgs)        lastArgs = null        timer = null      }, wait)    } else {      lastArgs = [...param]    }  }}

6. 手写debounce()

/** * @param {Function} func * @param {number} wait */function debounce(func, wait) {  let timer  return function (...param) {    function clear() {      window.clearTimeout(timer)      timer = null    }    function run() {      timer = window.setTimeout(() => {        func.call(this, ...param)        clear()      }, wait)    }    if (!timer) {      run()    } else {      clear()      run()    }  }}

8. 手写shuffle()随机打乱一个数组（实现一个洗牌算法）

/**  * @param {any[]} arr  */function shuffle(arr) {  for (let i = 0; i < arr.length; i += 1) {    const j = i + Math.floor(Math.random() * (arr.length - 1));    [arr[i], arr[j]] = [arr[j], arr[i]]  }  return arr}

9. 解密音讯

/** * @param {string[][]} message * @return {string} */function decode(message) {  // 为空的判断  if (!message.length || !message[0].length) {    return ''  }  let power = true  let str = ''  let i = 0  let j = 0  let direction = 'LowerRight' // LowerRight | UpperRight  let w = message[0].length  let h = message.length  function lowerRight() {    if (i + 1 < h && j + 1 < w) {      i = i + 1      j = j + 1    } else {      if (i - 1 > 0 && j + 1 < w) {        direction = 'UpperRight'        i = i - 1        j = j + 1      } else {        power = false      }    }  }  function upperRight() {    if (i - 1 > 0 && j + 1 < w) {      i = i - 1      j = j + 1    } else {      if (i + 1 < h && j + 1 < w) {        direction = 'LowerRight'        i = i + 1        j = j + 1      } else {        power = false      }    }  }  while (power) {    str += message[i][j]    if (direction === 'LowerRight') {      lowerRight()    } else if (direction === 'UpperRight') {      upperRight()    }  }  return str}

10. 找出第一个不良版本

/* type TypIsBad = (version: number) => boolean *//** * @param {TypIsBad} isBad  */function firstBadVersion(isBad) {  return (version) => {    let start = 0    let end = version    let result = isBad(version) ? version : -1    while (end >= start) {      let midd = Math.floor((start + end) / 2)      if (isBad(midd)) {        // 如果是坏的        end = midd - 1        result = midd      } else {        // 如果是好的        start = midd + 1      }    }    return result  }}

11. 什么是Composition?实现pipe()

/** * @param {Array<(arg: any) => any>} funcs  * @return {(arg: any) => any} */function pipe(funcs) {    return function (arg) {        let param = arg        for (let i = 0; i < funcs.length; i += 1) {            const func = funcs[i]            param = func(param)        }        return param    }}

13. 利用栈(Stack)创立队列(Queue)

class Stack {  constructor () {    this.stack = []  }  push(element) {    this.stack.push(element)  }  peek() {    return this.stack[this.stack.length - 1]  }  pop() {    return this.stack.pop()  }  size() {    return this.stack.length  }}// 应用Stack实现Queueclass Queue {  constructor () {    this.enqueueStack = new Stack()    this.dequeueStack = new Stack()  }  _enqueueSyncDequeue () {    const dequeueTemp = new Stack()    const enqueueTemp = new Stack()    while (this.enqueueStack.size()) {      const p = this.enqueueStack.pop()      dequeueTemp.push(p)      enqueueTemp.push(p)    }    while (enqueueTemp.size()) {      this.enqueueStack.push(enqueueTemp.pop())    }    this.dequeueStack = dequeueTemp  }  _dequeueSyncEnqueue () {    const dequeueTemp = new Stack()    const enqueueTemp = new Stack()    while (this.dequeueStack.size()) {      const p = this.dequeueStack.pop()      dequeueTemp.push(p)      enqueueTemp.push(p)    }    while (dequeueTemp.size()) {      this.dequeueStack.push(dequeueTemp.pop())    }    this.enqueueStack = enqueueTemp  }  enqueue(element) {     this.enqueueStack.push(element)    this._enqueueSyncDequeue()  }  peek() {     return this.dequeueStack.peek()  }    dequeue() {    const p = this.dequeueStack.pop()    this._dequeueSyncEnqueue()    return p  }  size() {     return this.enqueueStack.size()  }}// 改进版class Queue {  constructor () {    this.stack = new Stack()    this.queue = new Stack()  }  enqueue(element) {     while (this.queue.size()) {      this.stack.push(this.queue.pop())    }    this.queue.push(element)    while (this.stack.size()) {      this.queue.push(this.stack.pop())    }  }  peek() {     return this.queue.peek()  }    dequeue() {    return this.queue.pop()  }  size() {     return this.queue.size()  }}

14. 实现`memo()`

/** * @param {Function} func * @param {(args:[]) => string }  [resolver] - cache key generator */function memo(func, resolver) {  const map = new Map();  return function (...params) {    let key    if (typeof resolver === 'function') {      key = resolver(...params)    } else {      key = [...params].join('-')    }    if (map.has(key)) {      return map.get(key)    } else {      const val = func.apply(this, [...params])      map.set(key, val)      return val    }  }}

15. 实现相似jQuery的DOM wrapper

/** * @param {HTMLElement} el - element to be wrapped */function $(el) {  el.css = function (key, value) {    el.style[key] = value    return el  }  return el}

16. 实现一个Event Emitter

// please complete the implementationclass EventEmitter {  constructor () {    this.map = {}  }  subscribe(eventName, callback) {    const event = {eventName, callback}    const that = this    if (this.map[eventName]) {      this.map[eventName].push(event)    } else {      this.map[[eventName]] = [event]    }    return {      release () {        that.map = {          ...that.map,          [eventName]: that.map[eventName].filter((e) => e !== event)        }      }    }  }    emit(eventName, ...args) {      if (this.map[eventName]) {      this.map[eventName].forEach((event) => {        const { callback } = event        callback(...args)      })    }  }}

17. 实现一个DOM element store

class NodeStore {  constructor () {    this.map = {}  }  /**  * @param {Node} node  * @param {any} value  */  set(node, value) {    if (!node.__mapKey__) {      node.__mapKey__ = Symbol()      this.map[node.__mapKey__] = value    } else {      this.map[node.__mapKey__] = value    }  } /**  * @param {Node} node  * @return {any}  */  get(node) {    return this.map[node.__mapKey__]  }  /**  * @param {Node} node  * @return {Boolean}  */ has(node) {   return !!node.__mapKey__ && node.__mapKey__ in this.map }}

18. 优化一个function

优化前的工夫复杂度O(m * n)

// items是一个array// 蕴含的元素有 >=3 个属性let items = [  {color: 'red', type: 'tv', age: 18},   {color: 'silver', type: 'phone', age: 20},  {color: 'blue', type: 'book', age: 17}] // 一个由key和value组成的arrayconst excludes = [   {k: 'color', v: 'silver'},   {k: 'type', v: 'tv'},   ...] function excludeItems(items, excludes) {   excludes.forEach( pair => {     items = items.filter(item => item[pair.k] === item[pair.v])  })   return items}

优化后：

function excludeItems(items, excludes) {   const excludesMap = {}  excludes.forEach(({k, v}) => {    if (excludesMap[k]) {      excludesMap[k].add(v)    } else {      excludesMap[k] = new Set()      excludesMap[k].add(v)    }  })  return items.filter((item) => {    return Object.keys(item).every((key) => {      if (excludesMap[key]) {        return !excludesMap[key].has(item[key])      }      return true    })  })}

19. 雷同构造的DOM tree下面寻找对应的节点

/** * @param {HTMLElement} rootA * @param {HTMLElement} rootB - rootA and rootB are clone of each other * @param {HTMLElement} nodeA */const findCorrespondingNode = (rootA, rootB, target) => {  const paths = []  let isSearchEnd = false  let targetB = rootB  const find = (node, index) => {    if (index !== undefined && !isSearchEnd) {      paths.push(index)    }    if (node !== target) {      const children = [...node.children]      children.forEach((item, index) => {        find(item, index)      })      if (!isSearchEnd) {        paths.pop()      }    } else {      isSearchEnd = true    }  }  find(rootA)  if (paths.length !== 0) {    while (paths.length) {      const index = paths.shift()      targetB = [...targetB.children][index]    }  }  return targetB}

20. 检测 data type

/** * @param {any} data * @return {string} */function detectType(data) {  if(data instanceof FileReader) {    return 'object'  }  const type = Object.prototype.toString.call(data);  return /^\[object\s+([A-Za-z]+)\]$/.exec(type)[1].toLocaleLowerCase()}

21. 手写JSON.stringify()

/** * @param {any} data * @return {string} */function stringify(data) {  if(typeof data === 'bigint') {    throw new Error()  }   if(typeof data === 'string') {    return `"${data}"`  }   if(typeof data === 'function') {    return undefined;  }  if(data !== data) {    return 'null'  }  if(data === Infinity) {    return 'null'  }  if(data === -Infinity) {    return 'null'  }  if(typeof data === 'number') {   return `${data}`  }  if(typeof data === 'boolean') {    return `${data}`  }  if(data === null) {    return 'null'  }  if(data === undefined) {    return 'null'  }  if(typeof data === 'symbol') {    return 'null'  }  if(data instanceof Date) {    return `"${data.toISOString()}"`  }  if (Array.isArray(data)) {    const arr = data.map((item) => stringify(item))    return `[${arr.join(',')}]`  }  if (typeof data === 'object') {    const arr = []    Object.entries(data).forEach(([key, value]) => {      if (value !== undefined) {        arr.push(`"${key}":${stringify(value)}`)      }    })    return `{${arr.join(',')}}`  }}

22. 手写JSON.parse()

/** * @param {any} data * @return {string} */function parse(data) {  function equal(text) {    if (text && text !== current) {      throw new Error()    }    return true  }  function next() {    current = text.charAt(index)    index += 1    return current  }  function white() {    while (current && current == ' ') {      next()    }  }  function object() {    let key    let obj = Object.create(null)    if (current === '{') {      next()      white()      if (current === '}') {        next()        return obj      }      while (current) {        key = string()        // 读取下一个非空的字符        white()        // 下一个非空字符应该是":", 否则就抛出谬误        equal(':')        next()        obj[key] = value()        // 读取下一个非空的字符        white()        if (current === '}') {          next()          return obj        }        // 如果不是'}', 下一个字符应该是',', 否则就抛出谬误        equal(',')        // 读取下一个非空的字符        white()      }    }    throw new Error()  }  function string() {    let str = ''    if (current === '"') {      let startIndex = index      while (next()) {        if (current === '"') {          if (index - 1 > startIndex) {            str += text.substring(startIndex, index - 1)          }          next()          return str        }      }    } else {      throw new Error()    }  }  function array() {    let arr = []    if (current === '[') {      next()      // 读取下一个非空字符串      white()      if (current === ']') {        next()        return arr      }      while (current) {        // 读取数组的内容        arr.push(value())        // 读取下一个字符        white()        if (current === ']') {          next()          return arr        }        equal(',')        next()        white()      }    }    throw new Error()  }  function number() {        let number = ''    let string = ''    if (current === '-') {      string = ''      next()    }    let temp = Number(current)    while (temp >= 0 && temp <= 9 && current) {      string += current      next()      temp = Number(current)    }    if (current === '.') {      string += '.'      next()      temp = Number(current)      while (temp >= 0 && temp <= 9 && current) {        string += current        next()        temp = Number(current)      }    }    number = Number(string)    return number  }  function word() {    switch (current) {      case 't':        next()        equal('r')        next()        equal('u')        next()        equal('e')        next()        return true      case 'f':        next()        equal('a')        next()        equal('l')        next()        equal('s')        next()        equal('e')        next()        return false      case 'n':        next()        equal('u')        next()        equal('l')        next()        equal('l')        next()        return null    }    throw new Error()  }  function value() {    white()    switch (current) {      // 如果是对象      case '{':        return object()      // 如果是数组      case '[':        return array()      // 如果是字符串      case '"':        return string()      // 如果蕴含负号，阐明是数字      case "-":        return number()      default:        let temp = Number(current)        if (temp >= 0 && temp <= 9) {          return number()        } else {          return word()        }    }  }  let text = data + ''  let index = 0  let current = ' '  let result = value()  white()  if (current) {    throw new Error()  }  return result}

23. 实现一个sum()办法

/** * @param {number} num */function sum(num) {  const fn = function (arg) {    return sum(num + arg)  }  fn.toString = function () {    return num  }  return fn}

24. 用JavaScript手写一个Priority Queue

// complete the implementationclass PriorityQueue {  /**   * @param {(a: any, b: any) => -1 | 0 | 1} compare -    * compare function, similar to parameter of Array.prototype.sort   */  constructor(compare) {    this.compare = compare;  }  /**   * return {number} amount of items   */  size() {  }  /**   * returns the head element   */  peek() {  }  /**   * @param {any} element - new element to add   */  add(element) {     }  /**   * remove the head element   * @return {any} the head element   */  poll() {      }}

25. 更新数组的程序

/** * @param {any[]} items * @param {number[]} newOrder * @return {void} */// 不实用额定空间function sort(items, newOrder) {  // 应用简略的冒泡排序  for (let i = 0; i < items.length; i += 1) {    for (let j = i + 1; j < items.length; j += 1) {      if (newOrder[i] > newOrder[j]) {        // 更新items的程序以及newOrder的程序        let otemp = newOrder[j]        let itemp = items[j]        newOrder[j] = newOrder[i]        newOrder[i] = otemp        items[j] = items[i]        items[i] = itemp      }    }  }  return items}

26. 实现Object.assign()

/** * @param {any} target * @param {any[]} sources * @return {object} */ function objectAssign(target, ...sources) {  if (target === null || target === undefined) {    throw new Error()  }   if (typeof target === 'number') {    target = new Number(target)  }  if (typeof target === 'boolean') {    target = new Boolean(target)  }  if (typeof target === 'string') {    target = new String(target)  }  sources.forEach(source => {    if (source === undefined || source === null) {      return    }    Object.defineProperties(      target,      Object.getOwnPropertyDescriptors(source)    )  })  return target}

27. 实现completeAssign()

function completeAssign(target, ...sources) {  if (target === null || target === undefined) {    throw new Error()  }   if (typeof target === 'number') {    target = new Number(target)  }  if (typeof target === 'boolean') {    target = new Boolean(target)  }  if (typeof target === 'string') {    target = new String(target)  }  sources.forEach(source => {    if (source === undefined || source === null) {      return    }    Object.defineProperties(      target,      Object.getOwnPropertyDescriptors(source)    )  })  return target}

28. 实现clearAllTimeout()

const beforeSetTimeout = window.setTimeoutwindow.timers = new Set()// 重写setTimeoutwindow.setTimeout = function (handler, timeout, ...arg) {  const that = this  const timer = beforeSetTimeout(    function (...arg) {      handler.apply(that, [...arg])    },    timeout,    ...arg  )  window.timers.add(timer)  return timer}/** * cancel all timer from window.setTimeout */function clearAllTimeout() {  window.timers.forEach((timer) => {    window.clearTimeout(timer)  })}

29. 实现async helper - `sequence()`

/*type Callback = (error: Error, data: any) => voidtype AsyncFunc = (   callback: Callback,   data: any) => void*/function promisify(func) {  return function (num) {    return new Promise(function(resolve, reject) {      func(function (err, data) {        if (err) {          reject(err)        } else {          resolve(data)        }      }, num)    })  }}/** * @param {AsyncFunc[]} funcs * @return {(callback: Callback) => void} */function sequence(funcs) {  funcs = funcs.map(func => promisify(func))  return async function (callback, data) {    try {      for (let i = 0; i < funcs.length; i += 1) {        data = await funcs[i](data)      }      callback(undefined, data)    } catch (error) {      callback(error, undefined)    }  }}

30. 实现async helper - `parallel()`

/*type Callback = (error: Error, data: any) => voidtype AsyncFunc = (   callback: Callback,   data: any) => void*/function promisify(func) {  return function (...args) {    return new Promise(function(resolve, reject) {      func(function (err, data) {        if (err) {          reject(err)        } else {          resolve(data)        }      }, ...args)    })  }}/** * @param {AsyncFunc[]} funcs * @return {(callback: Callback) => void} */function parallel(funcs){  funcs = funcs.map(func => promisify(func))  return function (callback, data) {    let count = 0    let handleError = false    const result = []    for (let i = 0; i < funcs.length; i += 1) {      funcs[i](data).then(function (res) {        result[i] = res        count += 1        if (count === funcs.length) {          callback(undefined, result)        }      }).catch(function (err) {        if (!handleError) {          callback(err, undefined)          handleError = true        }      })    }  }}

31. 实现async helper - `race()`

/*type Callback = (error: Error, data: any) => voidtype AsyncFunc = (   callback: Callback,   data: any) => void*/function promisify(func) {  return function (...args) {    return new Promise(function(resolve, reject) {      func(function (err, data) {        if (err) {          reject(err)        } else {          resolve(data)        }      }, ...args)    })  }}/** * @param {AsyncFunc[]} funcs * @return {(callback: Callback) => void} */function race(funcs){  funcs = funcs.map(func => promisify(func))  return function (callback, data) {    let handleEnd = false    for (let i = 0; i < funcs.length; i += 1) {      funcs[i](data).then(function (res) {        if (!handleEnd) {          callback(undefined, res)        }        handleEnd = true      }).catch(function (err) {        if (!handleEnd) {          callback(err, undefined)        }        handleEnd = true      })    }  }}

32. 实现`Promise.all()`

/** * @param {Array<any>} promises - notice input might have non-Promises * @return {Promise<any[]>} */function all(promises) {  return new Promise((resolve, reject) => {    if (!promises.length) {      return resolve([])    }    const result = [];    let count = 0;    for (let i = 0; i < promises.length; i++) {      const promise = promises[i] instanceof Promise ? promises[i] : Promise.resolve(promises[i])      promise.then((res) => {        result[i] = res        count += 1        if (count === promises.length) {          resolve(result)        }      }).catch((err) => {        reject(err)      })    }  })}

33. 实现`Promise.allSettled()`

/** * @param {Array<any>} promises - notice that input might contains non-promises * @return {Promise<Array<{status: 'fulfilled', value: any} | {status: 'rejected', reason: any}>>} */function allSettled(promises) {  return new Promise((resolve, reject) => {    if (!promises.length) {      return resolve([])    }    const result = [];    let count = 0;    for (let i = 0; i < promises.length; i++) {      const promise = promises[i] instanceof Promise ?        promises[i] :        Promise.resolve(promises[i])      promise.then((res) => {        result[i] = {status:"fulfilled",value: res}        count += 1        if (count === promises.length) {          resolve(result)        }      }).catch((err) => {        result[i] = {status:"rejected",reason: err}        count += 1        if (count === promises.length) {          resolve(result)        }      })    }  })}

34. 实现`Promise.any()`

/** * @param {Array<Promise>} promises * @return {Promise} */function any(promises) {  return new Promise((resolve, reject) => {    if (!promises.length) {      return reject(        new AggregateError(          'No Promise in Promise.any was resolved',           []        )      )    }    const errors = [];    let count = 0;    for (let i = 0; i < promises.length; i += 1) {      const promise = promises[i] instanceof Promise ? promises[i] : Promise.resolve(promises[i])      promise.then((res) => {        resolve(res)      }).catch((err) => {        errors[i] = err        count += 1        if (count === promises.length) {          reject(            new AggregateError(              'No Promise in Promise.any was resolved',               errors            )          )        }      })    }  })}

35. 实现`Promise.race()`

/** * @param {Array<Promise>} promises * @return {Promise} */function race(promises) {  return new Promise((resolve, reject) => {    if (promises.length) {      for (let i = 0; i < promises.length; i += 1) {        const promise = promises[i] instanceof Promise ?          promises[i]          :          Promise.resolve(promises[i])        promise.then((res) => {          resolve(res)        }).catch((err) => {          reject(err)        })      }    }  })}

37. 手写Binary Search (unique)

/** * @param {number[]} arr - ascending unique array * @param {number} target * @return {number} */function binarySearch(arr, target){  if (arr.length === 0) return -1    const _binarySearch = (arr, base) => {    if (arr.length) {      const midd = Math.floor(arr.length / 2)      if (arr[midd] === target) {        return midd + base      } else if (arr[midd] > target) {        return _binarySearch(arr.splice(midd + 1), midd)      } else {        return _binarySearch(arr.splice(0, midd), base)      }    } else {      return -1    }  }  return _binarySearch([...arr], 0)}

38. 实现`jest.spyOn()`

/** * @param {object} obj * @param {string} methodName */function spyOn(obj, methodName) {  if (!(obj[methodName] instanceof Function)) {    throw new Error()  }  const before = obj[methodName]  const calls = []  obj[methodName] = function (...args) {    calls.push([...args])    before.call(this, ...args)  }  return {    calls  }}

39. 手写range()

/** * @param {integer} from * @param {integer} to */function range(from, to) {  const result = []  while (from <= to) {    result.push(from)    from += 1  }  return result}

40. 手写冒泡排序

/** * @param {number[]} arr */ function bubbleSort(arr) {  for (let i = 0; i < arr.length; i += 1) {    for (let j = i + 1; j < arr.length; j += 1) {      if (arr[i] > arr[j]) {        [arr[i], arr[j]] = [arr[j], arr[i]]      }    }  }  return arr}

41. 手写归并排序

// Note: 须要间接在原数组上批改function merge (left, right) {  const arr = []  while (left.length && right.length) {    if (left[0] > right[0]) {      arr.push(right.shift())    } else {      arr.push(left.shift())    }  }  return [...arr, ...left, ...right]}/** * @param {number[]} arr */function mergeSort(arr) {  if (arr.length <= 1) {    return arr  }  const midd = Math.floor(arr.length / 2)  const left = arr.splice(0, midd)  return merge(mergeSort(left), mergeSort(arr))}// 原地批改// 递归最外层的right就是原数组function merge (left, right) {  const arr = []  while (left.length && right.length) {    if (left[0] > right[0]) {      arr.push(right.shift())    } else {      arr.push(left.shift())    }  }  while (arr.length) {    right.unshift(arr.pop())  }  if (left.length) {    right.push(left.pop())  }  return right}/** * @param {number[]} arr */function mergeSort(arr) {  if (arr.length <= 1) {    return arr  }  const midd = Math.floor(arr.length / 2)  const left = arr.splice(0, midd)  return merge(mergeSort(left), mergeSort(arr))}

42. 手写插入排序

/** * @param {number[]} arr */function insertionSort(arr) {  for (let i = 0; i < arr.length; i += 1) {    for (let j = i + 1; j < arr.length; j += 1) {      if (arr[i] > arr[j]) {        const item = arr.splice(j,1)[0]        arr.splice(i,0,item)      }    }  }  return arr}

43. 手写疾速排序

// Note: 须要间接在原数组上批改/** * @param {number[]} arr */function quickSort(arr) {  if (arr.length <= 1) {    return arr  }  const referenceValue = arr[0]  const max = []  const min = []  for (let i = 1; i < arr.length; i += 1) {    if (arr[i] >= referenceValue) {      max.push(arr[i])    } else {      min.push(arr[i])    }  }  return quickSort(min).concat(referenceValue, quickSort(max))}// 原地批改/** * @param {number[]} arr */function quickSort(arr) {  if (arr.length <= 1) {    return arr  }  const referenceValue = arr[0]  let max = []  let min = []  for (let i = 1; i < arr.length; i += 1) {    if (arr[i] >= referenceValue) {      max.push(...arr.splice(i,1))    } else {      min.push(...arr.splice(i,1))    }    i -= 1  }  min = quickSort(min)  max = quickSort(max)  while (max.length) {    arr.push(max.shift())  }  while (min.length) {    arr.unshift(min.pop())  }  return arr}

44. 手写抉择排序

/** * @param {number[]} arr */function selectionSort(arr) {  for (let i = 0; i < arr.length; i += 1) {    let minIndex = i    for (let j = i + 1; j < arr.length; j += 1) {      if (arr[j] < arr[minIndex]) {        minIndex = j      }    }    const min = arr.splice(minIndex, 1)[0]    arr.splice(i, 0, min)  }  return arr}

45. 在未排序的数组中找到第K大的元素

// 分治/** * @param {number[]} arr * @param {number} k */function findKThLargest(arr, k) {  let result  const divideAndConquer = (arr, base) => {    if (arr.length <= 1) {      result = arr[0]    }    const min = []    const max = []    let maxLen    const referenceValue = arr[0]    for (let i = 1; i < arr.length; i += 1) {      if (arr[i] > referenceValue) {        max.push(arr[i])      } else {        min.push(arr[i])      }    }    max.push(arr[0])    maxLen = max.length + base    if (maxLen >= k && max.length) {      divideAndConquer(max, base)    } else if (maxLen < k && min.length) {      divideAndConquer(min, maxLen)    }  }  divideAndConquer(arr, 0)  return result}

46. 实现`_.once()`

/** * @param {Function} func * @return {Function} */function once(func) {  let result  let once = true  return function (...args) {    if (once) {      result = func.call(this, ...args)      once = false    }    return result  }}

47. 反转链表

/**  * class Node { *  new(val: number, next: Node); *    val: number *    next: Node * } *//** * @param {Node} list * @return {Node}  */const reverseLinkedList = (list) => {    if (!list) return    const initNode = list    let newHead = initNode    let newHeadNextNode = initNode    while (initNode.next) {        newHead = initNode.next        if (newHead.next) {            initNode.next = newHead.next        } else {            initNode.next = null        }        newHead.next = newHeadNextNode        newHeadNextNode = newHead    }    return newHead}

48. 含有反复元素的数组中返回特定元素的首次呈现的地位

/** * @param {number[]} arr - ascending array with duplicates * @param {number} target * @return {number} */function firstIndex(arr, target){  if (arr.length === 0) return -1  let index = -1  const _firstIndex = (start, end) => {    if (start <= end) {      const midd = Math.floor((start + end) / 2)      if (arr[midd] === target) {        if (index === -1) {          index = midd        } else {          index = Math.min(index, midd)        }        _firstIndex(start, midd - 1)      } else if (arr[midd] > target) {        _firstIndex(start, midd - 1)      } else {        _firstIndex(midd + 1, end)      }    }  }  _firstIndex(0, arr.length - 1)  return index}

49. 含有反复元素的数组中返回特定元素的最初呈现的地位

/** * @param {number[]} arr - ascending array with duplicates * @param {number} target * @return {number} */function lastIndex(arr, target){  if (arr.length === 0) return -1  let index = -1  const _lastIndex = (start, end) => {    if (start <= end) {      const midd = Math.floor((start + end) / 2)      if (arr[midd] === target) {        if (index === -1) {          index = midd        } else {          index = Math.max(index, midd)        }        _lastIndex(midd + 1, end)      } else if (arr[midd] > target) {        _lastIndex(start, midd - 1)      } else {        _lastIndex(midd + 1, end)      }    }  }  _lastIndex(0, arr.length - 1)  return index}

50. 含有反复元素的数组中返回特定元素之前的元素

/** * @param {number[]} arr - ascending array with duplicates * @param {number} target * @return {number} */function firstIndex(arr, target){  if (arr.length === 0) return -1  let index = -1  const _firstIndex = (start, end) => {    if (start <= end) {      const midd = Math.floor((start + end) / 2)      if (arr[midd] === target) {        if (index === -1) {          index = midd        } else {          index = Math.min(index, midd)        }        _firstIndex(start, midd - 1)      } else if (arr[midd] > target) {        _firstIndex(start, midd - 1)      } else {        _firstIndex(midd + 1, end)      }    }  }  _firstIndex(0, arr.length - 1)  return index}/** * @param {number[]} arr - ascending array with duplicates * @param {number} target * @return {number} */function elementBefore(arr, target){  if (arr.length === 0) return undefined  const _firstIndex = firstIndex(arr, target)  if (_firstIndex === 0 || _firstIndex === -1) return undefined  return arr[_firstIndex - 1]}

51. 含有反复元素的数组中返回特定元素的之后的元素

/** * @param {number[]} arr - ascending array with duplicates * @param {number} target * @return {number} */function lastIndex(arr, target){  if (arr.length === 0) return -1  let index = -1  const _lastIndex = (start, end) => {    if (start <= end) {      const midd = Math.floor((start + end) / 2)      if (arr[midd] === target) {        if (index === -1) {          index = midd        } else {          index = Math.max(index, midd)        }        _lastIndex(midd + 1, end)      } else if (arr[midd] > target) {        _lastIndex(start, midd - 1)      } else {        _lastIndex(midd + 1, end)      }    }  }  _lastIndex(0, arr.length - 1)  return index}/** * @param {number[]} arr - ascending array with duplicates * @param {number} target * @return {number} */function elementAfter(arr, target){  if (arr.length === 0) return undefined  const _lastIndex = lastIndex(arr, target)  if (_lastIndex === arr.length - 1 || _lastIndex === -1) return undefined  return arr[_lastIndex + 1]}

53. 实现middleware

class Middleware {  constructor () {    this.callbacks = []    this.handleErrors = []    this.handleNextError = null  }  // 洋葱模型  _compose(funcs, type) {    if (funcs.length === 0) {      return arg => arg     }    if (funcs.length === 1) {      return funcs[0]    }    if (type === 'callback') {      return funcs.reduce((a, b) => {        return (req, next) => {          return a(req, (err) => {            if (err) {              this.handleNextError(err)            } else {              b(req, next)            }          })        }      })    } else if (type === 'handleError') {      return funcs.reduce((a, b) => {        return (err, req, next) => {          return a(err, req, (err) => {            b(err, req, next)          })        }      })    }  }  /**   * @param {MiddlewareFunc} func   */  use(func) {    if (func.length === 2) {      this.callbacks.push(func)    } else {      this.handleErrors.push(func)    }  }  /**   * @param {Request} req   */  start(req) {    const callback = this._compose(this.callbacks, 'callback')    const handleError = this._compose(this.handleErrors, 'handleError')    this.handleNextError = (err) => {      handleError(err, req, () => {})    }    try {      callback(req, (err) => {        if (err) {          this.handleNextError(err)        }      })    } catch (err) {      handleError(err, req, () => {})    }  }}

const middleware = new Middleware()middleware.use((req, next) => {   console.log(1)   next()   console.log(2)})// since error occurs, this is skippedmiddleware.use((req, next) => {  console.log(3)  next(new Error())  console.log(4)})// since error occurs, this is calledmiddleware.use((error, req, next) => {   console.log(error)   console.log(req)})middleware.start({})

class Middleware {  constructor () {    this.callbacks = []    this.handleErrors = []  }  /**   * @param {MiddlewareFunc} func   */  use(func) {    if (func.length === 2) {      this.callbacks.push(func)    } else {      this.handleErrors.push(func)    }  }  /**   * @param {Request} req   */  start(req) {    let callbackIndex = 0    let handleErrorIndex = 0    const next = (error) => {      const args = [req, next]      let func      if (error) {        func = this.handleErrors[handleErrorIndex]        args.unshift(error)        handleErrorIndex += 1      } else {        func = this.callbacks[callbackIndex]        callbackIndex += 1      }      try {        func && func(...args)      } catch (err) {        next(err)      }    }    next()  }}

蚂蚁金服面试真题: 实现compose

function f(next) {console.log(1);next();console.log(2);}function g(next) {console.log(3);next();console.log(4);}function h(next) {console.log(5);next();console.log(6);}// ((next) => {//   ((next) => {//     return f(() => {//       g(next)//     })//   })(() => { h(next) })// })(() => {//   console.log('ok')// })// 最终须要实现的指标// f(() => {//   g(() => {//     h(() => {//     })//   })// })// 实现composefunction compose(...funcs) {  r  return function () {    return funcs.reduce((a,b) => {      return (next) => {        return a(() => {          b(next)        })      }    })(() => {})  }}// 1,3,5,6,4,2// 第一次返回(next) => f(() => g(next)）// 第二次a: (next) => f(() => g(next)） b: h// 第二次返回 (next) => （(next) => f(() => g(next))(() => h(next))// (next) =>f(() => g(() => h(next)))compose(f,g,h)()

53. 用es5实现`extends`

const myExtends = (SuperType, SubType) => {  function Child (...args) {    SuperType.call(this, ...args)    SubType.call(this, ...args)    // 这里Child其实实质还是SubType，还是这里要批改下    Object.setPrototypeOf(this, SubType.prototype)  }  SubType.prototype = Object.create(SuperType.prototype)  Child.prototype = Object.create(SubType.prototype)  SubType.prototype.constructor = SubType  Child.prototype.constructor = Child  // 模仿es6额定的继承链  Object.setPrototypeOf(Child, SuperType)  return Child}

55. HTML字符串中高亮关键字

// 获取所有关键词的排列组合/** * @param {string} html * @param {string[]} keywords */function highlightKeywords(html, keywords) {  const combination = []  let arr = html.split(' ')  const getCombination = (head, arr) => {    for (let i = 0; i < arr.length; i += 1) {      const temp = [...arr]      temp.splice(i, 1)      const name = `${head}${arr[i]}`      combination.push(name)      getCombination(name, temp)    }  }  getCombination('', keywords)  arr = arr.map((item) => {    if (combination.includes(item)) {      return `<em>${item}</em>`    } else if (keywords.some((keyword) => item.includes(keyword))) {      for (let i = 0; i < keywords.length; i += 1) {        const keyword = keywords[i]        if (item.includes(keyword)) {          const reg = new RegExp(keyword, 'g')          item = item.replace(reg, `<em>${keyword}</em>`)          break        }      }      return item    } else {      return item    }  })  return arr.join(' ')};// 单纯的应用正则

58. 返回DOM tree的高度

/** * @param {HTMLElement | null} tree * @return {number} */function getHeight(tree) {  if (!tree) return 0  const result = []  const bfs = (nodes) => {    if (nodes.length) {      let childs = []      for (let i = 0; i < nodes.length; i += 1) {        const children = nodes[i].children        childs = [...childs, ...children]      }      result.push(childs)      bfs(childs)    }  }  bfs([tree])  return result.length       }

59. 实现browser history

class BrowserHistory {  constructor(url) {    this.history = [url || undefined]    this.index = 0  }  visit(url) {    if (this.index === this.history.length - 1) {      this.history.push(url)    } else {      this.history = this.history.splice(0, this.index + 1)      this.history.push(url)    }    this.index = this.history.length - 1  }    get current() {    return this.history[this.index]  }    goBack() {    this.index -= 1    this.index = this.index < 0 ? 0 : this.index    return this.history[this.index]  }    forward() {    this.index += 1    this.index = this.index > this.history.length - 1 ? this.history.length - 1 : this.index    return this.history[this.index]  }}

60. 实现本人的`new`

/** * @param {Function} constructor * @param {any[]} args - argument passed to the constructor * `myNew(constructor, ...args)` should return the same as `new constructor(...args)` */const myNew = (constructor, ...args) => {  const obj = Object.create({})  const returnValue = constructor.call(obj, ...args)  Object.setPrototypeOf(obj, constructor.prototype)  return returnValue || obj}

61. 实现`Function.prototype.call`

Function.prototype.mycall = function(thisArg, ...args) {  if (thisArg === undefined || thisArg === null) {    thisArg = window  }  if (typeof thisArg === 'string') {    thisArg = new String(thisArg)  }  if (typeof thisArg === 'number') {    thisArg = new Number(thisArg)  }  if (typeof thisArg === 'boolean') {    thisArg = new Boolean(thisArg)  }  const key = Symbol()  thisArg[key] = this  const result = thisArg[key](...args)  delete thisArg[key]  return result}

手写apply

Function.prototype.myapply = function (thisArg, argsArray = []) {  if (!Array.isArray(argsArray)) {    throw new Error()  }  if (thisArg === undefined || thisArg === null) {    thisArg = window  }  if (typeof thisArg === 'string') {    thisArg = new String(thisArg)  }  if (typeof thisArg === 'number') {    thisArg = new Number(thisArg)  }  if (typeof thisArg === 'boolean') {    thisArg = new Boolean(thisArg)  }  const key = Symbol()  thisArg[key] = this  const result = thisArg[key](...argsArray)  delete thisArg[key]  return result}

手写bind

Function.prototype.mybind = function (thisArg, ...initArgs) {  if (thisArg === undefined || thisArg === null) {    thisArg = window  }  if (typeof thisArg === 'string') {    thisArg = new String(thisArg)  }  if (typeof thisArg === 'number') {    thisArg = new Number(thisArg)  }  if (typeof thisArg === 'boolean') {    thisArg = new Boolean(thisArg)  }  const that = this  return function (...args) {    const key = Symbol()    thisArg[key] = that    const result = thisArg[key](...initArgs, ...args)    delete thisArg[key]    return result  }}

63. 手写`_.cloneDeep()`

// 躲避循环援用 Avoid circular referencesconst hash = new WeakMap()function isObject(value) {  return value != null && (typeof value === "object" || typeof value === "function")}function getSymbolKeys(value) {  let keys = Object.getOwnPropertySymbols(value)  keys = keys.filter((key) => value.propertyIsEnumerable(key))  return keys}function getAllKeys(value) {  let keys = Object.keys(value)  keys = [...keys, ...getSymbolKeys(value)]  return keys}function cloneDeep(data) {  let result = null  if (!isObject(data)) {    return data  }  const isArray = Array.isArray(data)  if (isArray) {    result = []  } else {    result = Object.create(Object.getPrototypeOf(data))  }  if (hash.has(data)) {    return hash.get(data)  } else {    hash.set(data, result)  }  const keys = getAllKeys(data)  for (let i = 0; i < keys.length; i += 1) {    const key = keys[i]    const val = data[key]    result[key] = cloneDeep(val)  }  return result}

64. Promise reject的时候主动retry

/** * @param {() => Promise<any>} fetcher * @param {number} maximumRetryCount * @return {Promise<any>} */function fetchWithAutoRetry(fetcher, maximumRetryCount) {  return new Promise(async (resolve, reject) => {    let error    for (let i = 0; i <= maximumRetryCount; i += 1) {      await fetcher().then((res) => {        resolve(res)      }).catch((err) => {        error = err      })    }    reject(error)  })}

65. 增加千位分隔符

/** * @param {number} num * @return {string} */function addComma(num) {  num = `${num}`  const reg = /\B(?=(\d{3})+$)/g  const decimalPlaces = num.split('.')[1]  let integerBits = num.split('.')[0]  integerBits = integerBits.replace(reg, ',')  if (decimalPlaces) {    return `${integerBits}.${decimalPlaces}`  }  return `${integerBits}`  }

66. 去掉数组中的反复元素

/** * @param {any[]} arr */function deduplicate(arr) {  const map = new Map()  for (let i = 0; i < arr.length; i += 1) {    if (map.has(arr[i])) {      arr.splice(i, 1)      i -= 1    } else {      map.set(arr[i], true)    }  }  return arr}

69. 实现`_.isEqual()`

const getSymbolKeys = (obj) => {  let symbolKeys = Object.getOwnPropertySymbols(obj)  symbolKeys = [...symbolKeys].filter((key) => {    return obj.propertyIsEnumerable(key)  })  return symbolKeys}const getAllKeys = (obj) => {  let keys = Object.keys(obj)  keys = [...keys, ...getSymbolKeys(obj)]  return keys}function isObject(value) {  return value != null && (typeof value === "object" || typeof value === "function")}const hash = new WeakMap()/** * @param {any} a * @param {any} b * @return {boolean} */function isEqual(a, b) {  let result = true  const equal = (a, b) => {    if (!isObject(a) || !isObject(b)) {      result = (a === b)      return     }    if (hash.has(a) && hash.has(b)) {      return true    }    const aKeys = getAllKeys(a)    const bKeys = getAllKeys(b)    if (aKeys.length !== bKeys.length) {      result = false      return    }    hash.set(a, true)    hash.set(b, true)    for (let i = 0; i < aKeys.length; i += 1) {      const key = aKeys[i]      const aValue = a[key]      const bValue = b[key]      if (!isObject(aValue) || !isObject(bValue)) {        if (aValue !== bValue) {          result = false          break        }      } else {        isEqual(aValue, bValue)      }    }  }  equal(a, b)    return result}

79. snake_case转换为camelCase

/** * @param {string} str * @return {string} */function snakeToCamel(str) {  const reg = /([^_])_([^_])/g  return str.replaceAll(reg, (_, p1, p2) => `${p1}${p2.toUpperCase()}`)}

camelCase转换为snake_case

/* * @param {string} str * @return {string} */function camelToSnake(str) {  const reg = /\B(\w)([A-Z])\B/g  return str.replaceAll(reg, (_, p1, p2) => `${p1}_${p2.toLowerCase()}`)}

81. 合并已排序的数组

/** * @param {number[][]} arrList * non-descending integer array * @return {number[]}  */function merge(arrList) {  let result = []  let offset = false  const isMerge = () => {    let count = 0    for (let i = 0; i < arrList.length; i += 1) {      if (arrList[i].length > 0) count += 1      if (count >= 2) break    }    return count >= 2 ? true : false  }  offset = isMerge()  while (offset) {    let index = 0    let min = Number.MAX_VALUE    for (let i = 0; i < arrList.length; i += 1) {      if (arrList[i][0] <= min) {        index = i        min = arrList[i][0]      }    }    result.push(...arrList[index].splice(0, 1))    offset = isMerge()  }  for (let i = 0; i < arrList.length; i += 1) {    result = [...result, ...arrList[i]]  }  return result }

85. 实现 `_.get()`

/** * @param {object} source * @param {string | string[]} path * @param {any} [defaultValue] * @return {any} */function get(source, path, defaultValue = undefined) {  if (typeof path === 'string') {    path = path.split('.')  }  const newPath = []  const reg = /^([A-Za-z]+)\[([0-9]+)]$/g  let result = source  for (let i = 0; i < path.length; i += 1) {    if (path[i].includes('[')) {      const arr = reg.exec(path[i])      newPath.push(arr[1])      newPath.push(arr[2])    } else {      newPath.push(path[i])    }  }  for (let i = 0; i < newPath.length; i += 1) {    if (result === undefined || result === null) {      result = defaultValue      break    }    result = result[newPath[i]]  }  console.log(result)  return result ? result : defaultValue}

87. 返回最长的不重复子字符串

/** * @param {string} str * @return {string} */function longestUniqueSubstr(str) {  const hash = {}  let result = ''  let current = ''  let start = 0  let end = 0    while (start <= end && end <= str.length - 1) {    if (hash[str[end]] === undefined) {      hash[str[end]] = end    } else {      start = hash[str[end]] + 1      hash[str[end]] = end      Object.keys(hash).forEach((key) => {        if (hash[key] < start) delete hash[key]      })    }    current = str.slice(start, end + 1)    if (result.length < current.length) {      result = current    }    end += 1  }  return result}

89. 返回DOM tree中”左边“的元素

/** * @param {HTMLElement} root * @param {HTMLElement} target * @return {HTMLElemnt | null} */function nextRightSibling(root, target) {  if (!root) return null  let result = null  const bfs = (nodes) => {    if (nodes.length) {      let childs = []      for (let i = 0; i < nodes.length; i += 1) {        const children = nodes[i].children        childs = [...childs, ...children]      }      for (let i = 0; i < childs.length; i += 1) {        if (childs[i] === target) {          if (i === childs.length - 1) {            result = null            return          } else {            result = childs[i + 1]            return          }        }      }      bfs(childs)    }  }  bfs([root])  return result   }

90. 实现`instanceof`

/** * @param {any} obj * @param {target} target * @return {boolean} */function myInstanceOf(obj, target) {  if (typeof obj !== 'object' || obj === null) {    return false  }  const proto = Object.getPrototypeOf(obj)  if (proto === null) {    return false  }  if (proto === target.prototype) {    return true  } else {    return myInstanceOf(proto, target)  }}

91. 反转二叉树

/** * @param {Node} node * @returns {Node} */function invert(node) {  if (!node) return null  const traverside = (node) => {    if (node) {      const left = node.left      const right = node.right      node.right = left      node.left = right      traverside(left)      traverside(right)    }  }  traverside(node)  return node}

92. Promise节流

/** * @param {() => Promise<any>} func * @param {number} max * @return {Promise} */function throttlePromises(funcs, max){  return new Promise(function (resolve, reject) {    const result = []    const len = funcs.length    let jobs = 0    let count = 0    const handleJobs = () => {      while (jobs < max && funcs.length) {        let promise = funcs.shift()()        let index = len - funcs.length - 1        promise = promise instanceof Promise ? promise : Promise.resolve(promise)        promise.then((res) => {          result[index] = res          count += 1          jobs -= 1          if (count === len) {            resolve(result)          }          handleJobs()        }).catch((err) => {          reject(err)        })        jobs += 1      }    }    handleJobs()  })}

94. 实现`Object.create`

/** * @param {any} proto * @return {object} */function myObjectCreate(proto) {  if (!(proto instanceof Object)) {    throw new Error()  }  const obj = {}  obj.__proto__ = proto  return obj}/** * @param {any} proto * @return {object} */function myObjectCreate(proto) {  if (!(proto instanceof Object)) {    throw new Error()  }  function Constructor () {}  Constructor.prototype = proto  return new Constructor();}// Error// ES6的class语法无奈批改类的Constructor.prototype// https://stackoverflow.com/questions/37680766/how-to-change-classs-prototype-in-es6/** * @param {any} proto * @return {object} */function myObjectCreate(proto) {  if (!(proto instanceof Object)) {    throw new Error()  }  class Constructor {}  Constructor.prototype = proto  return new Constructor();}

95. 实现 String.prototype.trim()

/** * @param {string} str * @return {string} */function trim(str) {  return str.replace(/^\s+|\s+$/g, '')}

97. 压缩字符串

/** * @param {string} str * @return {string} */function compress(str) {  let s = str[0]  let p = str[0]  let n = 1  for (let i = 1; i < str.length; i += 1) {    if (str[i] === p) {      n += 1      if (n > 2) {        let arr = s.split('')        arr.pop()        s = `${arr.join('')}${n}`      } else {        s = `${s}${n}`      }    } else {      p = str[i]      n = 1      s = `${s}${str[i]}`    }  }  return s}

99. 在HTML字符串中抽出所有的`<a/>`

/** * @param {string} str * @return {string[]} */function extract(str) {  const result = []  // (\s[^>]*)?, 如果有[^>]，就必须有空格  // [^>]也包含了空格  const reg = /<a(\s[^>]*)?>.*?<\s*\/\s*a>/g  let controller = true  while (controller) {    const match = reg.exec(str)    if (match) {      result.push(match[0])    } else {      controller = false    }  }  return result}

100. 检测链表中是否有环

/** * @param {Node} head * @return {boolean} */function hasCircle(head) {  let fast = head  let slow = head  let offset = true  let result = false  while (offset && fast && slow) {    fast = fast?.next    slow = slow?.next?.next    if (fast === slow) {      result = true      offset = false    }  }  return result}

102. 验证括号字符串

class Stack {  constructor () {    this.stack = []    Object.defineProperties(this, {      size: {        set () {          throw new Error()        },        get () {          return this.stack.length        }      }    })  }  push (n) {    this.stack.push(n)  }  pop () {    return this.stack.pop()  }  peek () {    return this.stack[this.stack.length - 1]  }}/** * @param {string} str * @return {boolean}  */function validate(str) {  const stack = new Stack()  for (let i = 0; i < str.length; i += 1) {    if (stack.size === 0) {      stack.push(str[i])    } else {      const top = stack.peek()      if (top === '[' && str[i] === ']') {        stack.pop()        continue      } else if (top === '{' && str[i] === '}') {        stack.pop()        continue      } else if (top === '(' && str[i] === ')') {        stack.pop()        continue      } else {        stack.push(str[i])      }    }  }  return stack.size === 0 ? true : false}

103. 实现Math.sqrt()

/** * @param {any} x * @return {number} */function mySqrt(x) {  if (!(typeof x === "number" && !isNaN(x) && x >= 0)) return NaN  if (x === 0) return 0  if (x === 1) return 1  let result = null  const sqrt = (start, end) => {    if (start <= end) {      const midd = Math.floor((end + start) / 2)      if (midd ** 2 < x) {        result = midd        sqrt(midd + 1, end)      } else if (midd ** 2 > x) {        sqrt(start, midd - 1)      } else {        result = midd      }    }  }  sqrt(0, x)  return result}

104. 按层遍历DOM树

/** * @param {HTMLElement | null} root * @return {HTMLElement[]} */// bfsfunction flatten(root) {  if (!root) return []  const result = [root]  const bfs = (nodes) => {    if (nodes.length) {      const children = []      for (let i = 0; i < nodes.length; i += 1) {        const child = nodes[i].children        children.push(...child)      }      result.push(...children)      bfs(children)    }   }  bfs([root])  return result}

105. 找到第一个反复的字符

/** * @param {string} str * @return {string | null} */function firstDuplicate(str) {  let result = null  const hash = {}  for (let i = 0; i < str.length; i += 1) {    const key = str[i]    if (!hash[key]) {      hash[key] = true    } else {      result = key      break    }  }  return result}

106. 找到和为0的两个数

/** * @param {number[]} arr * @return {number[]} */function findTwo(arr) {  const hash = {}  let result = null  for (let i = 0; i < arr.length; i += 1) {    if (!hash[arr[i]]) hash[arr[i]] = [i]    else hash[arr[i]].push(i)  }   for (let i = 0; i < arr.length; i += 1) {    const a = arr[i]    const index = hash[a].shift()    const b = 0 - a    if (hash[b] && hash[b].length > 0) {      result = [index, hash[b][0]]      break    } else {      hash[a].unshift(index)    }  }  return result}

107. 找到最大的差

/** * @param {number[]} arr * @return {number} */function largestDiff(arr) {  if (arr.length === 0) return 0  if (arr.length === 1) return 0  let min = Infinity  let max = -Infinity  for (let i = 0; i < arr.length; i += 1) {    min = Math.min(arr[i], min)    max = Math.max(arr[i], max)  }  return Math.abs(min - max)}

108. 用队列(Queue)实现栈(Stack)

/* you can use this Queue which is bundled together with your codeclass Queue {  enqueue(element) {    // add new element to the queue  }  peek() {     // return the head element  }  dequeue() {     // remove head element from the queue  }  size() {     // return the queue size  }}*/// you need to complete the following Stack, using only Queueclass Stack {  constructor () {    this.queue = new Queue()    this.stack = new Queue()  }  push(element) {    while (this.stack.size()) {      this.queue.enqueue(this.stack.dequeue())    }    this.stack.enqueue(element)    while (this.queue.size()) {      this.stack.enqueue(this.queue.dequeue())    }  }  peek() {     return this.stack.peek()  }  pop() {     return this.stack.dequeue()  }  size() {     return this.stack.size()  }}

109. 实现`Math.pow()`

/** * @param {number} base * @param {number} power - integer * @return {number} */function pow(base, power){  const isNegativeIndex = power < 0  const isNegative = base < 0    const _pow = (base, power) => {    if (power === 0) return 1    if (power === 1) return base    let result = power % 2 === 0 ?      pow(base * base, power / 2)      :      pow(base * base, (power - 1) / 2) * base    return result  }  let result = _pow(Math.abs(base), Math.abs(power))  result = isNegativeIndex ? 1 / result : result  result = isNegative ? result * -1 : result  return result}

116. 实现Object.is()

/** * @param {any} a * @param {any} b * @return {boolean} */function is(a, b) {  if (typeof a === 'number' && typeof b === 'number') {    if (isNaN(a) && isNaN(b)) {      return true    } else if (a === 0 && b === 0) {      return 1/a === 1/b    }  }  return a === b}

119. 创立一个tokenizer

/** * @param {string} str * @return {Generator} */function* tokenize(str) {  let temp = str.replace(/\s/g, '')  let num = ''  for (let i = 0; i < temp.length; i += 1) {    const s = temp[i]    switch (s) {      case '+':      case '-':      case '*':      case '/':      case '(':      case ')':        if (num !== '') {          yield num          num = ''        }        yield s        break      default:        num += s        break    }  }  if (num !== '') {    yield num  }}

122. 实现 memoizeOne()

const compare = (oldKey, newKey) => {  if (Array.isArray(oldKey) && Array.isArray(newKey) && oldKey.length === newKey.length) {    return oldKey.every((key, i) => key === newKey[i])  }  return oldKey === newKey}/** * @param {Function} func * @param {(args: any[], newArgs: any[]) => boolean} [isEqual] * @returns {any} */function memoizeOne(func, isEqual = compare) {  let oldKey = Symbol()  let catchResult = null  let that = null  let isCall = false    return function (...params) {    if (that !== this) {      oldKey = Symbol()      that = this    }     if (isCall && isEqual(oldKey, [...params])) {      return catchResult    }    isCall = true    oldKey = [...params]    const result = func.apply(this, [...params])    catchResult = result    return result  }}

123. 实现 Promise.prototype.finally()

/** * @param {Promise<any>} promise * @param {() => void} onFinally * @returns {Promise<any>} */function myFinally(promise, onFinally) {  return promise.then((res) => {    return Promise.resolve(onFinally()).then(() => {      return res    })  }).catch((err) => {    return Promise.resolve(onFinally()).then(() => {      throw err    })  })}

125. 实现classNames()

function getKeys (obj) {  return [...Object.keys(obj)]}function getType (data) {  const type = Object.prototype.toString.call(data);  return /^\[object\s+([A-Za-z]+)\]$/.exec(type)[1].toLocaleLowerCase()}function trim(str) {  return str.replace(/^\s+|\s+$/g, '')}function isNumberTypeOrStringNumber (data) {  const type = getType(data)  if (type === 'number' || type === 'string') {    return true  }  return false}/** * @param {any[]} args * @returns {string} */function classNames(...args) {  let result = ''  const _classNames = (value) => {    const type = getType(value)    if (type === 'number') {      result += ` ${value}`      return    }    if (type === 'string') {      result += ` ${value}`      return    }    if (type === 'map' || type === 'object') {      const keys = getKeys(value)      for (let i = 0; i < keys.length; i += 1) {        const key = keys[i]        const val = value[key]        if (val) {          if (isNumberTypeOrStringNumber(key)) {            result += ` ${key}`          } else {            _classNames(val)          }        }      }      return    }    if (type === 'set' || type === 'array') {      value.forEach((val) => {        if (val) {          if (isNumberTypeOrStringNumber(val)) {            result += ` ${val}`          } else {            _classNames(val)          }        }      })    }  }  for (let i = 0; i < args.length; i += 1) {    _classNames(args[i])  }  return trim(result)}

130. 创立LazyMan()

// interface Laziness {//   sleep: (time: number) => Laziness//   sleepFirst: (time: number) => Laziness//   eat: (food: string) => Laziness// }function sleep (time) {  return new Promise(function (resolve) {    setTimeout(() => {      resolve()    }, time)  })}/** * @param {string} name * @param {(log: string) => void} logFn * @returns {Laziness} */function LazyMan(name, logFn) {  const queue = [() => {    logFn(`Hi, I'm ${name}.`)  }]  let update = false  const handleQueue = function () {    update = true    if (update) {      Promise.resolve().then(async function () {        update = false        for (let i = 0; i < queue.length; i += 1) {          await queue[i]()        }      })    }  }  const laziness = {    sleep (time) {      queue.push(async () => {        await sleep(time * 1000)        logFn(time > 1 ? `Wake up after ${time} seconds.` : `Wake up after ${time} second.`)      })      if (!update) {        handleQueue()      }      return laziness    },    sleepFirst (time) {      queue.unshift(async () => {        await sleep(time * 1000)        logFn(time > 1 ? `Wake up after ${time} seconds.` : `Wake up after ${time} second.`)      })      if (!update) {        handleQueue()      }      return laziness    },    eat (food) {      queue.push(() => {        logFn(`Eat ${food}.`)      })      if (!update) {        handleQueue()      }      return laziness    }  }  if (!update) {    handleQueue()  }  return laziness}

131. 实现_.chunk()

/**  * @param {any[]} items * @param {number} size * @returns {any[][]} */function chunk(items, size) {  if (size === 0 || items.length === 0) {    return []  }  const result = []  while (items.length) {    result.push(items.splice(0, size))  }    return result}

137. 垂直遍历二叉树

/** * @param {Node} root * @returns {number[]} */function traverse(root) {  let result = []  const hash = {}  const helper = (node, offset, fnode, depth) => {    if (node) {      result.push({        value: node.value,        offset,        fnode,        depth      })      helper(node.left, offset - 1, node, depth + 1)      helper(node.right, offset + 1, node, depth + 1)    }  }    helper(root, 0, null, 0)  result.sort((a,b) => {    if (a.offset !== b.offset) {      return a.offset - b.offset    } else if (a.depth !== b.depth) {      return a.depth - b.depth    } else {      return 0    }  })  // 构建hash, 不便查找父级的索引  result.forEach((item, i) => {    hash[item.value] = {      ...item,      i,    }  })  console.log(hash)  console.log(result)  result.sort((a,b) => {    if (a.offset !== b.offset) {      return a.offset - b.offset    } else if (a.depth !== b.depth) {      return a.depth - b.depth    } else {      // 根节点非凡解决      if (!a.fnode) {        return -1      } else if (!b.fnode) {        return 1      } else {        const aFnodeIndex = hash[a.fnode.value].i        const bFnodeIndex = hash[b.fnode.value].i        return aFnodeIndex - bFnodeIndex      }    }  })    return result.map(item => item.value)}

138. 已排序数组的交加

应用hash的办法：

/** * @param {number[]} arr1 - integers * @param {number[]} arr2 - integers * @returns {number[]} */function intersect(arr1, arr2) {  const hash = {}  const result = []    for (let i = 0; i < arr1.length; i += 1) {    const key = arr1[i]    if (!hash[key]) {      hash[key] = 1    } else {      hash[key] += 1    }  }  for (let i = 0; i < arr2.length; i += 1) {    const key = arr2[i]    if (hash[key]) {      hash[key] -= 1      result.push(key)    }  }  return result}

应用双指针:

/** * @param {number[]} arr1 - integers * @param {number[]} arr2 - integers * @returns {number[]} */function intersect(arr1, arr2) {  const result = []  let pointer1 = 0  let pointer2 = 0    while (pointer1 < arr1.length && pointer2 < arr2.length) {    if (arr1[pointer1] === arr2[pointer2]) {      result.push(arr1[pointer1])      pointer1 += 1      pointer2 += 1    } else if (arr1[pointer1] > arr2[pointer2]) {      pointer2 += 1    } else if (arr1[pointer1] < arr2[pointer2]) {      pointer1 += 1    }  }    return result}

139. 实现_.partial()

function merge(params1, params2) {  for (let i = 0; i < params1.length; i += 1) {    if (params2.length) {      if (typeof params1[i] === 'symbol') {        const first = params2.shift()        params1[i] = first      }    } else {        break    }  }  return [...params1, ...params2]}/** * @param {Function} func * @param {any[]} args * @returns {Function} */function partial(func, ...initArgs) {  return function (...args) {    let params = merge([...initArgs], [...args])    params = params.map((arg) => {      if (typeof arg === 'symbol') {        return undefined      } else {        return arg      }    })    return func.call(this, ...params)  }}partial.placeholder = Symbol()

145. 最多反复呈现的字符

function count(str: string): string | string[] {  const map = {}  let result = []  for (let i = 0; i < str.length; i += 1) {    if (!map[str[i]]) {      map[str[i]] = 1    } else {      map[str[i]] += 1    }  }  const max = Math.max(...Object.values(map))  for (let key in map) {    if (map[key] === max) {      result.push(key)    }  }  return result.length > 1 ? result : result[0]}

146. 实现Array.prototype.reduce()

Array.prototype.myReduce = function (callback, initialValue) {  const argsLength = arguments.length  if (argsLength === 1 && this.length === 0) {    throw new Error()  }    let index = argsLength === 1 ? 1 : 0  let resultValue = argsLength === 1 ? this[0] : initialValue  for (let i = index; i < this.length; i += 1) {    resultValue = callback(resultValue, this[i], i, this)  }  return resultValue}

147. 取石头

function canWinStonePicking(n) {  if (n === 0) return null  if (n === 1) return 'B'  if (n === 2) return 'A'  const firstMove = new Map([    [1, false],    [2, true]  ])  const backhand = new Map([    [1, true],    [2, false]  ])  for (let i = 3; i <= n; i += 1) {    firstMove.set(i, (backhand.get(i-2) || backhand.get(i-1)))    backhand.set(i, (firstMove.get(i-2) && firstMove.get(i-1)))  }  return firstMove.get(n) ? 'A' : backhand.get(n) ? 'B' : null}

148. 创立一个counter对象

function createCounter() {  const obj = { _count: 0 }  return Object.defineProperties(obj, {    count: {      get () {        const r = obj._count        obj._count += 1        return r      }    }  })}

149. interpolation

function t(translation, data = {}) {  return translation.replace(/{{(.*?)}}/g, (_, key) => data[key] || '')}

151. 实现Array.prototype.map()

Array.prototype.myMap = function(callback, thisArg) {  const result = []  const that = thisArg || this  this.forEach(function (item, i) {    result[i] = callback.call(that, item, i, that)  })  return result}

152. 找到最大的前k个元素

// 分治/* * @param {number[]} arr * @param {number} k * @returns {number[]} */function topK(arr, k) {  if (!arr.length) return []  let result = []  let i = 1  const divideAndConquer = function (arr, base, k) {    console.log(arr)    if (arr.length === 1) {      return arr[0]    }    const max = []    const min = []    let maxLen = 0    const referenceValue = arr[0]    for (let i = 1; i < arr.length; i += 1) {      if (arr[i] > referenceValue) {        max.push(arr[i])      } else {        min.push(arr[i])      }    }    max.push(referenceValue)    maxLen = max.length + base    if (maxLen >= k && max.length) {      return divideAndConquer(max, base, k)    } else if (maxLen < k && min.length) {      return divideAndConquer(min, maxLen, k)    }  }  while (i <= k && i <= arr.length) {    result.push(divideAndConquer(arr, 0, i))    i += 1  }  return result}

153. uglify CSS class names

/** * @returns {string} */function getUniqueClassName() {  const letterSet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',]  const letterSetLength = letterSet.length  let prefix = ''  let className = letterSet[getUniqueClassName.index]  // 最初的边界状况  if (getUniqueClassName.prefix.length === letterSetLength) {    return ''  }  for (let i = 0; i < getUniqueClassName.prefix.length; i += 1) {    prefix += letterSet[getUniqueClassName.prefix[i]]  }  getUniqueClassName.index += 1  if (getUniqueClassName.index === letterSetLength) {    getUniqueClassName.index = 0    if (!getUniqueClassName.prefix.length) {      getUniqueClassName.prefix.push(0)    } else {      if (getUniqueClassName.prefix.every(item => item === letterSetLength - 1)) {        getUniqueClassName.prefix = getUniqueClassName.prefix.map(() => 0)        getUniqueClassName.prefix.push(0)      } else {        for (let i = getUniqueClassName.prefix.length - 1; i >= 0; i -= 1) {          if (getUniqueClassName.prefix[i] < letterSetLength - 1) {            getUniqueClassName.prefix[i] += 1            break          }        }      }    }  }  return prefix + className;}getUniqueClassName.reset = function () {  getUniqueClassName.prefix = []  getUniqueClassName.index = 0}// 前缀的长度getUniqueClassName.prefix = []getUniqueClassName.index = 0

154. 简略实现双向绑定Two-way binding

/** * @param {{value: string}} state * @param {HTMLInputElement} element */function model(state, element) {  element.value = state.value;  Object.defineProperty(state, 'value', {    get: () => element.value,    set: (value) => element.value = value,  })}

155. 请实现一个count函数

function count() {  count.count += 1  return count.count}count.reset = function () {  count.count = 0}count.count = 0

156. 请实现`_.set()`

function set(obj, path, value) {  // 字符串门路和数组门路对立变为数组门路  if (typeof path === 'string') {    path = path.split('.')  }  const newPath = []  const reg = /^([A-Za-z]+)\[([0-9]+)]$/g  let current = obj  let laskKey = ''  const isNumberKey = function (key) {    // 是否是数字的key    const isNumberKey = !isNaN(Number(key))    // 是否为有效的数字key，1 无效的，01 有效的    return isNumberKey && (Number(key) + '' === key)   }  for (let i = 0; i < path.length; i += 1) {    if (path[i].includes('[')) {      const arr = reg.exec(path[i])      newPath.push(arr[1])      newPath.push(arr[2])    } else {      newPath.push(path[i])    }  }  laskKey = newPath[newPath.length - 1]  for (let i = 0; i < newPath.length - 1; i += 1) {    const key = newPath[i]    const nextKey = newPath[i + 1]    const v = current[key]    if (v instanceof Object) {      current = v    } else {      if (isNumberKey(nextKey)) {        current[key] = []      } else {        current[key] = {}      }      current = current[key]    }  }  current[laskKey] = value  return obj}

157. semver 比拟

/** * @param {string} v1 * @param {string} v2 * @returns 0 | 1 | -1 */function compare(v1, v2) {  let result = 0  const reg = /([0-9]+)\.([0-9]+)\.([0-9]+)/  const v1Arr = []  const v2Arr = []  for (let i = 1; i <= 3; i += 1) {    v1Arr.push(Number(reg.exec(v1)[i]))    v2Arr.push(Number(reg.exec(v2)[i]))  }  for (let i = 0; i < v1Arr.length; i += 1) {    if (v1Arr[i] > v2Arr[i]) {      result = 1      break    } else if (v1Arr[i] < v2Arr[i]) {      result = -1      break    }  }  return result}

158. 返回DOM tree中”右边“的元素

/** * @param {Element} root * @param {Element} target * @return {Elemnt | null} */function previousLeftSibling(root, target) {  let result = null  const bfs = (nodes) => {    if (nodes.length) {      let childrenArr = []      let index = null      for (let i = 0; i < nodes.length; i += 1) {        const children = [...nodes[i].children]        childrenArr = [...childrenArr, ...children]      }      for (let i = 0; i < childrenArr.length; i += 1) {        if (childrenArr[i] === target) {          index = i - 1          if (index !== -1) {            result = childrenArr[index]          }        }      }      if (index === null) {        bfs(childrenArr)      }    }  }  bfs([root])  return result}

159. 实现promisify()

/** * @param {(...args) => void} func * @returns {(...args) => Promise<any} */function promisify(func) {  return function(...args) {    const that = this    return new Promise(function(resolve, reject) {      func.apply(that, [...args, function (error, data) {        if (error) {          reject(error)        } else {          resolve(data)        }      }])    })  }}

162. 请找到未反复呈现的整数

/** * @param {number[]} arr * @returns number */function findSingle(arr) {  let result = arr[0]  for (let i = 1; i < arr.length; i += 1) {    result = result ^ arr[i]  }  return result}

前言

1. 实现curry

2. 实现反对placeholder的curry()

3. 实现Array.prototype.flat()

4. 手写throttle()

6. 手写debounce()

8. 手写shuffle()随机打乱一个数组（实现一个洗牌算法）

9. 解密音讯

10. 找出第一个不良版本

11. 什么是Composition?实现pipe()

13. 利用栈(Stack)创立队列(Queue)

14. 实现memo()

15. 实现相似jQuery的DOM wrapper

16. 实现一个Event Emitter

17. 实现一个DOM element store

18. 优化一个function

19. 雷同构造的DOM tree下面寻找对应的节点

20. 检测 data type

21. 手写JSON.stringify()

22. 手写JSON.parse()

23. 实现一个sum()办法

24. 用JavaScript手写一个Priority Queue

25. 更新数组的程序

26. 实现Object.assign()

27. 实现completeAssign()

28. 实现clearAllTimeout()

29. 实现async helper - sequence()

30. 实现async helper - parallel()

31. 实现async helper - race()

32. 实现Promise.all()

33. 实现Promise.allSettled()

34. 实现Promise.any()

35. 实现Promise.race()

37. 手写Binary Search (unique)

38. 实现jest.spyOn()

39. 手写range()

40. 手写冒泡排序

41. 手写归并排序

42. 手写插入排序

43. 手写疾速排序

44. 手写抉择排序

45. 在未排序的数组中找到第K大的元素

46. 实现_.once()

47. 反转链表

48. 含有反复元素的数组中返回特定元素的首次呈现的地位

49. 含有反复元素的数组中返回特定元素的最初呈现的地位

50. 含有反复元素的数组中返回特定元素之前的元素

51. 含有反复元素的数组中返回特定元素的之后的元素

53. 实现middleware

蚂蚁金服面试真题: 实现compose

53. 用es5实现extends

55. HTML字符串中高亮关键字

58. 返回DOM tree的高度

59. 实现browser history

60. 实现本人的new

61. 实现Function.prototype.call

手写apply

手写bind

63. 手写_.cloneDeep()

64. Promise reject的时候主动retry

65. 增加千位分隔符

66. 去掉数组中的反复元素

69. 实现_.isEqual()

79. snake_case转换为camelCase

camelCase转换为snake_case

81. 合并已排序的数组

85. 实现 _.get()

87. 返回最长的不重复子字符串

89. 返回DOM tree中”左边“的元素

90. 实现instanceof

91. 反转二叉树

92. Promise节流

94. 实现Object.create

95. 实现 String.prototype.trim()

97. 压缩字符串

99. 在HTML字符串中抽出所有的<a/>

100. 检测链表中是否有环

102. 验证括号字符串

103. 实现Math.sqrt()

104. 按层遍历DOM树

14. 实现`memo()`

29. 实现async helper - `sequence()`

30. 实现async helper - `parallel()`

31. 实现async helper - `race()`

32. 实现`Promise.all()`

33. 实现`Promise.allSettled()`

34. 实现`Promise.any()`

35. 实现`Promise.race()`

38. 实现`jest.spyOn()`

46. 实现`_.once()`

53. 用es5实现`extends`

60. 实现本人的`new`

61. 实现`Function.prototype.call`

63. 手写`_.cloneDeep()`

69. 实现`_.isEqual()`

85. 实现 `_.get()`

90. 实现`instanceof`

94. 实现`Object.create`

99. 在HTML字符串中抽出所有的`<a/>`

109. 实现`Math.pow()`

156. 请实现`_.set()`