On Jun 11, 2013, at 12:05 PM, Sasha Pachev wrote:
> Part 1 - easy, you frequently see this in job interviews. Maybe not anymore
> because everybody knows it. You have a list of N unordered elements that
> contains unique numbers from 1 to N+1 with one missing. Using the amount of
> RAM that will be the same regardless of N can you find the missing number
> in one pass? Hint if you need one - remember how Gauss annoyed his math
> teacher.
I've not actually seen this challenge, and I have refused googling it. So here
goes:
Here's a python solution for part 1 with py.test unit tests (I really like
py.test):
def find_missing(haystack):
n = len(haystack) + 1
expected_sum = n * (n + 1) / 2
return expected_sum - sum(haystack)
def _generate_test_list(n, missing):
from random import shuffle
test_list = range(1, n+1)
test_list.remove(missing)
shuffle(test_list)
return test_list
def test_find_missing():
test_list = _generate_test_list(n=100, missing=42)
assert find_missing(test_list) == 42
def test_find_missing_on_large_list():
test_list = _generate_test_list(n=10000000, missing=42)
assert find_missing(test_list) == 42
> Part 2 - harder - can you do this if two numbers are missing? Is your
> solution robust enough to avoid register overflow? Can you do it without
> resorting to BigInt arithmetic?
Still thinking about this one. Runtime was not given as a constraint. I suppose
I could simply sort the list and look for holes. Would that violate the
constraints of the challenge?
I suppose you are fishing for a checksum or lookup table style algorithm. Still
thinking about those approaches.
--Dave
/*
PLUG: http://plug.org, #utah on irc.freenode.net
Unsubscribe: http://plug.org/mailman/options/plug
Don't fear the penguin.
*/
