ThoughtWorks Interview Question
Senior Software Development EngineersCountry: India
Interview Type: Phone Interview
arr = [2,4,8,16,32,1,100007]
l = len(arr)
def memoize(f):
cache = dict()
def fn(*args):
if args in cache:
return cache[args]
else:
rv = f(*args)
cache[args] = rv
return rv
return fn
@memoize
def count(start, rungcd=None, runmax=0):
rv = 0
for nxt in range(start, l):
if arr[nxt] > runmax:
rv += count(nxt+1, gcd(rungcd, arr[nxt]), arr[nxt])
if rungcd == 1:
rv += 1
return rv
def gcd(a,b):
if a == None or a == 0:
return b
if b == None or b == 0:
return a
return gcd(max(a,b)%min(a,b), min(a,b))
count(0)
The examples dont seem to be correct? eg. 1,2,3 can have [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] so 7 in total
- Anonymous June 27, 2016