Git Product home page Git Product logo

interview's People

Contributors

d-kylin avatar

Watchers

avatar

interview's Issues

链式调用

题目要求

实现一个 sum 函数，能满足以下情况调用时返回正确的结果。
sum(1,2,3,4).sumOf() //10
sum(1)(2)(3)(4).sumOf() //10
sum(1)(2,3)(4).sumOf() //10
sum()(2)()()()()().sumOf() //2

按照惯例，先上题目分析。链式调用的情况，可以通过返回对象本身，这样只要是对象的方法都能一直调用返回值，最容易想到的就是 JQuery 的链式调用。

var rootjQuery = null,
    jQuery = function( selector, context ) {
    return new jQuery.fn.init( selector, context, rootjQuery );
    };

jQuery.fn = jQuery.prototype = {
    init: function( selector, context, rootjQuery ) {
    console.log("jQuery.init");
    return this;
    },

    toArray: function() {
    console.log("jquery.toArray");
    return this;
    }
};

jQuery.fn.init.prototype = jQuery.fn;

jQuery().init().init().toArray().init().toArray();
//控制台打印的结果如下：
//jQuery.init
//jQuery.init
//jQuery.init
//jquery.toArray
//jQuery.init
//jquery.toArray

另一种就是通过返回函数。

下面直接上结果：

function sum(...args){
	let arr = args

	let fn = function(...args) {
		arr.push(...args)
		return fn
	}
	fn.sumOf = function() {
		return arr.reduce((re, cu) => {
			return  re + cu
		})
	}

	return fn
}

查找变种题

1、一个长度为 N 的数组，元素为 1 时为正常值，元素为 2 时为异常值，并且有个约束，从第一个出现 2 以后的所有元素都只能是 2，如何用最少的查找次数找到第一个出现的 2 索引。
测试用例：
let a = [1,1,1,1,1,2,2]；
let b = [2,2,2,2,2,2,2]；
let c = [1,1,1,1,1,1,2]；

排序算法的一些实现和细节

冒泡排序

运作方式

  • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤，除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

复杂度

最坏时间复杂度 O(n2)

最优时间复杂度 O(n)

平均时间复杂度 O(n2)

最坏空间复杂度 总共 O(n)，需要辅助空间 O(1)

实现示例

  function bubble(arr) {
    let i, j, temp;
    for (i = 0; i < arr.length - 1; i++) {
      for (j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j]
          arr[j] = arr[j + 1]
          arr[j + 1] = temp
        }
      }

      return arr
    }
  }

插入排序

运作方式

  • 从第一个元素开始，该元素可以认为已经被排序
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  • 将新元素插入到该位置后
  • 重复步骤2~5

复杂度

最坏时间复杂度 O(n2)

最优时间复杂度 O(n)

平均时间复杂度 O(n2)

最坏空间复杂度 总共 O(n)，需要辅助空间 O(1)

实现示例

  function insertion(arr) {
    let i, j
    for (i = 1; i < arr.length; i++) {
      for (j = 0; j < i; j++) {
        if (arr[j] > arr[i]) {
          arr.splice(j, 0, arr[i])
          arr.splice(i + 1, 1)
          break
        }
      }
    }

    return arr
  }

桶排序

运作方式

  • 设置一个定量的数组当作空桶子。
  • 寻访序列，并且把项目一个一个放到对应的桶子去。
  • 对每个不是空的桶子进行排序。
  • 从不是空的桶子里把项目再放回原来的序列中。

复杂度

最坏时间复杂度 O(n2)

最优时间复杂度 O(n)

平均时间复杂度 O(n + k)

最坏空间复杂度 总共 O(n + k)

示例代码

  function bucketSort(arr, num) {
    function swap(arr, i, j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
    }

    const max = Math.max(...arr)
    const min = Math.min(...arr)
    const buckets = []
    const bucketsSize = Math.floor((max - min) / num) + 1

    for (let i = 0; i < arr.length; i++) {
      let index = ~~(arr[i] / bucketsSize)
      !buckets[index] && (buckets[index] = [])
      buckets[index].push(arr[i])
      let l = buckets[index].length
      while(l > 0) {
        buckets[index][l] < buckets[index][l - 1] && swap(buckets[index], l, l - 1)
        l--
      }
    }
    let wrapBuckets = []
    for (let i = 0; i < buckets.length; i++) {
      buckets[i] && (wrapBuckets = wrapBuckets.concat(buckets[i]))
    }

    return wrapBuckets
  }

计数排序

