HOME RUN of software engineer

general
1

i have team of 16 software engineers .named 1,2…16

if they are arranged in 4*4 matrix format s.e 1 will have home position of 0,0
s.e 2 will have home pos of 0,1 and so on

given a randomly arranged 4*4 matrix like
4 5 9 11
16 15 10 3
1 7 12 8
2 6 13 14

move 9 to its home pos .
constraints are-- 9 can be swaped with any of its horizontal or vertical neighbour only if sum of 9 and its neighbour = a prime no.
we have to output min no of swaps.
we can have random array input and no to be moved to its home position at run time from user.

this question was on my algo round during placement process of usigma.

i didnt came up with solution.
pls help me on this:)

2

Well sounds like a question that can be done by DFS(Depth first Search) .Just need to take care of the extra condition of prime sum.
Either visiting the neighbors turn wise you can check for the neighbors satisfying prime sum condition or you can calculated it for all case before processing the input.

So the summary is do a Depth first Search of the matrix where neighbours of value in (i,j) are (i-1,j) , (i+1,j) , (i,j-1) , (i,j+1) .

int  dfs(int i,int j)
{
int min=1000;
 if(i-1&&isprime(mat[i-1][j]+mat[i][j]))
  min=minimum(dfs(i-1,j),min);
.....so on for all the other neighbors
}
3 Likes
3

Out of the remaining 15 numbers there are 5 numbers {2,4,8,10,14} whose summation with 9 results in a prime number. So your answer is always less than 6. You can try a simple recursive solution for this question. Here is the algorithm:

 ::Function search (x,y):
   ->If 9 is at its original position(x,y = (2,1) ) return 0 else :
      ->For each number adjacent to 9, swap 9 with this number if the number belongs to the set {2,4,8,10,14}.
            ->Call this function again recursively after each swap with new position of 9    ex:- search(x+1, y) or search(x, y+1)
            ->If the function finds a path, compare it with existing minimum value for this path. Set minimum value appropriately.
             ->UNDO the swap and continue.
  ->return this minimum value to the calling function

You can also add the condition that path length explored should be less than 6 as there can be no more than 5 meaningful swaps.

1 Like