记一个朋友遇到的腾讯面试题

朋友面试腾讯，遇到了一个算法题，挺有意思的，特此记录一下。题目是这样的，给定一个数组如下：

let arr = [
  ["a", "aa", "aaa", "aaaa"],
  ["b", "bb", "bbb"],
  ["a", "ab", "aba"],
  ["a", "aa", "aab"]
]

将其转化成一个树状的子结构，如下：

[
  {
    name: "a",
    child: [
      {
        name: "aa",
        child: [
          {
            name: "aaa",
            child: [
              {
                name: "aaaa",
                child: [],
              },
            ],
          },
          {
            name: "aab",
            child: [],
          },
        ],
      },
      {
        name: "ab",
        child: [
          {
            name: "aba",
            child: [],
          },
        ],
      },
    ],
  },
  {
    name: "b",
    child: [
      {
        name: "bb",
        child: [
          {
            name: "bbb",
            child: [],
          },
        ],
      },
    ],
  },
];

这题需要借助 trie 的数据结构，什么是 trie？查看这篇文章。

全部解题代码如下：

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.root = {
        isWord: false,
        next: new Map()
    }
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let cur = this.root
    for(let c of word) {
        if(!cur.next.has(c))
            cur.next.set(c, { isWord: false, next: new Map() })
        cur = cur.next.get(c)
    }
    cur.isWord = true
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let cur = this.root
    for(let c of word) {
        if(!cur.next.has(c))
            return false
        cur = cur.next.get(c)
    }
    return cur.isWord
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let cur = this.root
    for(let c of prefix) {
        if(!cur.next.has(c))
            return false
        cur = cur.next.get(c)
    }
    return true
};

let t = new Trie()
let arr = [["a", "aa", "aaa", "aaaa"], ["b", "bb", "bbb"], ["a", "ab", "aba"], ["a", "aa", "aab"]]

for(let item of arr.flat(Infinity)) {
    t.insert(item)
}

let res = []

cur(t.root, res, '')
function cur(node, parent, pre='') {
    if(node.next.size === 0) return
    for(let [k, v] of node.next) {
        k = pre + k
        let child = []
        cur(v, child, k)
        let item = [{name: k, child}]
        parent.push(item)
    }
}

console.log(res)

接下来看一道字节的高频面试题

字节的面试题要相对难一些。具体题目是啥可以点这个链接查看，下面我只给出我的答案：

class Scheduler {
  constructor() {
    this.queue = [];
    this.count = 0;
  }
  add(promiseCreator) {
    let that = this;
    if (that.count > 1) return this.queue.push(promiseCreator);

    function fn(task) {
      that.count++;
      task().then(() => {
        that.count--;
        if (that.count < 2 && that.queue.length) {
          fn(that.queue.shift());
        }
      });
    }

    fn(promiseCreator);
  }
}

const timeout = (time) =>
  new Promise((resolve) => {
    setTimeout(resolve, time);
  });

const scheduler = new Scheduler();

const addTask = (time, order) => {
  scheduler.add(() => timeout(time).then(() => console.log(order)));
};

addTask(1000, "1");
addTask(500, "2");
addTask(300, "3");
addTask(400, "4");

// output: 2 3 1 4