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