5 ms·

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

by zem 10y ago

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.

djamrozik 10y ago
For those curious about the best solution (like myself): http://www.geeksforgeeks.org/find-the-missing-number/ http://www.geeksforgeeks.org/find-the-missing-number/
OJFord 10y ago
Strict requirements (like linear and constant) give so much away about the nature of the solution. "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.
- zem 10y ago
  yeah, i was paraphrasing a bit. how the actual interview went was i was asked to simply find the missing number, i came up with the log space solution pretty quickly, the interviewer then asked if i could do better than that, and it took me a bit of thinking to come up with the constant space answer.
api_or_ipa 10y ago
I really enjoyed solving that. It didn't take very long at all (but was very satisfying!). It reminds me of an old story (of which I can't verify) about Gauss while in school solving a summation using a very neat observation. Enough said!
deleted 10y ago
[deleted]
logicallee 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. 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.

by zem 10y ago

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.

djamrozik 10y ago

For those curious about the best solution (like myself): http://www.geeksforgeeks.org/find-the-missing-number/ http://www.geeksforgeeks.org/find-the-missing-number/

OJFord 10y ago

Strict requirements (like linear and constant) give so much away about the nature of the solution. "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.

zem 10y ago
yeah, i was paraphrasing a bit. how the actual interview went was i was asked to simply find the missing number, i came up with the log space solution pretty quickly, the interviewer then asked if i could do better than that, and it took me a bit of thinking to come up with the constant space answer.

api_or_ipa 10y ago

I really enjoyed solving that. It didn't take very long at all (but was very satisfying!). It reminds me of an old story (of which I can't verify) about Gauss while in school solving a summation using a very neat observation. Enough said!

deleted 10y ago

[deleted]

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