常见编程题

一、实现EventEmitter

class EventEmitter {
	constructor() {
		this.events = {}
	}
	on(name, fn) {
		this.events[name] = (this.events[name] || []).push(fn)
		return this
	}
	off(name, fn) {
		// 移除该事件下的所有监听器
		if (!fn) {
			this.events[name] = []
		} else {
			this.events[name] = (this.events[name] || []).filter(f => f !== fn)
		}
		return this
	}
	emit(name, ...args) {
		(this.events[name] || []).map(fn => {
			fn.apply(this, args)
		})
		return this
	}
	once(name, fn) {
		let wrapperFn = (...args) => {
			fn.apply(this, args)
			this.off(name, wrapperFn)
		}
		this.on(name, wrapperFn)
		return this
	}
}

// 测试
let ee = new EventEmitter();

function a() {
	console.log('a')
}

function b() {
	console.log('b')
}

function c() {
	console.log('c')
}

function d(...a) {
	console.log('d', ...a)
}

ee.on('event1', a).on('event1', b).once('event2', c)

ee.emit('event1').emit('event2').emit('event2').off('event1').emit('event1')

二、深拷贝和浅拷贝

浅拷贝

创建一个对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，那么拷贝的就是基本类型的值，如果属性是引用类型，那么拷贝的就是内存地址，所以如果其中一个对象修改了某些属性，那么另一个对象就会受到影响。可以使用Object.assign()或者通过展开运算符 ... 来实现浅拷贝。

let a = { age: 1 }
let b = Object.assign({}, a)
let c = {...a};
a.age = 2
console.log(b.age) // 1
console.log(c.age)  // 1

深拷贝

从内存中完整地拷贝一个对象出来，并在堆内存中为其分配一个新的内存区域来存放，并且修改该对象的属性不会影响到原来的对象。简单的做法：JSON.parse(JSON.stringfy(obj))，但是该方法也是有局限性的：

• 会忽略undefined、symbol、函数
• 不能解决循环引用的对象 （会报错）

解决循环引用问题，我们可以额外开辟一个存储空间，来存储当前对象和拷贝对象的对应关系，当需要拷贝当前对象时，先去存储空间中找，有没有拷贝过这个对象，如果有的话直接返回，如果没有的话继续拷贝，这样就巧妙化解循环引用的问题。这个存储空间，需要可以存储key-value形式的数据，且key可以是一个引用类型，我们可以选择Map这种数据结构：

• 检查map中有无克隆过的对象
• 有 - 直接返回
• 没有 - 将当前对象作为key，克隆对象作为value进行存储
• 继续克隆

function clone(target, map = new WeakMap()) {
	if (!isObject(target)) {
		return target
	}
	var cloneTarget = Array.isArray(target) ? [] : {}
	if (map.get(target)) {
		return map.get(target)
	}
	map.set(target, cloneTarget)
	for (var key in target) {
		cloneTarget[key] = clone(target[key], map)
	}
	return cloneTarget
};

function isObject(obj) {
	return Object.prototype.toString.call(obj) === '[object Object]'
}

const target = {
	field1: function() {
		console.log(1)
	},
	field2: undefined,
	field3: {
		child: 'child'
	},
	field4: [2, 4, 8],
	field5: new Date()
};
target.target = target

console.log(clone(target))

WeakMap 对象是一组键/值对的集合，其中的键是弱引用的。其键必须是对象，而值可以是任意的。 使用WeakMap，map和target存在的就是弱引用关系，当下一次垃圾回收机制执行时，这块内存就会被释放掉。

参考

深拷贝 - BFS (广度优先遍历)

// 如果是对象/数组，返回一个空的对象/数组，
// 都不是的话直接返回原对象
function getEmptyArrOrObj(item) {
  let itemType = Object.prototype.toString.call(item) 
  if(itemType === '[object Array]') {
    return []
  }
  if(itemType === '[object Object]') {
    return {}
  }
  return item
}

function deepCopyBFS(origin) {
  const queue = []
  const map = new Map() // 记录出现过的对象，处理环

  let target = getEmptyArrOrObj(origin)

  if(target !== origin) {
    // 说明origin是一个对象或数组，需要拷贝子代
    queue.push([origin, target]);
    map.set(origin, target)
  }

  while(queue.length) {

    let [ori, tar] = queue.shift(); // 出队

    for(let key in ori) {
      if(ori.hasOwnProperty(key)) { // 不在原型上

        if(map.get(ori[key])) { // 处理环
          tar[key] = map.get(ori[key])
          continue
        }

        tar[key] = getEmptyArrOrObj(ori[key]);
        if(tar[key] !== ori[key]) {
          queue.push(ori[key], tar[key])
          map.set(ori[key], tar[key])
        }
      }
    }
  }

  return target
}

深拷贝 - DFS

function deepCopyDFS(origin){
	let stack = [];
	let map = new Map(); // 记录出现过的对象，用于处理环

	let target = getEmptyArrOrObj(origin);
	if(target !== origin){
		stack.push([origin, target]);
		map.set(origin, target);
	}

	while(stack.length){
		let [ori, tar] = stack.pop();
		for(let key in ori){
      if(ori.hasOwnProperty(key)) { // 不在原型上
        // 处理环状
        if(map.get(ori[key])){
          tar[key] = map.get(ori[key]);
          continue;
        }

        tar[key] = getEmptyArrOrObj(ori[key]);
        if(tar[key] !== ori[key]){
          stack.push([ori[key], tar[key]]);
          map.set(ori[key], tar[key]);
        }
      }
		}
	}

	return target;
}

