Interview Question
Country: United States
The minimum no of moves will be 2*pow(n,2) + 3*n. Where n is the no of monsters.
The sequence for AAAA_BBBB is: (_ is the empty space)
AAA_ABBBB
AAABA_BBB
AAABAB_BB
AAAB_BABB
AA_BABABB
A_ABABABB
ABA_ABABB
ABABA_ABB
ABABABA_B
ABABABAB_
A_ABABAB_
ABA_ABAB_
A_A_ABAB_
A_ABA_AB_
ABA_A_AB_
A_A_A_AB_
A_A_ABA__
A_ABA_A__
ABA_A_A__
A_A_A_A__
A_A_A__A_
A_A_A___A
A_A_A____
A_A__A___
A_A___A__
A_A____A_
A_A_____A
A_A______
A__A_____
A___A____
A____A___
A_____A__
A______A_
A_______A
A________
_A_______
__A______
___A_____
____A____
_____A___
______A__
_______A_
________A
AAAAA*BBBBB -> BBBBB*AAAAA
Use two different steps:
a) A moves to neighboring empty slot
b) B jumps over As to empty slot
Using these two steps, it takes N ( where N is the number of monsters of one type ) plus 1 steps to move one B to its final place:
AAAA*ABBBBB (step a)
AAA*AABBBBB (step a)
AA*AAABBBBB (step a)
A*AAAABBBBB (step a)
*AAAAABBBBB (step a)
BAAAAA*BBBB (step b)
You have to do this process for each B, so it is N*(N+1) steps. Finally you have to move each A to its final position using step a. Overall the whole thing will take N*(N+2) steps.
Can you please explain the question again. Both A and B can jump over the other type. What does it mean.
21
Firstly jump one monster to middle ,then we have blank space on one side jump one monster from other side then we got blank space on other side ,similarly follow this hence we always will get steps=2*(number of monsters) + 1
AAAA*BBBB
AAA*ABBBB
AAABA*BBB
AAAB*ABBB
AAABBA*BB
AAABBAB*B
AAABB*BAB
AAABBB*AB
AAABBB*AB
AAABBBBA*
It seems that there is only one monster can get through the road. The number of steps is 2 * n(monsters) + 1.
The Question did asked how to let "them" get through.
Have I missed something important in the question?
n + n/2;where n is total number of monster. here i am assuming 10 A monster and 10 B monster. so h is 20
for example :
6(n) steps from here to
AAA*BBB
AA*ABBB
AABA*BB
A*BAABB
ABBAA*B
*BBAAAB
BBBAAA*
here
now 3(n/2) steps from here to
BBBAA*A
BBBA*AA
BBB*AAA
here
so total is 3*n/2;
and here there is no backward motion, as A is moving forward only, and B is also moving forward only.
I think the answer is n(n+2),n is the number of monster A or B, which is the same. T he steps begin with A move B jump, then B move A jump 2times ....till A move B jump n times.The line will be like BABABA...BA*,then A move,B jump n-1 times...till A move B jump 1 time. The line will be BBB...BA*A...AA. Then A move. The step number is (1+1)+...(1+n-1)+(1+n)+(1+n-1)+...(1+1)+1=n(n+2).
For monster A and B to swap places it will take 3 jumps.
- DashDash March 13, 2013First A will jump to empty slot
Then B will jump to vacated A space and then A will jump from empty slot to B
Therefore I think min jumps will be 30 ?
Please correct me if I am wrong.