Interview Question
Country: United States
def find(cities, n):
memo = {}
def helper(cs, n):
if len(cs) == n:
return 1
tcs = tuple (cs)
if tcs in memo:
return memo.get(tcs)
z = [cs[0]-2]+cs+[cs[-1]+2]
ans = 0
for i,(a,b) in enumerate(zip(z,z[1:])):
if 0<a+1<b<n+2:
ans += helper(cs[:i]+[a+1]+cs[i:], n)
if 0<a<b-2:
ans += helper(cs[:i]+[b-1]+cs[i:], n)
memo[tcs] = ans
return ans
return helper(sorted(cities), n) % (10**9+7)
print find([2,5],5)
- adr November 08, 2018