运作方式

  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
  • 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
  • 反向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去1

复杂度

最坏时间复杂度 O(n + k)

最优时间复杂度 O(n + k)

平均时间复杂度 O(n + k)

最坏空间复杂度 O(n + k)

示例代码

  function countingSort(arr) {
    let i, j
    let C = []
    let result = []
    for (i = 0; i < arr.length; i++) {
      C[arr[i]] >= 1 ? C[arr[i]]++ : (C[arr[i]] = 1)
    }

    for (j = 0; j < C.length; j++) {
      if (C[j]) {
        while (C[j] > 0) {
          result.push(j)
          C[j]--
        }
      }
    }

    return result
  }

归并排序

复杂度

最坏时间复杂度 O(nlogn)

最优时间复杂度 O(nlogn)

平均时间复杂度 O(nlogn)

最坏空间复杂度 O(n)

递归法

  • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
  • 设定两个指针，最初位置分别为两个已经排序序列的起始位置
  • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
  • 重复步骤3直到某一指针到达序列尾
  • 将另一序列剩下的所有元素直接复制到合并序列尾

示例代码

  function merge(left, right) {
    let result = []
    while (left.length > 0 && right.length > 0) {
      if (left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
    return result.concat(left, right)
  }

  function mergeSort(arr) {
    if (arr.length <= 1) {
      return arr
    }
    let middle = Math.floor(arr.length / 2)
    let left = arr.slice(0, middle)
    let right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right))
  }

迭代法

  • 将序列每相邻两个数字进行归并操作，形成 ceil(n/2) 个序列，排序后每个序列包含两/一个元素
  • 若此时序列数不是1个则将上述序列再次归并，形成 ceil(n/4) 个序列，每个序列包含四/三个元素
  • 重复步骤2，直到所有元素排序完毕，即序列数为1

示例代码

  function merge(left, right) {
    let result = []
    while (left.length > 0 && right.length > 0) {
      if (left[0] < right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
    return result.concat(left, right)
  }

  function mergeSort(arr) {
    let result = []
  }

防抖与节流

防抖与节流

防抖与节流是一种常用的高频触发优化方式，可用于对页面中一些高频触发的操作进行性能优化。

  • 防抖（debounce）：将多刺高频优化为只在最后一次执行，常见的使用场景：需要对用户输入进行检索或者校验，只需要在输入完成后执行一次检索或者校验即可；提交表单等。
function debounce(fn, wait = 0, immediate = false) {
	let timer = null

	return function() {
		let args = arguments
		let context = this

		if (immediate && !timer) {
			fn.apply(conext, args)
		}

		if (timer) clearTimeout(timer)
		timer = setTimeout(() => {
			fn.apply(context, args)
		}, wait)
	}
}
  • 节流（throttle）：每隔一段时间吼执行一次，常见使用场景：滚动条事件、resize时间。
function throttle(fn, wait, immediate) {
	let timer = null
	let callNow = immediate

	return function() {
		let args = arguments
		let context = this

		if (callNow) {
			fn.apply(context, args)
			callNow = false
		}

		if (!timer) {
			timer = setTimeout(() => {
				fn.apply(context, args)
				timer = null
			}, wait)
		}
	}
}

防抖与节流引申出的一些有趣的知识点

  • 闭包
  • event loop
  • 作用域
  • this

考察构造函数、generator、promise规范

实现一个 Queue 构造函数，包含 task 和 start 方法，可以使用 start(time, cb) 方法添加延时任务，使用 start 方法执行所有添加的方法。例如 Queue().task(1000, ()=>{ console.log(1000) }).task(2000, ()=>{ console.log(2000) }).start()

class Queue {
	constructor() {
		this.queue = []
	}

	task(time, cb) {
		this.queue.push({
			time,
			cb
		})
		// 返回实例，就可以链式调用task来添加定时任务
		return this
	}

	start() {
		this._run(this._generator())
	}

	_generator() {
		const _this = this
		return function* gen() {
			for (let i = 0; i < _this.queue.length; i++) {
				const { time, cb } = _this.queue[i]
				// 利用promise生成异步函数
				yield new Promise((resolve, reject) => {
					setTimeout(() => { 
						resolve(cb()) 
					}, time)
				})
			}
		}
	}

	_run(generator) {
		const g = generator()

		function next(data) {
			let result = g.next(data)

			if (result.done) return

			// result 的 value 值就是 generator 函数体内的 promise 函数的返回值
			result.value.then(function(data) {
				next(data)
			})
		}

		next()
	}
}

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.