Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

How about treating all the pieces of jigsaw as polygons?

Write 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.

}
}
}

- Vimal May 03, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

try 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.

- Anonymous May 30, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous September 14, 2007 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- vanmiestro March 15, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- crazyboy March 16, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can't think of an efficient way to do this. Any ideas?

- Khoa December 14, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one way would be using an adjacency list graph.

- khoa December 14, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

not sure.. but comparing each piece with every other will be O(n**2 ), so maybe we can group them in 2's first and then merge them recursively......Gayle, any inputs?

- vatson December 21, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
}

- Gayle L McDowell December 22, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you comment on how you would go about solving the problem of minimizing the number of calls to the function???

- Ram September 20, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- truthcreator February 18, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please elaborate your solution.

- Noname January 06, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Ryan May 01, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you look at this problem for example at the first step; you have about O(n!) choices to break this problem into 2 sub problems, Image all the permutations in each sub problem. Which means DP is not the solution to this problem as it cant be solved in poly time.

- Noname July 04, 2007 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Dhwani June 25, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Divide-and-Conquer may work.
Divide the pieces into left and right parts (or up and down parts), and continue the process.
O(nlogn)

- brucesea January 05, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider Jigsaw puzzle have 100 parts and each part is defined as polygon, create a structure having each side with flag associated with it. Each parts side must have address of the associated other part and it should be unique. If match is found set the flag.

- phoenix August 21, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is similar to a map colouring problem. Here the jig-saw pieces for a set. We need to visualise the entire structure as a graph. then we can use DFS and backtracking mechanism to find the solution to the jig saw puzzle.

- Anonymous March 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This problem is similar to a map colouring problem. Here the jig-saw pieces for a set. We need to visualise the entire structure as a graph. then we can use DFS and backtracking mechanism to find the solution to the jig saw puzzle.

- nayak_khalnaya March 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't we use 2d linked list for this problem....
where each piece will have the address of the targeted piece and also the targeted piece will have the address of piece.........

- Anonymous May 15, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we take the puzzle as a graph, then what we want is to find a Hamiltonian cycle, which is NP-complete, i.e. no polynomial time solution exists.

- chaos January 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Of course the Hamiltonian cycle is the optimal case, where each piece is visited once.

To let a program solve the puzzle, I would use a hashtable, following the divide and conquer tactic.

- chaos January 26, 2010 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More