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

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)。

- libik

---

可能应该发布在计算机科学Stack Exchange上。 - Brett DeWoody

我知道这将是主观性很强的 - 但这绝对不是一个难题。你的候选人是否知道会有编程问题？ - gurvinder372

这确实是一个非常琐碎的问题。 - Adriano

也许更适合于 https://codegolf.meta.stackexchange.com/。 - smac89

我希望能被问到这个问题。它远非简单，事实上它关乎基本算法素养。我的答案会先介绍一下刘易斯·卡罗尔（提出了这个问题，但解法不正确），然后按照斯泰潘诺夫的二进制计数器实现（链接：https://github.com/Meghdeep/Binary-Counter-Stepanov/blob/master/Stepanov's%20Original%20Code/Lecture%20-%2011/min_element1_2.h）。不过我认为20分钟是不够的。斯泰潘诺夫讲解这个问题用了10个讲座。 - user58697

Answer 1

这并不难，而且可以让你思考。我肯定会在面试中使用这种问题。但是，我会准备一些引导性问题：

1. 如何找到最大值？
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

- Ori Drori

---

不要使用任何特殊的数组函数。我认为使用缩减函数实际上也算是这样做了。可能已经省去了编写外部循环的样板代码。此外，如果数组在某个位置包含负数后跟零，则会失败，因为这会在错误的时间触发!r.first。 - Ext3h

我实际上会接受这个解决方案，虽然有一些边缘情况，但整个算法已经写在这里了。 - libik

@Ext3h - 在这种情况下，Array#reduce不过是一个被美化的循环。然而，我已经将其改为了for循环。你对于!r.first/second的看法是正确的，所以我已经将其改为了r.first/second === undefined。 - Ori Drori

虽然这仍然不是一个理想的解决方案。从逻辑和运行时复杂度来看，它是完全没问题的。然而，在循环中不使用严格类型（可能导致undefined）会阻止JIT编译器进行重要的优化。预先初始化对象，并将非等值检查移出循环可以实现该优化。 - Ext3h

Answer 2

实际上，开发人员会选择最简单的方法。也就是说，他们会对数组进行排序并取第二个最大的元素。这样可以减少编写代码和思考的时间。在我的看法中，这是一个胜利。

因此，你需要考虑的问题是，你想要记住如何从头开始正确实现此算法的开发人员（可能存在错误），还是想要那些可以重复使用已经存在的方法，在最短的时间内找到解决方案，并且几乎没有时间惩罚，并且基本上没有错误。

我的意思是，你上一次想在数百万个元素的数组中找到第二大的元素是什么时候？大多数开发人员可能只会选择我最初描述的方法（排序并取第二大），如果发现代码是任何性能问题的瓶颈，则将优化留给O(n)的另一个时机。

- smac89

---

我理解你的观点，但并不完全同意。这个任务的原因绝对不是“需要了解算法”，而是为了证明你具有一定的分析思维，并且能够将其转化为代码。我认为“查找第二大的数字”足够简单，可以展示这一点……那么你会采取什么方法或者任务来进行现场编码，以证明这一点呢？ - libik

@libik，你必须小心，不要过于沉迷于“分析性”等词语。根据你刚才所说的，我认为你更看重那些引入更多复杂性的开发者，而不是那些正在重复利用已有资源的开发者。万物皆有时，现在不是创新超工程解决方案的时候，可以用两行简短的代码解决的问题。如果由我来决定，我会向潜在雇员提出一个经常在代码库中遇到的问题。 - smac89

这些可能涉及数据库查询、实现服务、与某些端点通信、探索减少发送数据量的方法、不同的缓存方式等。这些都是对你很重要的事情，所以在招聘人员时应该专注于这些方面。当然，除非在列表中查找第二大的值对你很重要，那么你应该将该方法编写为公司基础库的一部分并继续前进。我相信除了一个简单的“max”函数之外，还有其他需要创新的东西。 - smac89

Answer 3

完全同意smac89的观点。作为工程招聘团队和代码导师的一员，我不喜欢有不切实际约束条件的面试问题。

