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

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

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'

// 实现 curry
const curry = (fn, ...initParams) => {return (...args) => {return ((params) => {return params.length >= fn.length ? fn(...params) : curry(fn, ...params) 
    })([...initParams, ...args])
  }
}

/**
 * 合并参数（替换占位符）*/
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()

/**
 * @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}
}

/**
 * @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]
    }
  }
}

/**
 * @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()}
  }
}

/**
  * @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
}

/**
 * @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
}

/*
 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
  }
}

/**
 * @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
    }
}


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 实现 Queue
class 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
    }
  }
}


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

  return el
}

// please complete the implementation
class 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)
      })
    }
  }
}

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}
}

优化前的工夫复杂度 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 组成的 array
const 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
    })
  })
}

/**
 * @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
}

/**
 * @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()}

/**
 * @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(',')}}`
  }
}

/**
 * @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
}

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


// complete the implementation
class 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() {}
}

/**
 * @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
}

/**
 * @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
}

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
}

const beforeSetTimeout = window.setTimeout

window.timers = new Set()

// 重写 setTimeout
window.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) => void

type 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) => void

type 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) => void

type 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)
        })
      }
    }
  })
}

/**
 * @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}
}

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

/**
 * @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
}

// 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))
}

/**
 * @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
}

// 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
}

/**
 * @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
}

// 分治

/**
 * @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
  }
}

/** 
 * 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
}

/**
 * @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 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 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]
}

/**
 * @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]
}

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 skipped
middleware.use((req, next) => {console.log(3)
  next(new Error())
  console.log(4)
})


// since error occurs, this is called
middleware.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()}
}

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(() => {//})
//   })
// })

// 实现 compose
function 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
}

// 获取所有关键词的排列组合
/**
 * @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(' ')
};

// 单纯的应用正则


/**
 * @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       
}

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
}

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
}

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 references
const 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
}

/**
 * @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)
  })
}

/**
 * @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}`
  
}

/**
 * @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
}

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

/*
 * @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()}`)
}


/**
 * @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
}

/**
 * @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
}


/**
 * @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)
  }
}

/**
 * @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
}

/**
 * @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();}

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

/**
 * @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
}

/**
 * @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
}

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
}

/**
 * @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
}


/**
 * @param {HTMLElement | null} root
 * @return {HTMLElement[]}
 */
// bfs
function 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
}

/**
 * @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
}


/**
 * @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
}

/**
 * @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)
}

/* you can use this Queue which is bundled together with your code
class 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 Queue
class 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
}

/**
 * @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
}


/**
 * @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}
}

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
  }
}

/**
 * @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})
  })
}

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)
}

// 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
}

/** 
 * @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
}

/**
 * @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)
}

应用 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
}

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()

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]
}

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
}

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
}

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

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

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
}

// 分治
/*
 * @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
}

/**
 * @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


/**
 * @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,
  })
}

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
}

/**
 * @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
}

/**
 * @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
}

/**
 * @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)
        }
      }])
    })
  }
}

/**
 * @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()`