得物面试题(day6)

[robbiemie]

Q: 实现⼀个 arrange 函数，可以进⾏时间和⼯作调度

[ > … ] 表⽰调⽤函数后的打印内容

arrange('William').execute(); 
> William is notified 
arrange('William').do('commit').execute(); 
> William is notified 
> Start to commit 
arrange('William').wait(5).do('commit').execute(); 
> William is notified 
等待 5 秒 
> Start to commit 
arrange('William').waitFirst(5).do('push').execute(); 
等待 5 秒 
> William is notified 
> Start to push 

Q: 实现⼀个函数

可以将数组转化为树状数据结构：

// ⼊参格式参考：
const arr = [
  { id: 1, name: "i1" },
  { id: 2, name: "i2", parentId: 1 },
  { id: 4, name: "i4", parentId: 3 },
  { id: 3, name: "i3", parentId: 2 },
  { id: 8, name: "i8", parentId: 7 },
];

Q: 实现⼀个异步任务处理函数

1. 第⼀个参数asyncTasks代表需要处理的任务列表，
2. 第⼆个参数n代表可以同时发起的任务数。所有任务完成后把处理结果按顺序放在数组⾥返回

⼊参格式参考:

const asyncTask1 = () => new Promise((resolve) => setTimeout(() => { console.log('resolve task 1'); resolve(); }, 1000)) 
const asyncTask2 = () => new Promise((resolve) => setTimeout(() => { console.log('resolve task 2'); resolve(); }, 2000)) 
const asyncTask3 = () => new Promise((resolve) => setTimeout(() => { console.log('resolve task 3'); resolve(); }, 2000)) 
const asyncTasks = [asyncTask1, asyncTask2, asyncTask3] 
handleAsyncTasks(asyncTasks, 2) 

 // 等待1s 
 // > resolve task 1 
 // 等待1s 
 // > resolve task 2 
 // 等待1s 
 // > resolve task 3 */

Q: 实现一个函数

从第⼀个参数，整数数组中，找到所有的组合, 并按照数组的⻓度有⼩到⼤的顺序 (**使得每个数组相加的值都等于第⼆个参数的值 **)

输⼊[1,2,3,4,5], 6 -> 输出 [[1,5], [2,4]，[1,2,3]]
输⼊[1,3], 6 -> 输出 []

[robbiemie]

Q: 实现⼀个 arrange 函数，可以进⾏时间和⼯作调度

arrange('William').execute(); 
> William is notified 
arrange('William').do('commit').execute(); 
> William is notified 
> Start to commit 
arrange('William').wait(5).do('commit').execute(); 
> William is notified 
等待 5 秒 
> Start to commit 
arrange('William').waitFirst(5).do('push').execute(); 
等待 5 秒 
> William is notified 
> Start to push 

A:

function arrange(name) {
  const sleep = time => new Promise(resolve => setTimeout(resolve, time * 1000))
  const cacheStack = []
  cacheStack.push(Promise.resolve(`${name} is notified `))
  return {
      async execute() {
          for(let p of cacheStack) {
              const result = await p
              result && console.log(result)
          }
      },
      do(type) {
          cacheStack.push(Promise.resolve(`Start to ${type}`))
          return this
      },
      wait(time) {
          cacheStack.push(sleep(time))
          return this
      },
      waitFirst(time) {
          cacheStack.unshift(sleep(time))
          return this
      }
  }

}

arrange('William').execute();
arrange('William').do('commit[').execute(); 
arrange('William').wait(5).do('commit').execute(); 
arrange('William').waitFirst(5).do('push').execute(); 

[robbiemie]

Q: 实现⼀个函数，可以将数组转化为树状数据结构

⼊参格式参考：

const arr = [
  { id: 1, name: "i1" },
  { id: 2, name: "i2", parentId: 1 },
  { id: 4, name: "i4", parentId: 3 },
  { id: 3, name: "i3", parentId: 2 },
  { id: 8, name: "i8", parentId: 7 },
];
// 出参格式可⾃⾏设计

/**
 * TreeNode
 * @param {number} id
 * @param {string} name
 * @param {[TreeNode]} children
 */
class TreeNode {
  constructor(props) {
    this.id = props.id;
    this.name = props.name;
    this.children = props.children || [];
  }
}

