Hiring the Smartest People in the World

Post by drostie » Wed, May 02, 2012, 11:49 AM UTC

nabb wrote: post #36

alexchamberlain wrote: post #3

A quick Google will find you the answer to the first question. The second just requires an additional equation, where people are suggesting powers in finite groups. This seems rather complex. Can we not reach the same constraints by only summing the even numbers, for instance?

An easy way to do the second is to consider the sum and the sum of squares. This gets you a-b and a^2-b^2. Recall that the latter is (a-b)(a+b) and the answer follows immediately.

    >>> from random import shuffle
    >>> def test(n, missing, extra):
    ...     t = [i if i != missing else extra for i in range(1, n + 1)]
    ...     shuffle(t)
    ...     return t
    ...
    >>> def solve(list):
    ...     diff, diffsq, n = 0, 0, 1
    ...     for i in list:
    ...         diff += i - n
    ...         diffsq += i*i - n*n
    ...         n += 1
    ...     sum = diffsq / diff
    ...     return {'extra': (sum + diff)/2, 'missing': (sum - diff)/2}
    ...
    >>> solve(test(7633507, missing=3518688, extra=4057456))
    {'missing': 3518688L, 'extra': 4057456L}

Post by alexchamberlain » Wed, May 02, 2012, 11:54 AM UTC

drostie wrote: post #44

cncool wrote: post #37

Earlier quoted context omitted.

1. How is this not linear time?

Because as the numbers increase, their storage requirement also increases. Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number. Give…

Post by 6ren » Wed, May 02, 2012, 11:59 AM UTC

zheng wrote: post #10

6ren wrote: post #9

For the first one, if they are in an order, and in an array, you can do a binary search, O(log2 n) time - better than linear time. Perhaps the question was misstated. Also, the friend's relationship is accidentally disclosed as a son.

The problem wasn't misstated, when they aren't in order the solution isn't obvious unless you remember a bit about sums. Most interview problems, if restricted, can either be solved very quickly, or aren't interesting anymore. Either way, as it was stated, it's a fairly common interview question as another comment has pointed out.

Post by JoachimSchipper » Wed, May 02, 2012, 12:04 PM UTC

alexchamberlain wrote: post #54

drostie wrote: post #44

Earlier quoted context omitted.

Because as the numbers increase, their storage requirement also increases. Suppose you have the array [1, 2, 3, ..., n]. How does storage of that array scale? You need log(n) bits to store the largest element and you need about n elements of that size (at the very least the last n/2 will have the last bit set) -- so you are operating on a data source which has size O(n log n). At least, if n is the above number. Give…

I disagree. The array is stored outside of your algorithm. The algorithm is constant space.

Post by ckuehne » Wed, May 02, 2012, 12:34 PM UTC

ckuehne wrote: post #34

I very much doubt that the OP can solve either problem 1 or problem 2 with constant space. Hint: even storing an additional integer N requires \Omega(log(N)) space. Edit: For the down voter: I searched around and found a discussion of the puzzle [1]. Please go ahead and read it. [1] http://books.google.de/books?id=415loiMd_c0C&lpg=PP1&#38...