Test employee interview puzzle

findnum.py

from random import randint
from time import time
N_SOLS = 1
def binary_search(min, max):
    n_bins = 0
    while min <= max:
        mid = (min + max) // 2
        n_bins += 1
        if mid < NUM:
            min = mid + 1
        elif mid > NUM:
            max = mid - 1
        else:
            print n_bins
            return mid
def find_number(growth_func):
    guess = 2
    n_grows = 0
    while True:
        if guess < NUM:
            guess = growth_func(guess)
            n_grows += 1
        else:
            print n_grows
            return binary_search(0, NUM)
NUM = randint(0, 2**(2**20))
for func in [lambda x: 2*x, lambda x: x**2, lambda x: x**10, lambda x: x**x]:
    start = time()
    for x in range(N_SOLS):
        n = find_number(func)
        assert n == NUM
        print '%.2f seconds to find %d solutions.' % (time() - start, N_SOLS)