Interview Question Software Engineer / Developers
I dont get it...
Zombies cannot move directly from 1st lane to purchase lane? the initial condition is "The zombies are standing in the first waiting lane (ordered 1st to 10th)" why not just move one by one to the purchase lane or next lane? i think it definitely not the correct answer. did i miss anything here?
okay. added more info to the question.
You can only move zombie's from the front of the lane, the back of the lanes are closed. So if you move zombie3 to purchase lane then only zombies 1&2 can be moved to that lane because any other zombie greater than 3 cannot stand in front of zombie3.
Think of the lanes as a stack.
i am gonna give a wild guess here.
move 3~10 from 1st to 2nd lane. it takes 255 steps : sum(n)=sum(n-1)*2+1
move 1 and 2 from 1st lane to purchase lane in order : 3 steps.
move 5~10 from 2nd to 1st lane. it takes 63 steps
move 3 and 4 from 2nd lane to purchase lane in order: 3 steps.
move 7~10 from 1st lane to 2nd lane. it takes 15 steps.
move 5 and 6 from 1st lane to purchase lane in order: 3 stpes.
move 9~10 from 2nd to 1st lane. it takes 3 steps.
move 7 and 8 from 2nd lane to purchase lane in order: 3 stpes.
finally move 9 and 10 to purchase lane in order: 3 steps.
So, the total would be 351 steps.
Optimal number of moves for moving 10000 zombies from one lane to another lane in a 4-lane problem is :: 374931278650296101567069263458900577819295744
Optimal number of moves for moving 1000000 discs from one stack to another stack in a 1000-peg problem is :: 6000001.00
93 is the answer.
Aussme f(n) is the steps that we need, then
f(1) = 1
f(2) = 3
When n > 2
f(n) = f(n-2) + 1 + 1 + 1 + f(n-2) = 2*f(n-2) + 3
Ex:
When we need to move 10 zombies,
we can use f(8) steps to move zombie 1st to 8th to a waiting lane, then 1s tep to move zombie 9th to the another empty wating lane(it must be empty), after that 1 step move zombie 10th to purchase lane, 1 step to move zombie 9th to purchase lane, at last, f(n-2) steps to move 1st to 8th to purchase lane.
93 is the answer.
Aussme f(n) is the steps that we need, then
f(1) = 1
f(2) = 3
When n > 2
f(n) = f(n-2) + 1 + 1 + 1 + f(n-2) = 2*f(n-2) + 3
Ex:
When we need to move 10 zombies,
we can use f(8) steps to move zombie 1st to 8th to a waiting lane, then 1s tep to move zombie 9th to the another empty wating lane(it must be empty), after that 1 step move zombie 10th to purchase lane, 1 step to move zombie 9th to purchase lane, at last, f(n-2) steps to move 1st to 8th to purchase lane.
93...
- anonymous... October 27, 2010