Amazon Interview Question
Software Engineer / Developerstry to use a multi-dimensional arrays to hold the elements as original puzzle copy.
shuffle the elements into a map or any collection, to solve the puzzle, just map the elements in map with the elements in the arrays.
Seems similar to what I came up with. I was thinking we could take the original picture and organise a grid that divided it into smaller parts(of some size that is quite small). Now for each piece that forms a part of the jigsaw, assign a number. In the original arrangement of the pieces, find out the number of the piece that comes above each square of the grid. Store these values for each square.
To play : when the user puts a piece on the grid, the underlying squares get the value of the number of the piece. Keep doing this. If the player is able to come up with the same arrangment as the original, he wins.
To solve the puzzle : Simply arrange each piece according to the numbering of the grid.
Using an adjacency matrix would take a lot of space because it would very sparse for large jigsaw puzzle. Here's another approach.
Assume the jigsaw puzzle is n x m pieces (say n horizontal, m vertical, although orientation does not matter here.) Define a piece data structure similiar to what someone suggested above:
typedef struct
{
int jigsawId; // some ID to uniquely identify this piece.
int neighborCount;
JigsawPiece *neighborPieces
} JigsawPiece;
Further assumption is that jigsaw fits together much like a grid with following properties (called groups A, B, and C):
(A) 4 JigsawPieces have only 2 neighbors. They would be the four corner pieces of the jigsaw puzzle.
(B) 2*(n-2)+2*(m-2) JigsawPieces have only 3 neighbors. They would be the pieces along the edges of the jigsaw puzzle, excluding the actual corners.
(C) (n-2)*(m-2) JigsawPieces have exactly 4 neighbors. They would be the inner (n-2) x (m-2) pieces excluding outermost edges and corners.
A-B-B-B-B-A
B-C-C-C-C-B
B-C-C-C-C-B
B-C-C-C-C-B
B-C-C-C-C-B
A-B-B-B-B-A
The algorithm to solve the jigsaw puzzle:
1. For each piece, iterate through remaining pieces and call function to identify neighbors. Assume some function, such as:
boolean FitsTogether(JigsawPiece *jp1, JigsawPiece *jp2)
This would be called (N*M-1) + (N*M-2) + ... + 3 + 2 + 1 = (N*M-1)*(N*M)/2. If K=N*M then this involves (K-1)*K/2 = O(K^2) comparisons. In practice we can skip over jigsaw pieces that have already fit at most 4 times as they won't fit with any more. This means the # of comparisons will be much less.
Once this is done, we have jig saw pieces in groups A,B, and C from above. Pick a piece from group A and walk along its neighbors in group B. Each piece in group B will be neighbor to one piece in group C and others in group A or B. When you encounter piece in group A, you have a row of the original jigsaw.
i.e. A-B-B-B-B-A
From this you can identify the next row of the jigsaw puzzle by excluding pieces already examined going row-wise.
if we use a data structure that hashes all the edges of the jigsaw puzzle that match each time by using the same hashfunction then we can know that if a edge of a jigsaw puzzle is hashed using the function then it would be a part of the solution to the puzzle in that way the complexity will be only o(n).pls let me know if this approach will hold good
First, let's talk about the data structures. What about something like this:
struct Edge
{
//assume that this represents the shape of the edge
//if this array is empty, then it's an edge
Point[] points;
//the parent piece
Piece* parent;
}
struct Piece
{
Edge top;
Edge left;
Edge right;
Edge bottom;
}
bool EdgesFit(Edge edge1, Edge edge2)
{
//computes if the two edges fit together
//Note that this takes in the actual edges, not the pieces
}
to clearfy the question : do not use simple graph data structurewith one piece only have more than four neighbors!
With a deep thought, the method can be minimize to be called by (n-1)+(n-2)+...+2+1, then the time complex should be O(n*n),actually the worst case is less than n*n.
The solution is use graph with a relation flag for each two pairs. The relation flag is used to record each time comparsion by calling the method.
If with this flag to memorize the comparson result, the worst case for calling the method would be 1(n-1)+2(n-2)+3(n-3)+……+(n-1)1 = (n^3-n)/6
This sounds like a dynammic programming problem. With jigsaw pieces, they can have odd shapes. I see a previous post limiting them to have 4 neighbors.
You could essentially build an undirected graph. I think it would still be O(n^2).
I would proceed by using an adjacency martix for the pieces(as am not sure of how many neighbors can be there)
Then would try to grup starting with boundary---> this would reduce the comparisions for the start.
Then, club the obvious portions of the jigsaw together, like pieces of a structure like a mountain, animal, etc.
There would be some ambiguous ones which I can keep togeher. Start with using the 'function' on the groups first and the ambiguous ones.
Would this be a better solution or would have to iterate through all the pieces without visual clues?
How about treating all the pieces of jigsaw as polygons?
- Vimal May 03, 2007Write a function to Combine the polygons which are neighbors of each other.
At the end of program we will have only one polygon and the jigsaw will be solved.
The structure of the jigsaw can be
typedef struct
{
int x;
int y;
}Point;
typedef struct
{
int no_of_vertices;
Point *vertices;
}Polygon;
typedef struct
{
int num_pieces;
Polygon * pieces;
}JigSaw;
the O(n^2) algo can be
main()
{
//Initalise the jigsaw here.
Jigsaw Jig;
while(Jig.num_pieces != 1)
{
Polygon first = Jig.pieces[0];
for(int i=1;i<n;i++)
{
if(AreNeighbors(Jig.pieces[i],Jig.pieces[0])
{
Combine(Jig.pieces[i],Jig.pieces[0],&Jig);
//Combine function will combine the two polygons
//It will also remove the Jig.piece[i] from Jig and
//reduce num_pieces by 1.
// We can use convx hull algo to combine the two polygons.
}
}
}