one i really enjoyed solving: given an array of size (n - 1), containing all but one of the numbers between 1 and n, find the missing number in linear time and constant space.
But hey you know what, actually, fuck these requirements, they're pretty bad.
This is a stupid and wrong solution and the actual correct way to do it (which is guaranteed to work) is to sort the list in-place (or into a copy, if you need the original), then iterate through from the beginning, making sure it starts with one, that every value is in there, and that it is missing one and only one number. On the second missing number or if after sorting it does not start with 1, or if any value is not an integer, or if any value is repeated, then say that the array does not meet the promises, and you can even error with the exact way in which it fails. This is much better and in-place sort is pretty fast. Quicksort, which I will use, requires pointers and is not actually constant space (despite being an in-space sort) but because it's better and we should use it.
So, with all due respect, fuck the requirements, that is going to be our solution. I realize it misses both your linear time and constant space requirements, but I really feel these requirements are stupid and lead to a brittle solution - this solution is better and is the one I stand by. Sorry. :)"
How'd I do? Would I get the job? (Probably NOT.)
But if I'm looking for a senior position, you're probably in. Senior people do push back on bad requirements, and they know when to do so, and why. If I want experience and leadership, what you did is exactly what I'm looking for.
The difference is that the senior person is going to do it when they know that the spec is a bad idea (and know why it's a bad idea), and the junior person is going to do it all the time because they're a show-off know-it-all and a hothead...
that was my first answer. the interviewer pointed out that even if n fit within an int, there was no guarantee that n^2 would. my immediate second thought was to multiply every even number by -1, but i realised that you could always provide an input that would make that overflow too.
Here, I coded this for you - http://codepad.org/kdqoLXFA (scroll down for the output! it's not just a pastebin but runs it for you). As you can see my code contains tests at the end to show it's working, but not a robust testing class because it's a brittle piece of shit. I don't even want to know what it would do with input that doesn't meet its promises.
I also Googled this and an alternative (that admittedly I did not think of) given such tight restraints is to keep a running bitwise xor of your elements, and also bitwise xor'ing in (1..n) similar to the above - then you don't need to do it from a head and a tail, at the end rather than a difference you just end up with the missing number. This is probably superior to what I just coded.
But both algorithms are really stupid and really brittle. Sorting is fast and there is no reason not to do it that way.
i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)
With the xor solution, on the other hand, you don't really have that option -- if the input does not exactly match the input condition, then it WILL return whatever - with no indication that anything is amiss. Even slightly wrong input will give unpredictable, completely wrong output with no indication that anything is wrong.
What's worse is that it's trivial to game: as an exercise try making a malicious generator that takes an n of at least 4 and Target number, and returns (generates) an array (of size n-1) for feeding the XOR solution that shall get the xor solution to output the Target as the missing number. Further, the malicious generator, instead of generating an array with one missing number, actually shall generate a list which is as close to correct as possible, except that it shall (as an extra 'fuck you') in all cases contain the "Target" value -- twice.
btw thanks for the feedback on the sum thing :)
"What's the best you can do within ..." adds an extra challenge - in particular I don't think I'd often see the constant space solution as perhaps one in logspace.
Enough said!