Coding round, online interview, and HR round.

Round 2 (Technical Interview):

This interview started with a brief introduction of myself and then quickly jumped to the discussion of the different projects I had done. It was a 10-minute discussion.

As my project was based on cloud computing, the following project-specific questions were asked:

• Which hypervisor did you use?
• How does VirtualBox work? What kind of virtualization is there?
• Why didn’t you use OVAs? Why did you implement the infrastructure from scratch?
• What is an ISO file?

Then, the interviewer gave me an easy recursion/loop question. The question was to print a pattern based on an integer.

Johnny has some difficulty memorizing the small prime numbers. His computer science teacher has asked him to play with the following puzzle game frequently.

The puzzle is a 3x3 board consisting of numbers from 1 to 9. The objective is to swap the tiles until the following final state is reached:

1 2 3 4 5 6 7 8 9

At each step, Johnny may swap two adjacent tiles if their sum is a prime number. Two tiles are considered adjacent if they have a common edge.

Help Johnny find the shortest number of steps needed to reach the goal state.

Input The first line contains t, the number of test cases (about 50). Then t test cases follow. Each test case consists of a 3x3 table describing a puzzle that Johnny would like to solve.

The input data for successive test cases is separated by a blank line.

Output For each test case, print a single line containing the shortest number of steps needed to solve the corresponding puzzle. If there is no way to reach the final state, print -1.

Example Input: 2

7 3 2 4 1 5 6 8 9

9 8 5 2 4 1 3 7 6

Output: 6 -1

Output details The possible 6 steps in the first test case are described in the following figure: