1、setTimeout模拟实现setInterval

题目：使用setInterval 用来实现循环定时调用 可能会存在一定的问题 能用 setTimeout 解决吗?

function mySetInterval(fn, time) {
	let timer = null
	function interval() {
    fn()
		timer = setTimeout(() => {
      interval()
    }, time)
	}
  interval()
  return {
    clear: () => {
      clearTimeout(timer)
    }
  }
}

扩展：使用 setInterval 模拟实现 setTimeout 吗？

function mySetTimeout(fn, time) {
	let timer = setInterval(() => {
    fn()
    clearInterval(time)
  }, time)
}

拓展思考：setinterval 的缺陷是什么？

• 1、即使调用的代码报错了，setInterval仍然会继续调用
• 2、无视网络延迟，在使用ajax轮询服务器数据时，它会去一遍又一遍的发送请求，如果网络不好，会导致请求堆积。
• setInterval不定时。如果它调用的代码执行的时间小于定时的时间，它会跳过调用，这就导致无法按照你需要的执行次数或无法得到你想要的结果

2、 发布订阅模式

题目： 实现一个发布订阅模式拥有 on emit once off 方法

class EventEmitter {
  constructor() {
    this.events = {}
  }
  on(type, cb) {
    if (this.events[type]) {
      this.events[type].push(cb)
    } else {
      this.events[type] = [cb]
    }
  }
  off(type, cb) {
    this.events[type] = this.events[type].filter(x => x !== cb)
  }
  once(type, cb) {
    function fn() {
      cb()
      this.off(type, fn)
    }
    this.on(type, fn)
  }
  emit(type, ...rest) {
    this.events[type]?.forEach(x => {
    	x.apply(this, rest)
  	})
  }
}

3、 数组扁平化

题目：实现一个方法使多维数组变成一维数组

// 递归
function flatter(arr) {
  if (!arr.length) return
  return arr.reduce((prev, curr) => Array.isArray(curr) ? [...prev, ...flatter(curr)] : [...prev, curr], [])
}

// 迭代
function flatter(arr) {
  if (!arr.length) return
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr)
  }
  return arr
}

4、寄生组合继承

function Parent(name) {
  this.name = name
  this.say = () => {
    console.log('say')
  }
}
Parent.prototype.play = () => {
  console.log('basketball')
}
function Child(name) {
  Parent.call(this)
  this.name = name
}

Child.prototype = Object.create(Parent.prototype)
Child.prototype.constructor = Child

5、 实现有并行限制的 Promise 调度器

题目: JS 实现一个带并发限制的异步调度器 Scheduler，保证同时运行的任务最多有两个

class Scheduler {
  constructor(limit) {
    this.queue = []
    this.maxCount = limit
    this.runCount = 0
  }
  add(promise) {
    this.queue.push(promise)
  }
  taskStart() {
    for (let i = 0; i< this.maxCount; i++) {
      this.request()
    }
  }
  request() {
    if (!this.queue || !this.queue.length || this.runCount >= this.maxCount) {
      return
    }
    this.runCount++
    this.queue.shift()().then(() => {
			this.runCount--
      this.request()
    })
  }
}

6、new操作符

function objectFactory() {
	const obj = {}
	const constructor = [].shift.call(arguments)
	obj.__proto__ = constructor.prototype
	const res = constructor.apply(obj, arguments)
	return typeof res === 'object' ? res : obj
}

7、call、apply、bind

Function.prototype.myCall = function (context, ...args) {
  if (!context || content === null) {
    context = window
  }
  // 创造唯一的key值  作为构造的context内部方法名
  let fn = Symbol()
  context[fn] = this // 指向调用myCall的那个函数
  return context[fn](...args)
} 

Function.prototype.myApply = function (context, args) {
  if (!context || context === null) {
    context = windw
  }
  let fn = Symbol()
  context[fn] = this
  return context[fn](...args)
}

Function.prototype.myBind = function (context, args) {
  if (!context || context === null) {
    context = window
  }
  let fn = Symbol()
  context[fn] = this
  let _this = this
  const result = function (...innerArgs) {
    if (this instanceof _this) {
      this[fn] = _this
      this[fn](...[args, ...innerArgs])
    } else {
      context[fn](...[...args, ...innerArgs])
    }
  }
  result.prototype = Object.create(this.prototype)
  return result
}

8、深拷贝

function isObject(val) {
  return typeof val === 'obj' && val !== null
}