function buildTree(arr = []) {
  /*** 此处写代码逻辑 */
  if (!arr || arr.length === 0) {
    console.warn("No data");
    return;
  }
  let root = null 
  let nodeCount = 0
    // 寻找根节点
    arr.forEach((item) => {
        if(!item.parentId) {
            root = new TreeNode(item)
            nodeCount++
        }
  })
  
  /**
   * 递归生成 TreeNode
   * @param {*} node 
   * @param {*} array 
   */
  const fn = (node, array) => {
    array.forEach(item => {
        if(item.parentId === node.id) {
            // 插入子树
            const nodeTree = new TreeNode(item)
            node.children.push(nodeTree)
            nodeCount++
        }
    })

    node.children.forEach(item => {
        fn(item, array)
    })
  }

  fn(root, arr)
  return root
}

buildTree(arr);

[robbiemie]

Q: 实现⼀个函数

从第⼀个参数，整数数组中，找到所有的组合, 并按照数组的⻓度有⼩到⼤的顺序
使得每个数组相加的值都等于第⼆个参数的值

 输⼊[1,2,3,4,5], 6 -> 输出 [[1,5], [2,4]，[1,2,3]] 
 输⼊[1,3], 6 -> 输出 [] 

function getAllArrays(array, value) { 
    /** * 此处写代码逻辑 */ 
    let results = []
    let rightIndex = array.length - 1
    // 外层循环从大到小遍历数组
    while(rightIndex) {
        let sum = value
        let index = rightIndex
        let arr = []
        // 内层循环找符合的元素
        while(sum > 0 && index >= 0) {
            if(sum >= array[index]) {
                arr.push(array[index])
                sum -= array[index]
            }
            index--
        }
        // 匹配
        if(sum === 0) {
            results.push(arr.sort())
        }
        rightIndex--
    }
    return results
}
console.log(getAllArrays([1,2,3,4,5], 6))

[robbiemie]

Q: 实现⼀个异步任务处理函数

1. 函数第⼀个参数asyncTasks代表需要处理的任务列表，
2. 第⼆个参数n代表可以同时发起的任务数。所有任务完成后把处理结果按顺序放在数组⾥返回

⼊参格式参考:

 const asyncTask1 = () => new Promise((resolve) => setTimeout(() => { console.log('resolve task 1'); resolve(); }, 1000)) 
 const asyncTask2 = () => new Promise((resolve) => setTimeout(() => { console.log('resolve task 2'); resolve(); }, 2000)) 
 const asyncTask3 = () => new Promise((resolve) => setTimeout(() => { console.log('resolve task 3'); resolve(); }, 2000)) 
 const asyncTasks = [asyncTask1, asyncTask2, asyncTask3] 
 handleAsyncTasks(asyncTasks, 2) 

 // 等待1s 
 // > resolve task 1 
 // 等待1s 
 // > resolve task 2 
 // 等待1s 
 // > resolve task 3 */

function handleAsyncTasks(asyncTasks, n) {
  /*** 此处写代码逻辑 */
  let limit = n;
  let tasks = asyncTasks || [];
  let pool = []; // 缓存池

  function addTask() {
      if(tasks.length === 0) return
      let task = tasks.shift();
      let promise = task();
      pool.push(promise);
      return promise;
  }

  function deleteTask(promise) {
    promise.then((_) => {
        pool.splice(pool.indexOf(promise), 1);
      });
  }


  // 先将缓存池塞满
  while (tasks.length > 0 && pool.length < limit) {
    let promise = addTask();
    deleteTask(promise)
  }
  
  const race = Promise.race(pool);
  race.then((_) => {
    if (tasks.length === 0) return;
    let promise = addTask();
    deleteTask(promise)
  });
}

const asyncTask1 = () =>
  new Promise((resolve) =>
    setTimeout(() => {
      console.log("resolve task 1");
      resolve();
    }, 1000)
  );
const asyncTask2 = () =>
  new Promise((resolve) =>
    setTimeout(() => {
      console.log("resolve task 2");
      resolve();
    }, 2000)
  );
const asyncTask3 = () =>
  new Promise((resolve) =>
    setTimeout(() => {
      console.log("resolve task 3");
      resolve();
    }, 2000)
  );
const asyncTasks = [asyncTask1, asyncTask2, asyncTask3];
handleAsyncTasks(asyncTasks, 2);