附加题

answer.md

1. n^2
2. 在 UTF-8 编码规范中，8 个 character 组成的编号代表一个 byte，每个 character 以 0 或 1 表示。string 是一组 byte 或 character。 一个字符以 8 个 byte character 代表。 Unicode 是一种文字编码方案，目的是为了统一表示全球所有文字符号。UTF-8, UTF-16, GB2312 和 GB18030 是 Unicode 的几个具体实现
3. iOS/MacOS

• iOS 下的微信，在登录了电脑版后，没有一个智能判断用户目前在哪个设备上活跃，而把消息通知只发到那个平台上
• iOS 下的 Twitter，没有浏览记录，如果回想起某条推文很难再找到
• MacOS 和 iPhone 手机有很多互动可以产生很有趣的交互，我还期望可以在我拿着 iPhone 离开 Macbook 后可以自动锁屏的功能

4. 工厂模式-生成器模式：生成器模式相比工厂模式会通过生成一些部件组合成复杂的功能 适配器-装饰器：装饰器是把原有功能之外做的功能转换

5. 如果不考虑旋转的情况下，可以把这个问题分解成怎么在一个轴上插入一段线段并且与原有线段不相交。 插入线条的问题再分解成两条线条是否相交的问题。gist

insertLine.ts

type Line = [number, number]
const isOverlap = (a: Line, b: Line) => !(a[0] > b[1] || b[0] > a[1])

const mergeTwoLines = (a: Line, b: Line): Line => [
  Math.min(a[0], b[0]),
  Math.max(a[1], b[1])
]

const mergeLines = (lines: Line[]) => {
  for (let i = 0; i < lines.length - 1; i ++) {
    for (let j = 1; j < lines.length - 1; j ++) {
      const a = lines[i]
      const b = lines[j]
      if (isOverlap(a, b)) {
        lines.splice(i, 1, null)
        lines.splice(j, 1, null)
        const nextLines = lines.filter(l => l)
        return mergeLines([mergeTwoLines(a, b), ...nextLines])
      }
      return lines
    }
  }
  return lines
}

const sortLines = (lines: Line[]) => lines.sort((a, b) => a[1] - b[0])

const conactLines = (a: Line, b: Line) => {
  return [a[1], b[0]]
}


function insertLine(newLine: Line, lines: Line[]) {
  // 合并线段并排序
  const sortedMergedLines = sortLines(mergeLines(lines))
  // 找到空余的互补线段
  const complementLines = []
  sortedMergedLines.forEach((line, i, lines) => {
    const nextLine = lines[i + 1] || [Infinity, Infinity]
    complementLines.push(conactLines(line, nextLine))
  })
  // 找到空余线段与要插入的线段相交的地方就是要插入的地方
  return complementLines.find(line => isOverlap(line, newLine))
}

const line: Line = [5, 6]
const lines: Line[] = [[1,4], [2,3], [4,5], [7,9]]
console.log( insertLine(line, lines) )