参考

三、在一个数组中求连续最大的累加和

我们用dp[i]表示遍历到a[i]时的最大累加和。

• 当dp[i-1]小于0时，dp[i]取a[i]。
• 当dp[i-1]不小于0时，dp[i]取dp[i-1]+a[i]。

所以状态方程：max(dp[i]) = getMax(max(dp[i-1]) + a[i], a[i])。时间复杂度O(n)，空间复杂度O(n)。代码如下：

function getMax(argument) {
	if (arr.length == 1) {
		return arr[0]
	}
	var temp = arr[0], 
		max = arr[0]  // 最大和
	for (var i = 1; i < arr.length; i++) {
		temp = Math.max(temp + arr[i], arr[i])
		temp > max && (max = temp)
	}
	return max
}

四、手写实现inherit函数

// 返回一个继承自原型对象proto的属性的新对象
// 这里可以用到ES5的Object.create()函数
function inherit(proto) {
    //proto是一个对象，但不能是null
    if(proto == null) throw TypeError();
    if(Object.create) return Object.create(proto);    //如果Object.create()存在,使用它
    var t = typeof proto;                    //否则进一步检查
    if(t!=='object' && t!=='function') throw TypeError();
    var F = function() {};        // 定义一个空构造函数
    F.prototype = proto;        // 将其原型属性设置为proto
    return new F();                // 使用F()创建proto的继承对象
}

五、手写 ajax

function ajax(){
    var xmlhttp;
    if(window.XMLHttpRequest){
        xmlhttp = new XMLHttpRequest();
    }else{
        // code for IE6, IE5
        xmlhttp = ActiveXObject("Microsoft.XMLHTTP");
    }

    //判定执行状态
    xmlhttp.onreadystatechange = function(){
        /*
        readyState
            0: 请求未初始化
            1: 服务器连接已建立
            2: 请求已接收
            3: 请求处理中
            4: 请求已完成，且响应已就绪
        status
            200:请求成功
            404:未找到
            500:服务器内部错误
        */
        if (xmlhttp.readyState==4 && xmlhttp.status==200){
            document.getElementById("myDiv").innerHTML=xmlhttp.responseText;//获得字符串形式的响应数据
        }
      }
    xmlhttp.open("Get","url",true);

    //设置头信息
    xmlhttp.setRequestHeader("Content-type","application/x-www-form-urlencoded");

    //将信息发送到服务器
    xmlhttp.send();    

}

六、map和reduce互相转换

reduce实现map

// reduce实现map
Array.prototype.myMap = function(callback) {
    return this.reduce((accr, cur, index) => {
        accr.push(callback(cur))
        return accr;
    }, [])
}

var arr = [1, 2, 3]
arr = arr.myMap((item, index) => {
    item *= 2;
    return item;
})

console.log(arr)

map实现reduce

// map实现reduce
Array.prototype.myReduce = function(callback, accurlater) {
    let accur = accurlater
    if (typeof callback != 'function') {
        throw new TypeError(callback + ' is not a function');
    } else {
        this.map((item, index) => {
            accur = callback(accur, item, index)
        })
        return accur;
    }
}

var arr = [1, 2, 3]
arr = arr.myReduce((accr, cur, index) => {
    accr *= cur;
    return accr;
}, 1)

console.log(arr)

七、函数式编程 compose

手动实现一个compose函数，满足以下功能

var arr = [func1, func2, func3];
function func1 (ctx, next) {
    ctx.index++
    next();
}
function func2 (ctx, next) {
    setTimeout(function() {
        ctx.index++;
        next();
    });
}
function func3 (ctx, next) {
    console.log(ctx.index);
}
compose(arr)({index: 0}); // 输出：2

实现：

const compose = arr => args => {
    return dispatch(0)

    function dispatch(i) {
        const fn = arr[i];
        if (!fn) {
            return Promise.resolve();
        }
        return Promise.resolve(fn(args, function next() {
            return dispatch(i + 1)
        }))
    }
}

实现以下功能

compose([a, b, c])('参数')
=>
a( b( c('参数') ) )

实现

function a(num) {
    return num * 2
}

function b(num) {
    return num * 3
}

function c(num) {
    return num * 4
}

const compose = arr => args => {
    const len = arr.length;
    let index = len - 1;
    let result = arr[index](args); // 第一次执行的结果

    while (--index >= 0) {
        result = arr[index](result);
    }
    return result;
}

console.log(compose([a, b, c])(2)); // 48

八、实现无限累加

基础版本

实现add(1)(2)(3)(4)函数无限极累加。方法是重写函数的toString()方法

const add = a => {
    const temp = b => (add(a + b))
    temp.toString = () => (a)
    return temp
}

升级版

实现一个求和函数add，支持任意参数: add(1), add(1,2,3,4); 支持连续调用: add(1)(2)(3)。如下所示：

const result = add(1)(2, 3)(4, 5, 6)(7, 8, 9, 10)(10)
console.log(result) // 输出 65

const add = (...arg1) => {
    const sum1 = arg1.reduce((a, b) => (a + b))
    const temp = (...arg2) => {
        const sum2 = arg2.reduce((a, b) => (a + b))
        return add(sum1 + sum2)
    }
    temp.toString = () => (sum1)
    return temp
}