笔试题

实现继承

// call方法
// 缺点无法继承原型方法
 function Parent () {}
 function Child () {
   Parent.call(this)
}

// 原型链继承
// 缺点：所有实例共用同一个原型对象
function Parent () {}
function Child () {}
Child.prototype = new Parent()

// 组合形式
function Parent () {}
function Child () {
  Parent.call(this)
}
Child.prototype. = Object.create(Parent.prototype)
Child.prototype.constructor = Child

// es6继承
class Parent {}
class Child extends Parent {
  constructor() {
      super()
  }
}

防抖

function debounce (fn, delay) {
  let timer = null
  return function () {
    const that = this
    const ars = Array.prototype.slice.call(arguments)
    if (timer) {
        clearTimeout(timer)
    }
    timer = setTimeout(() => {
      fn.apply(that, ars)
    }, delay)
}

节流

function throttle(fn, delay) {
  let timer = null
  return function () {
    const that = this
    if (timer) {
      return 
    }
    const args = Array.prototype.slice.call(arguments)
    timer = setTimerout(() => {
      fn.apply(that, args)
      timer = null
    }, delay)
  }
}

reduce实现map

Array.prototype.map = function (cb) {
  return this.reduce((acc, cur, index, arr) => {
     acc.push(cb.call(null, cur, index, arr))
    return acc
  }, [])
}

二叉树遍历

// 前序遍历
function visit (node) {
  const arr = []
  function _v (n) {
    if (!n) return
    arr.push(n.val)
    _v(n.left)
    _v(n.right)
  }
  _v(node)
  return arr
}
function visit(node) {
  const arr = []
  const stack = [node] 
  while(stack.length) {
    const curNode = stack.pop()
    arr.push(curNode.val)
    if (curNode.right) {
      stack.push(node.right)
    }
    if(curNode.left){
      stack.push(node.left)
    }
  }
  return arr
}

// 中续遍历
function visit (node) {
  let arr = []
  function _v (n) {
    if (!n) return
    _v(n.left)
    arr.push(n.val)
    _v(n.right)
  }
  _v(node)
  return arr
}
// 中序遍历 迭代法
var inorderTraversal = function(root) {
    const stack = []
    const res = []
    while(root || stack.length) {
        while(root) {
            stack.push(root)
            root = root.left
        }
        const curNode = stack.pop()
        res.push(curNode.val)
        root = curNode.right
    }
    return res
};

// 后续遍历
function visit (node) {
  let arr = []
  function _v (n) {
    if (!n) return
    _v(n.left)
    _v(n.right)
    arr.push(n.val)
  }
  _v(node)
  return arr
}
// 迭代法 后序遍历
var postorderTraversal = function (root) {
    const stack = [root];
    const res = [];

    while (stack.length > 0) {
        const node = stack.pop();
        if (node) {
            stack.push(node.left, node.right);
            res.unshift(node.val);
        }
    }
    return res;
};
// 层序遍历
function solution (root) {
  const res = []
  if (!root) {
    return res
  }
  const queue = []
  queue.push(root)
  while (queue.length !== 0) {
    const curQueueLength = queue.length
    const curArr = []
    for (let i = 0; i < curQueueLength; i++) {
      const node = queue.shift()
      curArr.push(node.val)
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
    res.push(curArr)
  }
  return res
}

数组去重

function unique (arr) {
  if (Array.isArray(arr)) {
    return Array.from(new Set(arr))
  }
}
function unique (arr) {
  let cache = {}
  let uniqueArr = []
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] in cache) {
      continue
    } else {
      cache[arr[i]] = true
      uniqueArr.push(arr[i])
    }
  }
  return uniqueArr
}

斐波那契数列

function Fibonacci(j)
{
  // n = (n-1)+(n-2)
  const cache = {
    0: 0,
    1: 1
  }
  function _fibonacci (n) {
    if (cache[n] !== undefined) {
      return cache[n]
    }
    cache[n] = _fibonacci(n-1) + _fibonacci(n-2)
    return cache[n]
  }
  
  return _fibonacci(j)

}

function fbnc (n) {
  let cur = new Array(n)
  cur[0] = 0
  cur[1] = 1
  for (let i = 2; i < n; i++) {
    cur[i] = cur[i - 1] + cur[i - 2]
  }
  return cur
}

调度器

//JS实现一个带并发限制的异步调度器Scheduler，保证同时运行的任务最多有两个。完善代码中Scheduler类，使得以下程序能正确输出
class Scheduler {
  constructor() {
    this.tasks = {}
    this.queue = []
    this.uid = 0
  }
  get taskLength() {
    return Object.keys(this.tasks).length
  }

  add(promiseCreator) {
    return new Promise((resolve) => {
      this.queue.push({
        id: this.uid++,
        isCreated: false,
        promiseCreator,
        resolve
      })
      this.pushTasks()
    })
  }

  pushTasks () {
    if (this.taskLength < 2 && this.queue.length > 0) {
      const cur = this.queue.shift()
      this.tasks[cur.id] = cur
    }
    this.startTasks()
  }

  startTasks () {
    for(let id in this.tasks) {
      const task = this.tasks[id]
      if (task.isCreated) {
        continue
      }
      task.isCreated = true
      task.promiseCreator().then(() => {
        task.resolve()
        delete this.tasks[id]
        this.pushTasks()
      })
    }
  }

