Finding nth lowest value without any Math max or min methods

Question

So I decided to make a more efficient solution to a Google interview question where they ask you to either find the lowest or second lowest value in an array without using the max or min methods. I believe it is more efficient because you can use my method to find any nth lowest value in the array so it solves for all cases.

Please let me know if there is anything I can do to improve this solution or if there is anything I am missing:

/*Algorithm:
-first sort the array from ascending order
-Then iterate over the array with a loop
-if(array[i + nth lowest input you want])
-return the output

function nThOrderStatistic(array, number):
 -if you want to find the lowest number sub in 0 for number 
 -for every nth lowest number you would sub in n - 1 for the number */


function nThOrderStatistic(array, number) {
  array.sort(function(a,b){return a -b});
  for(i = 0; i < array.length; i++)
  {
    if(array[i + number] < array[i + (number + 1)])
  {
     return array[i + number];
    }
  }
}

nThOrderStatistic([6,7,43,2,95], 2);

//sample output for 3rd lowest value is: 7 //

Answer 1

Good code primary doesn't need to be the most efficient, it needs to be readable, so you should make sure it is correctly formated and indented.

---

More importantly it needs to be correct. Here are some examples of wrong results:

nThOrderStatistic([6,7,43,2,95], 4); // Expected result: 95, returns undefined

nThOrderStatistic([1], 0); // Expected result: 1, returns undefined

nThOrderStatistic([1, 1, 2], 1); // Expected result: 2, returns 1.

---

It's not really "more" efficient either. Sorting the array is much more inefficient, than directly looking for the nth lowest element in it (or than just looking for the two lowest elements).

---

And finally, it's bad form of a function like this one to unexpectedly modify its input (in this case sort the given array).

Answer 2

I decided to make a more efficient solution to a Google interview question

The purpose of such interview questions is to get signal as to whether you understand asymptotic efficiency or not; your answer indicates you do not. It will also be looking for signal as to whether you understand the asymptotic performance characteristics of various data structures.

sort is O(n lg n) time complexity in the typical case, but max and min can be implemented in O(n) time complexity; whether you can recognize that or not, and write the code accordingly, is the test.

I believe it is more efficient because you can use my method to find any nth lowest value in the array so it solves for all cases.

That's not the sort of "efficiency" they're looking for. The question they're asking is not "can you solve a more general problem, and therefore be more efficient in terms of lines of code written per problem solved?" The question they are asking is "can you find the algorithm that makes more efficient use of machine resources?".

If you wanted to use this solution in a Google-style interview and impress the interviewers, what you need to do is to make the argument that your sorting solution is more efficient in terms of amortized costs.

Exercise: under what circumstances is the amortized cost of the "least n" query on an arbitrary unsorted array lower if you spend the time sorting the array once?

Please let me know if there is anything I can do to improve this solution

Google-style interviewers will be looking primarily for signal as to whether you can write correct code, and provide test cases and logical arguments that demonstrate its correctness. Summing up:

• You haven't found a correct solution.
• You haven't made any argument for correctness.
• You have provided a single test case.
• You haven't found the asymptotically efficient solution.

This would be an easy "no hire" for a Google interviewer.

So, this gives you some things to concentrate on:

• Solve the problem that was posed; if you feel the need to solve a more general problem, say why.
• Have a good working understanding of asymptotic performance; I do not expect candidates to be able to rattle off the Master Theorem (I have had a grand total of one candidate in 20 years do so, and they did it wrong) but I do expect candidates to be able to tell me if an algorithm is sublinear, linear, superlinear, quadratic, exponential, and so on.
• Follow good coding practices: don't mutate your inputs, for example.
• Create a correct solution.
• Make a cogent, clear, correct argument that explains why your solution is correct.
• Provide test cases that convince the interviewer that you've thought about ways your algorithm could go wrong.

Answer 3

efficient solution to a Google interview question where they ask you to either find the lowest or second lowest value in an array without using the max or min methods.

If the question is to find the lowest or second lowest value, then sorting (log-linear) will be very inefficient compared to making one or two passes (linear) to find the two numbers.

The generalized version of the task to find the k-th lowest number, is not a small detail and not to be underestimated. Sorting the entire array is still going to be quite inefficient. Consider an alternative approach, using a max-heap:

• If k is larger than the number of elements, then raise an exception or return undefined.
• Add the first k elements to a max-heap.
• For each remaining element:
  • If the value is equal or greater than the top of the heap, ignore it
  • Otherwise add the value to the heap, and remove the top

In the end, the top of the heap is the k-the lowest value.