javascript - 面试现场编码 - 查找数组中的第二大数字

Question

快速元信息:

我一直在为这个问题寻找真正合适的地方，stackoverflow 上没有。仍然回答这个问题需要编程经验。

---

我是高级软件工程师，在拥有 250 名员工的公司领导 node.js 开发人员，因此我正在进行技术面试。我在这里只呆了 2 个月，所以我没有那么多经验(以前的公司小得多，所以很少雇用新的后端人员)。

面试部分是现场编码，通常通过 Skype。我认为这很重要，因为有些人真的什么都做不了。

但是有一件事让我很烦恼——很多人在“找到数组中第二大的数字”任务上失败了，我认为这很容易。

我通常给他们写这段代码，只有一个限制——不要对数组进行排序，也不要对数组使用任何特殊函数:

const _arr = [1, 7, 8, 5, 4, 2];

function findSecondBiggest(arr){
}

console.log(findSecondBiggest(_arr));

任务是将代码写入找到第二大数字的函数中。我认为这只是“检查”问题，对于大多数程序员来说是“只是做”。

即使是看起来很有前途的开发人员也常常在这方面失败。我知道他们承受着压力，但我什至试图引导他们，让他们平静下来，他们至少有 20 分钟的时间(通常甚至是 30 分钟，因为我在电话中多呆了 10 分钟，让他们有机会完成它)。 许多开发人员看起来很有前途 - 他们拥有丰富的经验和知识，能够评估他们使用此框架/技术的原因......但无法做到这一点。

我已经咨询过技术负责人，他说如果他们不能做到这一点，我们应该停止 - 因为我们正在寻找程序员并且我们期望编写代码。该公司还对中高级开发人员感兴趣。

这个任务真的那么难吗？或者，如果您至少可以想出简单的算法并加以实现，它是否真的是一个好的算法？

我也接受您使用两个 for 循环的解决方案，当第一个 for 循环找到最大的数字时，第二个 for 循环找到第二大的数字，因为它仍然是 O(n)。

Answer 1

这并不难，而且会让您思考。我肯定会在面试中使用这种问题。不过，我会准备一些指导性问题:

1. 如何找到最大的？
2. 你怎么知道一个数字是第 2 个？ 等等……

这是我可爱的解决方案(从 @BrettDeWoody's answer 窃取的测试用例)。您可以使用找到最大数的标准方法，然后将最小数也加上。

const _arr = [1, 7, 8, 5, 4, 2];

function findSecondBiggest(arr){
  const r = {};

  for(let i = 0; i < arr.length; i++) {
    if(r.first === undefined || arr[i] > r.first) {
      r.second = r.first;
      
      r.first = arr[i];
    } else if (arr[i] !== r.first && (r.second === undefined || arr[i] > r.second)) {
      r.second = arr[i];
    }
  }
    
  return r.second; // for arrays with length under 2, the answer would be undefined
}

console.log(findSecondBiggest([1, 7, 8, 5, 4, 2])); // 7
console.log(findSecondBiggest([1, 0, 0, 0, -1, -2])); // 0
console.log(findSecondBiggest([2, 2, 1, 0, -1, -2, 2])); // 1
console.log(findSecondBiggest([1, 1, 1, 1, 1])); // undefined
console.log(findSecondBiggest([0, 0, 0, 1])); // 0
console.log(findSecondBiggest([1, 2, 3, 4])); // 3
console.log(findSecondBiggest([Infinity, -Infinity])); // -Infinity
console.log(findSecondBiggest([-Infinity, Infinity])); // -Infinity
console.log(findSecondBiggest([1, 2, 3, 4, 5, Infinity])); // 5
console.log(findSecondBiggest([1])); // undefined