According to the hint, I tried my version with the build-in sort()
and get a one time AC. But if in a real interview scenario, do we allow to use build-in sort to solve this problem?
What would the actual point the interviewee might look for?
Well, if I was to interview someone and asked this question, my logic would be something like this. If the candidate can do it using sort()
, it's a good sign anyway, so it gives a positive point. The next thing I'd ask is what the complexity of the solution. If the candidate says it's O(N), that would be a huge negative point that would turned the score to negative, and at that point I'd probably decide that we don't want such an employee. If the candidate can't answer that because they don't know what complexity sort()
is, but don't make any wrong assumptions, that's still a negative point, but not that bad.
If the candidate gives the right answer, then I'd ask about possible ways to improve the complexity. Can it be done in linear time? Can it be done with no extra space? Can we get both? And I listen to their ideas. Possible reactions that may come up:
And of course, if they instantly come up with an O(N) time O(1) space solution, I'd become real suspicious. A good programmer can come up with one all right, but hardly instantly.
In the end, what matters is the right logic and the ability to implement that logic, no matter whether they can actually complete it during the interview or not.
Oh, and a good follow-up question is: is it possible that there are more than one valid value for h? This problem hints that it is, but the correct answer that it isn't.
P. S. Not that I have ever really interviewed someone, but I have more than 10 years of real job experience and I saw many different programmers, so I feel like I know what to look for.