  // ...
}

const timeout = (time) => new Promise(resolve => {
  setTimeout(resolve, time)
})

const scheduler = new Scheduler()
const addTask = (time, order) => {
  scheduler.add(() => timeout(time)).then(() => console.log(order))
}
addTask(1000, '1')
addTask(500, '2')
addTask(300, '3')
addTask(400, '4')
// output: 2 3 1 4

// 一开始，1、2两个任务进入队列
// 500ms时，2完成，输出2，任务3进队
// 800ms时，3完成，输出3，任务4进队
// 1000ms时，1完成，输出1
// 1200ms时，4完成，输出4

数组快排

// 冒泡
var sortArray = function(arr) {

    const max = arr.length
    for(let i = 0; i < max - 1; i++) {
        for (let j = 0; j < max - 1 -i; j++) {
            if (arr[j] > arr[j+1]) {
                const temp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
        }
    }
    return arr
    
};
// 快排
var quickSort = function(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

洗牌算法 （打乱数组）

function randArr (arr) {
  const n = arr.length
  const randOne = (min, max) => Math.floor(Math.random() * (max - min + 1) + min)
  for(let i = 0; i < n; i++) {
    const rand = randOne(i, n - 1)
    const temp = arr[i]
    arr[i] = arr[rand]
    arr[rand] = temp
  }
  return arr
}

二分查找

var search = function(nums, target) {
    let l = 0;
    let r = nums.length - 1
    while(l <= r) {
        const m = Math.floor((l + r) / 2)
        if(nums[m] == target) {
            return m
        } else if( target < nums[m]) {
            r = m - 1
        } else {
            l = m + 1
        }
    }
    return -1
};

翻转链表

function ReverseList(pHead)
{
  let pre = null
  while(pHead) {
    const next = pHead.next
    pHead.next = pre
    pre = pHead
    pHead = next
  }
  return pre
}

sleep

function sleep(delay){
  return new Promise((resolve) => {
    setTimeout(resolve, delay)
  })
}

Emitter

class Emitter {
  constructor() {
    this.listeners = {}
  }
  addEventListener (name, fn) {
    this.on(name, fn)
  }
  on(name, fn) {
    if (name in this.listeners) {
      this.listeners[name].push(fn)
    } else {
      this.listeners[name] = [fn]
    }
  }
  emit(name, ...args) {
    const events = this.listeners[name]
    for(let i = 0; i < events.length; i++) {
      events[i](args)
    }
  }
  removeListener(name, fn) {
    const events = this.listeners[name] || []
    const i = events.indexOf(fn)
    if (~i) {
      events.splice(i, 1)
    }
  }
  once(name, listener) {
    const self = this
    const fn = function () {
      const args = Array.prototype.slice.call(arguments)
      listener.apply(null, args)
      self.removeListener(name, fn)
    }
    this.on(name, fn)
  }
}

实现两个大数相加 IEEE754

function add(a ,b){
   //取两个数字的最大长度
   let maxLength = Math.max(a.length, b.length);
   //用0去补齐长度
   a = a.padStart(maxLength , 0);//"0009007199254740991"
   b = b.padStart(maxLength , 0);//"1234567899999999999"
   //定义加法过程中需要用到的变量
   let t = 0;
   let f = 0;   //"进位"
   let sum = "";
   for(let i=maxLength-1 ; i>=0 ; i--){
      t = parseInt(a[i]) + parseInt(b[i]) + f;
      f = Math.floor(t/10);
      sum = t%10 + sum;
   }
   if(f == 1){
      sum = "1" + sum;
   }
   return sum;
}

深拷贝

function deepClone(raw) {
  const type = Object.prototype.toString.call(raw)
  if (type == '[object Number]' ||
    type == '[object String]' ||
    type == '[object Null]' ||
    type == '[object Undefined]'
  ) {
    return raw
  }
  let obj
  if(Array.isArray(raw)) {
    obj = []
    for(let i = 0; i < raw.length; i++) {
      obj[i] = deepClone(raw[i])
    }
    return obj
  } else {
    obj = {}
    Object.keys(raw).forEach(key => {
      obj[key] = deepClone(raw[key])
    })
    return obj
  }
}

回文字符串

function judge(str) {
  const mid = str.length % 2 ? (str.length + 1) / 2 : str.length / 2
  let start = 0;
  let end = str.length - 1
  let value = true
  for (let i = 0; i <= mid; i++) {
    if (str[start] == str[end]) {
      continue
    } else {
      value = false
    }
  }
  return value
}

手写bind

function myBind (asThis) {
  const fn = this
  const slice = Array.prototype.slice
  const args = slice.call(arguments, 1)
  return function () {
    const args2 = slice.call(arguments)
    return fn.apply(asThis, args.concat(args2))
  }
}

手写promise.all

function promiseAll (arr) {
  return new Promise((resolve, reject) => {
    const list = []
    if (arr.length < 1) {
      resolve([])
      return
    }
    for (let i = 0; i < arr.length; i++) {
      const item = arr[i]
      Promise.resolve(item).then(val => {
        list[i] = val
        if (i == arr.length) {
          resolve(list)
        }
      }).catch(e => {
        reject(e)
      })
    }
  })
}