0
\$\begingroup\$

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 //
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know JS, but if you are sorting the array and you have to find the nth minimum number, why not just return array[n-1]? \$\endgroup\$ – harshit54 Mar 19 at 8:39
  • \$\begingroup\$ Your code does not work. I dont know why your question has not been closed. You should fix it and ask for another review. \$\endgroup\$ – Blindman67 Mar 19 at 11:28
  • \$\begingroup\$ @Blindman67 Broken code isn't off-topic here, only code that the author knew was broken (at the time of posting), is off-topic. There is nothing in the post, that suggests that the author knew his code was wrong. \$\endgroup\$ – RoToRa Mar 19 at 14:16
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I disagree with your opening statement. Good code MUST FIRST be efficient. Ask the end users, the many who pay for the code to be written, which is better, code that takes 10seconds or code that takes 1second to run. -1 \$\endgroup\$ – Blindman67 Mar 19 at 11:26
  • 2
    \$\begingroup\$ I didn't phrase that well. Code doesn't need to be most efficient. One should prefer readable code over perfectly optimized code. I'm speaking of cases where inefficient, but readable code takes 1.1 seconds instead of 1 second to run. If it were not for the bugs, the original idea of sorting the complete array would be IMHO an acceptable solution. It may not the most efficient solution, but in 99% of all use cases a more efficient solution would be overkill. However the OP did imply that this would be a more efficient solution than to "just" look for the top 2 lowest values, which it isn't. \$\endgroup\$ – RoToRa Mar 19 at 14:05
  • 1
    \$\begingroup\$ -1 from that?! Gosh this place is hostile. +1 from me for that very same statement; the whole "computation time over developer time" was a thing of the 80s to my understanding, but these days we don't reuse variables for different things, nor use GOTO's, etc. \$\endgroup\$ – morbusg Mar 19 at 21:46
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Yea perhaps I didn't realize the inherent difficulty of finding a generalized solution for this problem, which is why I struggled for a bit. I'm going to definitely need to learn algorithms and data structures soon \$\endgroup\$ – DreamVision2017 Mar 20 at 23:14
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ You shared a really helpful advice on just solving the problem at hand. For the initial problem I was easily able to solve it without using sort functions or mutating my array. But I thought for some reason that they would appreciate it if I can find a more general solution. All in all, the advice you gave was pretty great and I'll study further. (I haven't touched on algorithms and complexity yet, so I will give it a try after I brush up on my programming a bit more). \$\endgroup\$ – DreamVision2017 Mar 20 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.