I applied online for the position in Google Sydney and then received an invitation a few days after.

After a short phone call with the recruiter, I proceeded to the technical phone interview.

Despite the interviewer's accent being difficult to understand, everything went well.

Given a frame with size MxN and a list of jigsaw puzzle pieces (1x1), each piece is represented as a tuple of 4 integer numbers: (A, B, C, D) with -100 <= A <= B <= C <= D <= 100.

Two pieces' edges can be matched together if their values are opposite numbers. The pieces can be rotated, e.g., (A, B, C, D) => (D, A, B, C).

Write a program to test whether the list of pieces can be fitted into the frame. If possible, then return useless pieces.

Input:

• M N
• A list of pieces

Output:

• The pieces can be fitted in or not.
• If can, return the list of useless pieces.

Expected complexity is O(n). No need for 100% accuracy; just cover as many cases as possible.