Atmel Interview Question
Applications DevelopersCountry: India
Interview Type: In-Person
Definite Approach:
1. Start with 1,3.
2. Maximum number accessible with above numbers is 1+3=4.
3. Next number to be accessed 5. Max number until now is 4.
4. Next number is 5+4=9
5. Numbers are 1,3,9. Repeat steps 2,3,4.
Example- Max number accessible=1+3+9=13. Next number to be accessed is 14.
Next number is 13+14=27...
Numbers are 1,3,9,27.
Using stacks to process decision trees
def find4():
stack = [ [] ]
while len(stack):
nums = stack.pop()
if len(nums)<4:
start = 1
end = 36
if len(nums):
start = nums[-1] + 1
end = end + len(nums)
stack.extend([ nums + [x] for x in range(start,end+1) ])
continue
# verifying
reached = [ 0 ] * 41
total = 0
options = [{'sofar': []}]
while len(options):
decisions = options.pop()
sofar = decisions['sofar']
level = len(sofar)
if 'next' in decisions:
level = level + 1
sofar.append(decisions['next'])
if level<4:
options.append({'sofar': sofar[:], 'next':nums[level]})
options.append({'sofar': sofar[:], 'next':0})
options.append({'sofar': sofar[:], 'next':-nums[level]})
s = sum(sofar)
if s>0 and s<=40 and not reached[s]:
total = total + 1
reached[s]=1
if total>=40:
return nums
break
print find4()
1,3,9,27
- anonymous October 01, 2014