5 ms·

"All the integers between 1 and n should add up to (n(n+1) / 2) so just iterate over the array keeping a running sum, then at the end subtract from (n(n+1) / 2)

"All the integers between 1 and n should add up to (n(n+1) / 2) so just iterate over the array keeping a running sum, then at the end subtract from (n(n+1) / 2) to see the integer you are missing. It's constant space and requires just a single sum you track. 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.)

AnimalMuppet 10y ago
If I were looking for a junior dev, probably not. Don't like your attitude, son, and you're probably not a good fit. 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...
- logicallee 10y ago
  thanks :)
zem 10y ago
> All the integers between 1 and n should add up to (n(n+1) / 2) so just iterate over the array keeping a running sum, then at the end subtract from (n(n+1) / 2) to see the integer you are missing. It's constant space and requires just a single sum you track. 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.
- logicallee 10y ago
  Well, if you don't want to overflow then rather than summing all the numbers first and subtracting a single time from (n(n+1) / 2) at the end, you can subtract numbers one at a time from 1..n and end up with the same result. In order to make sure you don't overflow you have to tend toward zero, subtracting large numbers when your running sum gets large and small ones when it's small. Here, I coded this for you - http://codepad.org/kdqoLXFA 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.
  - zem 10y ago
    yeah, the bitwise xor was my next solution, and what the interviewer was looking for. i found it a fun puzzle, satisfying to solve and not really brittle at all (why would you feel it was? it's just a simple loop with an xored accumulator; it cannot overflow or do anything funny). i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)

AnimalMuppet 10y ago

If I were looking for a junior dev, probably not. Don't like your attitude, son, and you're probably not a good fit. 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...

logicallee 10y ago
thanks :)

zem 10y ago

> All the integers between 1 and n should add up to (n(n+1) / 2) so just iterate over the array keeping a running sum, then at the end subtract from (n(n+1) / 2) to see the integer you are missing. It's constant space and requires just a single sum you track. 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.

logicallee 10y ago
Well, if you don't want to overflow then rather than summing all the numbers first and subtracting a single time from (n(n+1) / 2) at the end, you can subtract numbers one at a time from 1..n and end up with the same result. In order to make sure you don't overflow you have to tend toward zero, subtracting large numbers when your running sum gets large and small ones when it's small. Here, I coded this for you - http://codepad.org/kdqoLXFA 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.
- zem 10y ago
  yeah, the bitwise xor was my next solution, and what the interviewer was looking for. i found it a fun puzzle, satisfying to solve and not really brittle at all (why would you feel it was? it's just a simple loop with an xored accumulator; it cannot overflow or do anything funny). i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)