阿里校招前端笔试题

阿里前端笔试题，题目不多，难度也不大，我只记录了两道稍微有点难度的编程题。题目如下：
1.JSON.stringify 的功能是，将一个 JavaScript 字面量对象转化为一个 JSON 格式的字符串。例如

const obj = {a:1, b:2}
JSON.stringify(obj) // => '{"a":1,"b":2}'

当要转化的对象有“环”存在时（子节点属性赋值了父节点的引用），为了避免死循环，JSON.stringify 会抛出异常，例如：

const obj = {
  foo: {
    name: 'foo',
    bar: {
      name: 'bar',
      baz: {
        name: 'baz',
        aChild: null // 待会将指向obj.bar
      }
    }
  }
}
obj.foo.bar.baz.aChild = obj.foo // foo->bar->baz->aChild->foo形成环
JSON.stringify(obj) // => TypeError: Converting circular personucture to JSON

请完善以下“环”检查器函数 cycleDetector，当入参对象中有环时返回 true，否则返回 false。

function cycleDetector(obj) {   
  // 请添加代码
}

解题思路：首先很容易想到要遍历这个对象，然后判断属性值是否为一个对象，如果是，则递归遍历这个属性值，但难点是该如何判断这个属性值是否为某个父节点的引用，要怎样拿到父节点的引用呢？？？
其实我们可以先用一个数组cache用来保存属性值(对象类型)，再用一个标记变量来标记是否有环，然后遍历时判断这个属性值的类型是否为一个对象，如果是，则判断这个属性值是否在那个cache数组里，如果在，则表明有环，如果不在，则把这个属性值添加到数组里，再递归遍历这个属性值即可。
初步代码如下：

function cycleDetector(obj) {
  let hasCircle = false, //用一个变量去标记是否有环
    cache = []; //保存值为对象的属性值
  (function(obj) {
    Object.values(obj).forEach(value => {
      if (Object.prototype.toString.call(value) === "[object Object]" && value !== null) {
        const index = cache.indexOf(value)
        if (index !== -1) { //如果cache中存在这个value，则表示有环
          hasCircle = true
          return
        } else {
          cache.push(value)  //添加到cache数组里
          arguments.callee(value)  //递归遍历这个value
        }
      }
    })
  })(obj)
  return hasCircle
}

以上代码似乎没啥问题，满足题目例子中的要求，但是没有考虑到叔叔、爷爷的兄弟等一些特殊情况。循环引用是引用父引用路径上的直系祖先，引用叔叔、爷爷的兄弟等是不会形成环的。例如下面叔叔的情况：

const obj = {
  a: {
    c: 1
  },
  b: {
    d: null // null 等下填充引用的地方
  }
};
obj.b.d = obj.a; // 并不会形成环，cache数组的设定存在问题
JSON.stringify(obj) // 可以正常序列化，说明没有环
console.log(cycleDetector(obj))  // 打印出来的却是true，说明有问题

这种情况打印出的结果是true，而预期结果是false，说明判断错了。那要怎样改呢？？？其实我们可以有两种思路：
方法一：在递归调用后再次判断是否有环，没有的话就把value从cache数组里弹出。意思就是，如果一个属性值下的所有子节点都不存在有环的情况，那么我们就完全可以将这个value弹出，后期就不会存在叔叔或者爷爷的兄弟的情况了(因为已经被弹出了)。
修改后的代码如下：

function cycleDetector(obj) {
  let hasCircle = false, //用一个变量去标记是否有环
    cache = []; //保存值为对象的属性值
  (function(obj) {
    Object.values(obj).forEach(value => {
      if (Object.prototype.toString.call(value) === "[object Object]" && value !== null) {
        const index = cache.indexOf(value)
        if (index !== -1) { //如果cache中存在这个value，则表示有环
          hasCircle = true
          return
        } else {
          cache.push(value)
          arguments.callee(value)
          if (!hasCircle) cache.pop() //递归调用后再判断是否有环，没有的话就把value从cache数组里弹出
        }
      }
    })
  })(obj)
  return hasCircle
}

这时就可以得到预期的结果了：

