Amazon Interview Question
Software Engineer / Developerslet the jigsaw be represent by a linked list of nodes, where each node is a piece in the puzzle. note that the head of the list is not necessarily the top left piece in the puzzle.
another thing: i am assuming that the pieces would be square with top, left, right and bottom as four sides.
struct node
{
node* next;
node* top;
node* bottom;
node* right;
node* left;
}
initially the list is connected by the next pointers. when the player arranges the pieces, the top, bottom, left and right can be assigned accordingly. They can be left as null if they are corner pieces.
to find the top left piece in the puzzle, iterate using the next node, until u reach a node that has both top and left as null.
Why can't we simple consider a single or two dimensional array, where each slot holds a unique number?
In a situation when the jigsaw puzzle is solved, the array will be in a sorted manner.. For any move made, the value of two slots will be swapped..
Eg:
board[][] in unsolved condition:
5 7 3
6 9 4
2 8 1
play moves, a.k.a swap slots..
check if all are sorted or not, if not then puzzle isn't solved yet, if yes, then puzzle solved..
board[][] in ideal solved condition:
1 2 3
4 5 6
7 8 9
class Picture {
List<Piece> Pieces;
int noOfPiece;
void Picture(){
Pieces = new ArrayList<Pieces>();
}
void break(){
for(int i=0;i<noOfPiece;i++){
Pieces.add();
}
Collections.shuffle();
}
void merge(){
//Todo Merging logic to be written
}
}
class Pieces {
int topNo,LeftNo,RightNo,BottomNo;
void Pieces(int t,int l, int r, int b){
this.topNo=t;//
}
}
class Game {
Picture p = new Picture();
p.beak();
p.merge();
}
class Picture {
List<Piece> Pieces;
int noOfPiece;
void Picture(){
Pieces = new ArrayList<Pieces>();
}
void break(){
for(int i=0;i<noOfPiece;i++){
Pieces.add();
}
Collections.shuffle();
}
void merge(){
//Todo Merging logic to be written
}
}
class Pieces {
int topNo,LeftNo,RightNo,BottomNo;
Piece left,right,top,button;
void Pieces(int t,int l, int r, int b){
this.topNo=t;//
}
}
class Game {
Picture p = new Picture();
p.beak();
p.merge();
}
www careercup.com/question?id=1552
- anonymous March 11, 2012