2018-09-28__一些有趣的笔试编程题.md

一些有趣的笔试编程题

任务队列实现

实现一个AI任务队列，提供以下接口：

1. AI.talk() // 执行一次任务，输出'talk'

2. AI.cancel() // 取消上一次任务的执行，成功取消输出'cancel'，如果未有任务执行输出'notask'

3. AI.sleep(num) // num秒后再执行任务，等待任务本身可以被取消

例子：

AI.talk()
// talk

AI.cancel()
// notask

AI.talk().cancel()
// cancel

AI.sleep(3).talk()
// 等待3秒后输出 talk

AI.cancel().talk().sleep(3).talk().cancel().sleep(3).talk()
// notask
// talk
// 等待3s后
// cancel
// 继续等待3s后
// talk

简单实现

const AI = {
  tasks: [],
  sleepTime: 0,
  flushed: false,
  flush () {
    if (!this.flushed) {
      setTimeout(() => {
        this.tasks.forEach(task => {
          if (typeof task === 'function') {
            task()
          }
        })
        this.tasks = []
        this.flushed = false
        this.sleepTime = 0
      }, 0)
      this.flushed = true
    }
  },
  talk () {
    if (this.sleepTime) {
      const delay = this.sleepTime * 1000
      this.tasks.push(() => {
        setTimeout(() => {
          console.log('talk')
        }, delay)
      })
    } else {
      this.tasks.push(() => console.log('talk'))
    }
    this.flush()
    return this
  },
  sleep (n) {
    this.sleepTime += n
    this.tasks.push(n)
    return this
  },
  cancel () {
    const task = this.tasks.pop()
    if (task !== undefined) {
      if (typeof task === 'number') {
        this.sleepTime -= task
      }
      const delay = this.sleepTime
      if (delay) {
        this.tasks.push(() => {
          setTimeout(() => {
            console.log('cancel')
          }, delay)
        })
      } else {
        this.tasks.push(() => console.log('cancel'))
      }
    } else {
      this.tasks.push(() => console.log('notask'))
    }
    this.flush()
    return this
  }
}

leetcode 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

简单实现

function longestConsecutive (nums) {
  const map = {}
  const done = {}
  let max = 0
  nums.forEach(n => map[n] = 1)
  nums.forEach(n => {
    if (done[n]) return
    let left = n - 1
    let right = n + 1
    let _max = 1
    while (map[left]) {
      done[left] = true
      _max++
      left--
    }
    while (map[right]) {
      done[right] = true
      _max++
      right++
    }
    done[n] = true
    max = Math.max(max, _max)
  })
  return max
}