function deepClone(obj, hash = new weakMap()) {
  if (!isObject(obj)) return obj
  if (hash.has(obj)) {
    return hash.get(obj)
  }
  let target = Array.isArray(obj) ? [] : {}
  hash.set(obj, target)
  Reflect.ownKeys(obj).forEach(item => {
    if (isObject(obj[item])) {
      target[item] = deepClone(obj[item], hash)
    } else {
      target[item] = obj[item]
    }
  })
  return target
}

9、instanceof

function myInstanceof(left, right) {
  while (true) {
    if (left === null) {
      return false
    }
    if (left.__proto__ === right.prototype) {
      return true
    }
    left = left.__proto__
  }
}

10、柯里化

function currying(fn, ...args) {
  const length = fn.length
  let allArgs = [...args]
  const res = (...newArgs) => {
    allArgs = [...allArgs, ...newArgs]
    if (allArgs.length === length) {
      return fn(...allArgs)
    } else {
      return res
    }
  }
  return res
}

11、冒泡排序(时间复杂度n^2)

function bubbleSort(arr) {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1; j++) {
      if (arr[j] > arr[j+1]) {
        let flag = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = flag
      }
    }
  }
}

12、选择排序

function selectSort(arr) {
  const len = arr.length
  let minIndex
  for (let i = 0; i < len - 1; i++) {
    for (let j = i; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }
  return arr
}

13、插入排序 **

function insertSort(arr) {
	for (let i = 1; i < arr.length; i++) {
		let j = i
		let target = arr[j]
		while(j > 0 && arr[j - 1] > target) {
			arr[j] = arr[j - 1]
			j--
		}
		arr[j] = target
	}
	return arr
}

14、快速排序(nlogn~ n^2 )

function quickSort(arr) {
  if (arr.length < 2) {
    return arr
  }
  const curr = arr[arr.length - 1]
  const left = arr.filter((item, index) => item < curr && index !== arr.length - 1)
  const right = arr.filter(item => item > curr)
  return [...quickSort(left), curr, ...quickSort(right)]
}

15、归并排序( nlog(n)) **

function merge(left, right) {
  let res = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      res.push(left[i]);
      i++;
    } else {
      res.push(right[j]);
      j++;
    }
  }
  if (i < left.length) {
    res.push(...left.slice(i));
  } else {
    res.push(...right.slice(j));
  }
  return res;
}

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.floor(arr.length / 2);

  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

16、二分查找（log2(n)）

题目:如何确定一个数在一个有序数组中的位置

function search(arr, target, start, end) {
  let targetIndex = -1
  let mid = Math.floor((start + end) / 2)
  if (arr[mid] === target) {
    targetIndex = mid
    return targetIndex
  }
  if (start >= end) {
    return targetIndex
  }
  
  if (arr[mid] < target) {
    return search(arr, target, mid + 1, end)
  } else {
    return search(arr, target, start, mid -1)
  }
}

17、防抖节流

// 防抖 非立即执行
function debounce(fn, wait) {
  let timer = null
  return function () {
    timer && clearTimeout(timer)
    timer = setTimeout(() => {
      fn.apply(this, arguments)
    }, wait)
  }
}

// 防抖 立即执行
function debounce(fn, wait) {
  let timer = null
  return function() {
    let flag = !timer
    timer && clearTimeout(timer)
    timer = setTimeout(() => {
      timer = null
    }, wait)
    if (flag) {
      fn.apply(this, arguments)
    }
  }
}

// 节流 时间戳
function throttle(fn, wait) {
  let prev = 0
  return function() {
    let now = Date.now()
    if (now - prev > wait) {
      fn.apply(this, arguments)
      prev = now
    }
  }
}

// 节流 定时器
function throttle(fn, wait) {
  let timer = null
  return function() {
    if (!timer) {
      setTimeout(() => {
      	fn.apply(this, arguments)
        timer = null
      }, wait)
    }
  }
}

18、LRU（最近最少使用）算法

class LRUCache {
  constructor(capacity) {
    this.secretKey = new Map()
    this.capacity = capacity
  }
  get(key) {
    if (this.secretKey.has(key)) {
      let tempValue = this.secretkey.get(key)
      this.secretKey.delete(key)
      this.secretKey.set(key, tempValue)
      return tempValue
    } else {
      return -1
    }
  }
  set(key, value) {
    if (this.secretKey.has(key)) {
      this.secretKey.delete(key)
      this.secretKey.set(key, value)
    } else if (this.capacity > this.secretKey.size) {
      this.secretKey.set(key, value)
    } else {
      this.secretKey.delete(this.secretKey.keys().next.value)
      this.secretKey.set(key, value)
    }
  }
}

