I initially submitted my resume online for the position of Software Engineer at Google.

About two months later, I received a call from HR asking if I was still looking for a job and if I was interested in a position at Google. I said yes and listed a number of positions I was interested in: Research Scientist, Software Engineer, and User Design Scientist.

Two days after the call, I received an email stating that my resume would fit the position of Software Engineer and I was scheduled for a technical phone interview three days later.

The interviewer was nice and polite. I gave a first answer to the puzzle, but he wasn't really satisfied with the answer. I got stuck for 20 minutes and didn't get much help from the interviewer.

The interview lasted 45 minutes. I was given 10 minutes at the end to ask him questions about his job, life at Google, etc. Then he hung up the phone in a manner that let me know I wouldn't go through to the next step.

Two days after the interview, I received an email from HR stating that I was rejected.

The question was the following. I'm rephrasing it to make it clear for everyone to understand:

• You are going on a one-way flight trip that includes billions of layovers.
• You have one ticket for each part of your trip (i.e., if your trip is from city A to city C with a layover in city B, then you will have one flight ticket from city A to city B, and one flight ticket from city B to city C).
• Each layover is unique; you are not stopping twice in the same city.
• You forgot the original departure city.
• You forgot the final destination city.
• All the tickets you have are randomly sorted.

The questions are:

• Design an algorithm to reconstruct your trip with minimum complexity.
• How would you improve your algorithm?

Example:

Randomly sorted: New York -> London San Francisco -> Hong Kong Paris -> New York London -> San Francisco

Sorted: Paris -> New York New York -> London London -> San Francisco San Francisco -> Hong Kong