与其问一个候选人在技术面试之外永远遇不到的问题，不如提出一个挑战性的问题，与候选人将要处理的工作相关，并允许候选人展示他们对将要使用的语言和技能的知识。

一个很好的例子是，一个朋友最近分享了一个前端面试问题 - 在时间限制内构建一个简单的应用程序，而不使用任何库。

使用提供的API端点（使用?page=N查询参数返回分页结果），应用必须接受用户的搜索，检索所有结果（这可能涉及多个结果页面），按字母顺序排序所有结果，并立即显示所有结果。这需要对fetch、Promise（以及Promise.all）、数组方法、事件监听器和原始JavaScript DOM操作进行了解（更重要的是，意识）。

候选人可以参考任何文档，并根据需要使用任何内置方法。时间限制足够完成，只要候选人对内置JS方法、Fetch API、Promises等有些许了解即可。

在我看来，这是一个非常完美的面试问题（至少对于前端开发人员而言）。

以下是我的解决方案：

• 使用ES5
• 不使用任何数组方法（除了Array.length）
• 处理诸如同类数组、长度为1的数组等边缘情况

function findSecondBiggest(arr, startInd){
  let start = startInd || 0;
  let largest = arr[start];
  let secondLargest = null;
  const arrLength = arr.length;
  
  if (start === arrLength - start) {
    return null;
  }
    
  for (var i = start + 1; i < arrLength; i++) {
    largest = arr[i] > largest ? setSecond(largest) && arr[i] : largest;
  }
  
  function setSecond(num, check) {
    secondLargest = num;
    return true;
  }
  
  if (secondLargest === null) {
    arr[arrLength] = arr[0];
    return findSecondBiggest(arr, start + 1);
  }
  
  return secondLargest;
}

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

- Brett DeWoody

Answer 4

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

function findSecondBiggest(arr) {
    if(arr.length < 2) {
        return undefined;
    }
    var first = arr[0];
    var second = arr[1];
    if(second > first) {
        [first, second] = [second, first];
    }
    for(var i = 2; i < arr.length; i++) {
        var tmp = arr[i];
        if(tmp > first) {
            [first, second] = [tmp, first];
        } else if(tmp > second) {
            [first, second] = [first, tmp];
        }
    }
    return first != second ? second : undefined;
}

console.log(findSecondBiggest(_arr));

不，我不会说这是一个非常难的问题。尽管有一些陷阱可能会在紧张情况下轻易使人迷失：

• 处理错误输入（输入元素不足）
• 对输入头进行特殊处理
• 如果您不知道ES6语法，则交换变量
• 混淆索引和值

因此，虽然不难，但有几个陷阱可能会让候选人轻易困惑或混淆。

- Ext3h

Answer 5

const findSecondBiggest = arr => {
    let max1 = Number.MIN_VALUE;
    
    return arr.reduce((acc, x) => {
        if(x > max1) {
            acc = max1;
            max1 = x;
        } else if (x > acc && x < max1) {
            acc = x;
        }
        
        return acc;
    }, Number.MIN_VALUE);
}

- user21429442

---

欢迎来到StackOverflow！虽然这可能回答了问题，但如果您解释一下它是如何以及为什么解决问题的话，它将具有更长期的价值。关于您的解决方案的一个问题：如果您要像这样缩小范围，为什么不使用[最大值，第二大值]作为累加器呢？类似这样：const findSecondLargest = (xs) => xs .reduce (([m, n], x) => x > n ? [n, x] : x > m ? [x, n] : [m, n], [-Infinity, -Infinity]) [0]？ - Scott Sauyet

Answer 6

var a = [1, 7, 8, 5, 4, 2];

   for (var i = 0; i < a.length ; i++) {
       var big = 0;
       for (var j = 0; j < a.length ; j++) {               
           if (a[j] > a[i]) big++;
       }           
       if (big == 1) {
           return a[i];
       }
   }

并且使用预定义的方法

a[a.sort().length-2]

- Ashutosh Jha