19、Promise

class Promise {
    constructor(executor) {
        this.state = 'pending'
        this.value = 'undefined'
        this.reason = 'undefined'
        this.onResolvedCallbacks = []
        this.onRejectedCallbacks = []
        
        let resolve = value => {
            this.state = 'fulfilled'
            this.value = value
            this.onResolvedCallbacks.forEach(fn => fn())
        }
        
        let reject = reason => {
            this.state = 'rejected'
            this.reason = reason
            this.onRejectedCallbacks.forEach(fn => fn())
        }
        
        try {
           executor(resolve, reject) 
        } catch(error) {
            reject(error)
        }
    }
    then(onFulfilled, onRejected) {
    onFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value => value
    onRejected = typeof onRejected === 'function' ? onRejected : err => { throw err }
        let promise2 = new Promise((resolve, reject) => {
            if (this.state === 'fulfilled') {
                setTimeout(() => {
                    try {
                        let x = onFulfilled(this.value)
                        resolve(promise2, x, resolve, reject)
                    } catch(e) {
                        reject(e)
                    }
                }, 0)
            }
            
            if (this.state === 'rejected') {
                setTimeout(() => {
                    try {
                        let x = onRejected(this.reason)
                        resolvePromise(promise2, x, resolve, reject)
                    } catch(e) {
                        reject(e)
                    }
                }, 0)
            }
            
            if (this.state === 'pending') {
             this.onResolvedCallbacks.push(() => {
                 setTimeout(() => {
                    try {
                        let x = onFulfilled(this.value)
                        resolvePromise(promise2, x, resolve, reject)
                    } catch(e) {
                        reject(e)
                    }
                 }, 0)
             })
             
             this.onRejectedCallbacks.push(() => {
                 setTimeout(() => {
                     try {
                        let x = onRejected(this.reason)
                        resolvePromise(promise2,x, resolve, reject)
                     } catch(e) {
                         reject(e)
                     }
                 }, 0)
             })
            }
        })
        return promise2
    }
}



function resolvePromise(promise2, x, resolve, reject) {
    if (x === promise2) {
        return new TypeError('chaining cycle detected for promise')
    }
    let called
    if (x != null && (typeof x === 'object' || typeof x === 'function')) {
        try {
            let then = x.then
            if (typeof then === 'function') {
                then.call(x, y => {
                    if (called) return 
                    called = true
                    resolvePromise(promise2, y, resolve, reject)
                }, err => {
                    if (called) return 
                    called = true
                    reject(err)
                })
            }
        } catch(error) {
            if (called) return
            called = true
            reject(error)
        }
    } else {
        resolve(x)
    }
}

// resolve
Promise.resolve = function(value) {
    if (value && typeof value === 'object' && (value instanceof Promise)) {
        return value
    }
    return new Promise(resolve => {
        resolve(value)
    })
}

// reject
Promise.reject = function(value) {
    return new Promise((_, reject) => {
        reject(value)
    })
}

// all
Promise.all = function(promises) {
    return new Promise((resolve, reject) => {
        let result = []
        let count = 0
        let len = promises.length
        if (len === 0) {
            resolve([])
        }
        promises.forEach((item, index) => {
            Promise.resolve(item).then(res => {
                count += 1
                result[index] = res
                if (count === len) {
                    resolve(result)
                }
            }).catch(err => {
                reject(err)
            })
        })
    })
}

// allSettled
Promise.allSettled = function(promises) {
   return new Promise((resolve, reject) => {
        let result = []
        let count = 0
        let len = promises.length
        if (len === 0) {
            resolve([])
        }
        promises.forEach((item, index) => {
            Promise.resolve(item).then(res => {
                count += 1
                result[index] = {
                    status: 'fulfiled',
                    value: res
                }
                if (len === count) {
                    resolve(result)
                }
            }).catch(err => {
                count += 1
                result[index] = {
                    status: 'rejected',
                    reason: err
                }
                if (len === count) {
                    resolve(result)
                }
            })
        })
   })
}

// race
Promise.race = function(promises) {
    return new Promise((resolve, reject) => {
        promises.forEach(item => {
            Promise.resolve(item).then(resolve).catch(reject)
        })
    })
}

20、实现 DOM2JSON 一个函数，可以把一个 DOM 节点输出 JSON 的格式

