2

面试准备记录

 3 years ago
source link: https://yazhen.me/_posts/2020/%E9%9D%A2%E8%AF%95%E5%87%86%E5%A4%87%E8%AE%B0%E5%BD%95/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

面试准备记录

By王亚振

发布于: 2020年09月02日 



Javascript

对象深拷贝

  1. JSON.stringify()

该方法有一些缺陷 比如属性值是 function 函数的会删除属性, 值是 undefined 的也会删除，下面是MDN文档表述

JSON.stringify() 将值转换为相应的JSON格式：

- 转换值如果有 toJSON() 方法，该方法定义什么值将被序列化。
- 非数组对象的属性不能保证以特定的顺序出现在序列化后的字符串中。
- 布尔值、数字、字符串的包装对象在序列化过程中会自动转换成对应的原始值。
- undefined、任意的函数以及 symbol 值，在序列化过程中会被忽略（出现在非数组对象的属性值中时）或者被转换成 null（出现在数组中时）。函数、undefined 被单独转换时，会返回 undefined，如JSON.stringify(function(){}) or JSON.stringify(undefined).
- **对包含循环引用的对象（对象之间相互引用，形成无限循环）执行此方法，会抛出错误**。
- 所有以 symbol 为属性键的属性都会被完全忽略掉，即便 replacer 参数中强制指定包含了它们。
- Date 日期调用了 toJSON() 将其转换为了 string 字符串（同Date.toISOString()），因此会被当做字符串处理。
- NaN 和 Infinity 格式的数值及 null 都会被当做 null。
- 其他类型的对象，包括 Map/Set/WeakMap/WeakSet，仅会序列化可枚举的属性。

对于循环引用该方法会报错

Uncaught TypeError: Converting circular structure to JSON
    --> starting at object with constructor 'Object'
    |     property 'abc' -> object with constructor 'Object'
    --- property 'b' closes the circle
    at JSON.stringify (<anonymous>)
    at js (<anonymous>:2:24)
    at <anonymous>:1:1

一个自然的想法就是消除循环引用. JSON-js 这个扩展包解决了这个问题。使用 JSON.decycle 可以去除循环引用。

参考文章:

  1. 自己实现 deepCopy 方法
function deepCopy(obj) {
	let result = {}
	if (obj === null) return null
	if (typeof obj !== 'object') return obj
	if (obj instanceof Date) return new Date(obj)
	for (let key in obj) {
		if (obj.hasOwnProperty(key)) {
			if (typeof obj[key] === 'object' && obj[key] !== null) {
				result[key] = deepCopy(obj[key])
			} else {
				result[key] = obj[key]
			}

		}
	}
	return result
}

数据结构与算法

冒泡排序比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至 正确的顺序，就好像气泡升至表面一样，冒泡排序因此得名。

Array.prototype.bubleSort = function() {
	for (let i = 0; i < this.length; i ++) {
		for (let j=0; j<this.length -1; j++) {
			if (this[j] > this[j + 1]) {
				let cur = this[j]
				this[j] = this[j+1]
				this[j+1] = cur
			}
		}
	}
}

快速排序也许是最常用的排序算法了。它的复杂度为O(nlog^n)，且它的性能通常比其他的复杂度为O(nlog^n)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开)。

快速排序的基本过程：

  1. 首先，从数组中选择中间一项作为主元
  2. 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指 针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交 换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之 前，而比主元大的值都排在主元之后。这一步叫作划分操作。
  3. 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的 子数组）重复之前的两个步骤，直至数组已完全排序。
Array.prototype.quickSort = function() {
	const partition = (array, left, right) => {
		let pivot = array[Math.floor((right + left) / 2)]
		let i = left
		let j = right
		while(i <= j) {
			while(array[i] < pivot) {
				i++
			}
			while(array[j] > pivot) {
				j--
			}
			if (i <= j) {
				let cur = array[i]
				array[i] = array[j]
				array[j] = cur
				i++
				j--
			}
		}
		return i
	}
	const quick = (array, left, right) => {
		let index
		if (array.length > 1) {
			index = partition(array, left, right)
			if (left < index -1) {
				quick(array, left, index - 1)
			}
			if (index < right) {
				quick(array, index, right)
			}
		}
	}
	quick(this, 0, this.lenght -1)
	return this
}

二分搜索算法的原理和猜数字游戏类似，就是那个有人说"我正想着一个1到100的数字"的游戏。我们每回应一个数字，那个人就会说这个数字是高了、低了还是对了。

这个算法要求被搜索的数据结构已排序，以下是该算法遵循的步骤：

  • 选择数组的中间值
  • 如果选中值是待搜索值，算法执行完毕（值找到了）
  • 如果待搜索值比选中值要小，则返回步骤1并在选中值左边的子数组中寻找
  • 如果待搜索值比选中值要大，则返回步骤1并在选种值右边的子数组中寻找
