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

8fq7wneg  于 2023-03-22  发布在  Node.js
关注(0)|答案(6)|浏览(128)

快速元信息:
我正在寻找这个问题的真正正确的地方,在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循环找到第二个最大的数字,因为它仍然是O(n)。

zi8p0yeb

zi8p0yeb1#

这并不难,而且会让你思考。我肯定会在面试中使用这种问题。不过,我会准备一些引导性问题:
1.如何找到最大的?
1.你怎么知道一个数字是第二个?
这里是我可爱的解决方案(从@BrettDeWoody的答案中偷来的测试案例)。你可以使用标准的方法找到最大的数字,然后加上最小的数字。

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
huwehgph

huwehgph2#

我完全同意smac89的观点,作为一个工程招聘团队的成员和代码导师,我不喜欢面试问题中不切实际的限制。
不要问一个候选人在技术面试之外永远不会遇到的问题,而是提出一个与候选人将要从事的工作相关的具有挑战性的问题,并允许候选人展示他们对将要使用的语言和技能的了解。
举个很好的例子,一个朋友最近分享了一个前端面试问题--在时间限制内构建一个没有任何库的简单应用程序。
使用提供的API端点(使用?page=N查询参数返回分页结果),应用程序必须接受用户的搜索,检索所有结果(这可能涉及多个结果页面),按字母顺序对所有结果进行排序,并同时显示所有结果。fetchPromise(和Promise.all)、数组方法、事件侦听器和普通JavaScript DOM操作。
候选人可以查阅任何文档,并根据需要使用任何内置方法。时间限制允许有足够的时间完成,只要候选人对内置JS方法,Fetch API,Promises等有所了解。
IMO,一个近乎完美的面试问题(至少对于前端开发人员来说)。
我的2美分。
这是我对这个问题的解答

  • 使用ES 5
  • 不使用数组方法(除了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]));
u0sqgete

u0sqgete3#

在现实中,开发人员将采取阻力最小的路径。也就是说,他们将对数组进行排序,并采取倒数第二个元素。更少的代码要写,更少的思考。在我的书中获胜。
因此,你必须考虑的问题是,你是否希望开发人员能够记住如何从头开始正确地实现这个算法(可能有bug),或者那些可以重用已经存在的方法以在最短的时间内找到解决方案的人,几乎可以忽略不计的时间损失,并且大多数情况下没有bug。
我的意思是,你最后一次想要在数百万个元素的数组中找到第二大元素是什么时候?大多数开发人员可能会选择我最初描述的方法(排序并取第二大),如果发现代码是任何性能问题的瓶颈,那么将优化留给O(n)。

omtl5h9j

omtl5h9j4#

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语法
  • 混淆索引和值

因此,虽然不难,但有几个缓存很容易让候选人卡住,或者让他们感到困惑。

b5buobof

b5buobof5#

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]
bvn4nwqk

bvn4nwqk6#

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);
}

相关问题