## Atmel Interview Question

Applications Developers**Country:**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