function dom2Json(domtree) {
	let obj = {}
	obj.name = domtree.tagName
	obj.children = []
	domtree.childNodes.forEach(child => obj.children.push(dom2Json(child)))
	return obj
}

21、类数组转化为数组的方法

const arrayLike =document.querySelectorAll('div')

// 扩展运算符
[...arrayLike]
// Array.from
Array.from(arrayLike)
// Array.prototype.slice
Array.prototype.slice.call(arrayLike)
// Array.apply
Array.apply(null, arrayLike)
// Array.prototype.concat
Array.prototype.concat.apply([], arrayLike)

22、Object.is 实现

Object.is不会转换被比较的两个值的类型，这点和===更为相似，他们之间也存在一些区别。

1. NaN在===中是不相等的，而在Object.is中是相等的
2. 2. +0和-0在===中是相等的，而在Object.is中是不相等的

Object.is = function(x, y) {
	if (x === y) {
    return x !== 0 || 1 / x === 1 / y
  }
  
  return x!== x && y!==y
}

23、 AJAX

const getJson = (url) => {
	return new Promise((resolve, reject) => {
    const xhr = new XMLHttpRequest()
    xhr.open('GET', url, false)
    xhr.setRequestHeader("Content-Type", "application/json")
    xhr.onreadystatechange = function() {
      if (xhr.readyState !== 4) return
      if (xhr.status === 200 || xhr.status === 304) {
        resolve(xhr.responseText)
      } else {
        reject(new Error(xhr.responseText))
      }
    }
    xhr.send()
  })
}

24、分片思想解决大数据量渲染问题

let ul = document.getElementById("ul")
let total = 1000000 // 插入100万条数据
let once = 20 // 一次插入20条
let page = total / once // 总页数
let index = 0 // 索引
// 循环加载数据
function loop(curTotal, curIndex) {
  if (curTotal <= 0) {
    return false
  }
  // 每页多少条数据
  const pageCount = Math.min(curTotal, once)
  window.requestAnimationFrame(function () {
    for (let i = 0; i < pageCount; i++) {
      let li = doucument.createElement('li')
      li.innerText = `第${curIndex + i}项 `
      ul.appendChild(li)
    }
    loop(curTotal - pageCount, curIndex + pageCount)
  })
}
loop(total, index)

25、将虚拟 Dom 转化为真实 Dom

{
  tag: 'DIV',
  attrs:{
  id:'app'
  },
  children: [
    {
      tag: 'SPAN',
      children: [
        { tag: 'A', children: [] }
      ]
    },
    {
      tag: 'SPAN',
      children: [
        { tag: 'A', children: [] },
        { tag: 'A', children: [] }
      ]
    }
  ]
}
把上诉虚拟Dom转化成下方真实Dom
<div id="app">
  <span>
    <a></a>
  </span>
  <span>
    <a></a>
    <a></a>
  </span>
</div>

function _render(vnode) {
  if (typeof vnode === 'number') {
    vnode = String(vnode)
  }
  if (typeof vnode === 'string') {
    return document.createTextNode(vnode)
  }
  const dom = ducument.createElement(vnode.tag)
  if (vnode.attrs) {
    Object.keys(vnode.attrs).forEach(key => {
      const value = vnode.attrs[key]
      dom.setAttribute(key, value)
    })
  }
  vnode.children.forEach(child => dom.appendChild(_render(child)))
  return dom
}

26、实现模板字符串解析功能

let template = '我是{{name}}，年龄{{age}}，性别{{sex}}';
let data = {
  name: '姓名',
  age: 18
}
render(template, data); // 我是姓名，年龄18，性别undefined

function render(template, data) {
  const computed = template.replace(/\{\{(\w+)\}\}/g, function(match, key) {
    return data[key]
  })
  return computed
}

27、列表转成树形结构

function listToTree(data) {
  let map = {}
  let treeData = []
  data.forEach(item => {
    if (!item.children) {
      item.children = []
    }
    map[item.id] = item
  })
  data.forEach(item => {
    let parent = map[item.pid]
    if (parent) {
      parent.children.push(item)
    } else {
      treeData.push(item)
    }
  })
  return treeData
}

28、树形结构转成列表

function treeToList(data) {
  let result = []
  data.forEach(item => {
    result.push(item)
    if (item.children && item.children.length > 0) {
      result.push(...treeToList(item.children))
    }
    Reflect.deleteProperty(item, 'children')
  })
  return result
}