Plug topics

Dave Smith dave at thesmithfam.org
Tue Jun 11 21:49:21 MDT 2013


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


More information about the PLUG mailing list