const obj = {
  a: {
    c: 1
  },
  b: {
    d: null 
  }
};
obj.b.d = obj.a; 
JSON.stringify(obj) // 可以正常序列化，说明没有环
console.log(cycleDetector(obj))  // 打印出来的却是false，证明确实是没有环的

方法二：通过ancestor数组保存直系祖先，更直接，但不易理解

function cycleDetector(obj) {
  let ancestor = []; //保存祖先
  return (function(obj, ancestor) {
    if (Object.prototype.toString.call(obj) !== "[object Object]" || obj === null) return false
    if (ancestor.indexOf(obj) !== -1) return true
    ancestor = [...ancestor, obj] //直接拿到他的直系祖先,并和原祖先合并
    return Object.values(obj).some(value => arguments.callee(value, ancestor))
  })(obj, ancestor)
}
const obj = {
  a: {
    c: 1
  },
  b: {
    d: null 
  }
};
obj.b.d = obj.a; 
JSON.stringify(obj) // 可以正常序列化，说明没有环
console.log(cycleDetector(obj))  // 打印出来也是false，也说明没有环

2.实现一个EventEmitter类，这个类包含以下方法：
on（监听事件，该事件可以被触发多次）
once（也是监听事件，但只能被触发一次）
fire（触发指定的事件）
off（移除指定事件的某个回调方法或者所有回调方法）

class EventEmitter {
  /**请补充你的代码***/
}
const event = new EventEmitter()
const drank = (person) => {
  console.log(person + '喝水')
}
event.on('drank', drank)
event.on('eat', (person) => {
  console.log(person + '吃东西')
})
event.once('buy', (person) => {
  console.log(person + '买东西')
})
event.fire('drank', '我')   // 我喝水  
event.fire('drank', '我')   // 我喝水  
event.fire('eat', '其它人')   // 其它人吃东西
event.fire('eat', '其它人')   // 其它人吃东西
event.fire('buy', '其它人')  //其它人买东西
event.fire('buy', '其它人')  //这里不会再次触发buy事件，因为once只能触发一次
event.off('eat')  //移除eat事件
event.fire('eat', '其它人')  //这里不会触发eat事件，因为已经移除了

解题思路：这题其实就是实现发布-订阅模式了，难点在于怎样实现once事件，即只触发一次。其实也就是要实现两种类型的事件，我们可以用不同的对象去保存这两种类型的事件，然后在fire的时候，这两种事件都要被处理即可。
具体代码如下：

class EventEmitter {
	constructor() {
		this.queue = {} //可触发多次的事件
		this.onceQueue = {} //只能触发一次的事件
	}
	on(event, fn) {  //监听事件，可以触发多次
		if (!this.queue[event]) this.queue[event] = []
		this.queue[event].push(fn)
	}
	once(event, fn) {   //监听事件，只能触发一次
		if (!this.onceQueue[event]) {
			this.onceQueue[event] = {
				fns: [],
				hasFired: false
			}
		}
		this.onceQueue[event].fns.push(fn)
	}
	fire() {  //触发指定的事件
		const event = [].shift.call(arguments), //取得事件名称
			fns = this.queue[event],  //取得该事件里所有的回调函数（可以触发多次的事件）
			onceFns = this.onceQueue[event]  //取得该事件里所有的回调函数（只能触发一次的事件）
		if (fns && fns.length != 0) {
			let i = 0,fn
			while (fn = fns[i++]) {
				fn.apply(this, arguments)
			}
		}
		if (onceFns && !onceFns.hasFired) {
			let i = 0,fn
			while (fn = onceFns.fns[i++]) {
				fn.apply(this, arguments)
			}
			this.onceQueue[event].hasFired = true
		}
	}
	off(event, fn = null) { //可移除特定事件里的某个回调函数或者所有回调函数
		const fns = this.queue[event]
		if (!fns || fns.length == 0) return
		if (fn) { //移除该事件特定的回调
			this.queue[event] = fns.filter(item => {
				return item !== fn
			})
		} else { //移除该事件所有的回调
			this.queue[event] = []
		}
	}
}