Array.prototype.binarySearch = function(item) {
	this.quickSort()
	let low = 0
	let mid = null
	let element = null
	let high = this.length -1

	while(low <= high) {
		mid = Math.floor((low + high) / 2)
		element = this[mid]
		if (elemnet < item) {
			low = mid + 1
		}  else if (element > item) {
			high = mid - 1 
		} else {
			return mid
		}
	}
	return -1
}

斐波那契数

斐波那契数列的定义如下：

  • 1和2的斐波那契数是1
  • n(n > 2) 的斐波那契数是 (n-1)的斐波那契数 + n(n-2)的斐波那契数
function fibonacci(num) {
	if (num ===1 || num === 2) return 1
	return fibonacci(num - 1) + fibonacci(num - 2)
}

简易版 Promise

const PENDING = 'PENDING'
const RESOLVED = 'RESOLVED'
const REJECTED = 'REJECTED'

function MyPromise(fn) {
  const that = this
  that.status = PENDING
  that.value = null
  that.resolvedCallbacks = []
  that.rejectedCallbacks = []

  function resolve(value) {
    if (that.status === PENDING) {
      that.value = value
      that.status = RESOLVED
      that.resolvedCallbacks.forEach(f => f(value))
    }
  }

  function reject(value) {
    if (that.status === PENDING) {
      that.status = REJECTED
      that.value = value
      that.rejectedCallbacks.forEach(fn => fn(value))
    }
  }

  try {
    fn(resolve, reject)
  } catch(e) {
    reject(e)
  }
}

MyPromise.prototype.then = function (onFulfilled, onRejected) {
  if (this.status === PENDING) {
    this.resolvedCallbacks.push(onFulfilled)
    this.rejectedCallbacks.push(onRejected)
  }
  if (this.status === RESOLVED) {
    onFulfilled(this.value)
  }
  if (this.status === REJECTED) {
    onRejected(this.value)
  }
   
  return this
}
    const result = new MyPromise((resolve, reject) => {
      setTimeout(() => {
        resolve('1s 返回的值')
      }, 1000)
    })
    console.log('正常')
    result.then(value => {
      console.log('这是：', value)
    }).then(value => {
      console.log('zhe 222:', value)
    })

实现 Promise.all 和 Promise.race

Promise.all

Promise.myAll = function(promises) {
  return new Promise((resolve, reject) => {
    if (!promises.length) {
      return resolve([])
    }
    let result = []
    let count = 0
    for (let i = 0; i < promises.length; i++) {
      const ele = promises[i]
      if (!(ele instanceof Promise)) {
        result[i] = ele
        if (++count === promises.length) {
          resolve(result)
        }
      } else {
        ele.then(value => {
          result[i] = value
          if (++count === promises.length) {
            resolve(result)
          }
        }, e => {
          reject(e)
        })
      }
    }
  })
}

Promise.race

Promise.myRace = function(promises) {
  return new Promise((resolve, reject) => {    
    for (let i = 0; i < promises.length; i++) {
      const ele = promises[i]
      if (!(ele instanceof Promise)) {
        Promise.resolve(ele).then(resolve, reject)
      }
      ele.then(resolve, reject)
    }
  })
}

throttle 方法

function throttle(fn, delay) {
  let start = 0
  return function() {
    let now = Date.now()
    if (now - start > delay) {
      fn()
      start = now
    }
  }
}

debouce 方法

function debouce(fn, delay) {
  let timer = null
  return function() {
    clearTimeout(timer)
    timer = setTimeout(fn, delay)
  }
}

实现一个 flat 方法， 抹平数组

function flatDeep(array, deep = 1) {
  return deep > 0 ? array.reduce((acc, val) => acc.concat(Array.isArray(val) ? flatDeep(val, deep - 1) : val), []) : array.slice()
}

实现 call apply bind

Function.prototype.myCall = function (thisArg, ...args) {
  thisArg = Object(thisArg) || window
  let fn = Symbol()
  thisArg[fn] = this
  let result = thisArg[fn](...args)
  delete thisArg[fn]
  return result
}

apply 

Function.prototype.myApply = function (thisArg, ...args) {
  thisArg = Object(thisArg)
  let fn = Symbol()
  thisArg[fn] = this
  let result = thisArg[fn](args)
  delete thisArg[fn]
  return result
}
Function.prototype.myBind = function(context, ...args) {
  return function(...newArgs) {
    return this.call(context, ...args, ...newArgs)
  }
}

写一个同时允许任务量最大为n 的函数

function limitRunTask(tasks, n) {
  return new Promise((resolve, reject) => {
    let start = 0
    let finished = 0
    let index = 0
    let result = []
    function run() {
      if (finished === tasks.length) {
        resolve(result)
        return
      }
      while (start < n && index < tasks.length) {
        start ++
        let cur = index
        tasks[index ++]().then(val => {
          start --
          finished ++
          result[cur] = val
          run()
        })
      }
    }
    run()
  })
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK