简单算法面试题

一、并发任务队列

class ConcurrentTaskQueue {
  constructor(concurrent) {
    this.concurrent = concurrent;
    this.queue = [];
    this.runningTask = [];
  }

  addTask(id, taskPromiseFn) {
    return new Promise((resolve, reject) => {
      this.queue.push({ id, taskPromiseFn, resolve, reject });

      this.runNext();
    });
  }

  runNext() {
    while (this.queue.length > 0 && this.runningTask.length < this.concurrent) {
      const task = this.queue.shift();

      this.runningTask.push(task);

      task
        .taskPromiseFn()
        .then(task.resolve)
        .catch(task.reject)
        .finally(() => {
          this.runningTask = this.runningTask.filter(
            (cur) => cur.id !== task.id
          );
          this.runNext();
        });
    }
  }
}

const queue = new ConcurrentTaskQueue(2);

queue.addTask("task1", task1).then(() => {
  console.log("task1");
});
queue.addTask("task2", task2).then(() => {
  console.log("task2");
});
queue.addTask("task3", task3).then(() => {
  console.log("task3");
});

function task1() {
  return new Promise((resolve) => setTimeout(resolve, 1000));
}
function task2() {
  return new Promise((resolve) => setTimeout(resolve, 3000));
}
function task3() {
  return new Promise((resolve) => setTimeout(resolve, 1000));
}

二、快速排序

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
}

// 测试
const array = [3, 6, 8, 10, 1, 2, 1];
console.log(quickSort(array)); // 输出：[1, 1, 2, 3, 6, 8, 10]

三、冒泡排序

function bubbleSort(arr) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    for (let j = 0; j < n - 1 - i; j++) {
      console.log(i, j);
      if (arr[j] > arr[j + 1]) {
        // 交换
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

const array = bubbleSort([5, 3, 8, 4, 2]); // [2,3,4,5,8]

console.log(array);