I would like to submit the following question I was asked
recently during my technical interview at Google.
I'm rephrasing the question to make it clear for everyone
to understand:
- You are going on a one-way flight trip that includes
billions of layovers.
- You have 1 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 1 flight ticket from city A to city
B, and 1 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.
Question 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
- 3 Answers
- 5307 Views
- Google, I also Faced
- E-Mail Answers
Answer Posted / raghvendra
1) Assuming the data in 2 dim array. (2 Columns: FROM
destination & TO destination)
2) Sort the array (any standard sorting logic) using column
1 i.e. FROM destination.
3) Take "TO" destination value of row 1 and use binary
search to search its match in "FROM" destination column
from row 2 to n
If match found, adjust that row as row 2. (Swap
pointers in place of physical data)
Take "TO" destination value of row 2 and
use binary search to search its match in "FROM" destination
column from row 3 to n
continue this logic till as long as a match
is found.
if match not found.
Resort the remaining unadjusted rows
using "TO destination" column.
Take "From" destination value of
row 1 and use binary search to search its match in "To"
column in all unadjusted rows.
Match must be found otherwise data
incorrect. adjust that row as row -1. (Swap pointers in
place of physical data)
Continue this till end of the
array.
Now you have the sorted list.
I am sure there can better ways to achieve the same.
| Is This Answer Correct ? | 3 Yes | 0 No |
Post New Answer View All Answers
Why is packaging and distribution important?
What was the architecture or design of your last project? what were the pros and cons of the design?did it scale well?
Write a command to find all of the files which have been accessed within the last 30 days. Output should be stored in a file “December.files”
Ford Software engineer interview process and model questions
One of our potential future investors ask us for following: "We also wanted to see the high level algorithm diagrams". I have searched the Web a lot and have found a lot of types of diagrams. I will not list them here. I'm not sure that the definition "high level algorithm diagrams" exists at all. Any way, if you know it is - where I can find it on Web. The more general question. If one need to create (let us define it this way) high level algorithm diagrams - where to find types, descriptions and templates on Web. Thanks a lot. Valery
If Web site developer want to evaluate their current authoring tool, where would they start?
Can you explain why software is called a product?
What is the role of the W3C in Web accessibility?
What is "System framework" layer in multiple layer programming? (5 layer: UI, Business, Data, Common, "System framework" are layers in this design)
What is Make to Order, and what is the difference between Make to order and Make to Cash
What, if anything, is the difference between "executing" a processing instructions and "processing" a processing instruction? Are the terms "executing" and "processing" interchangeable?
what are the stages of software system engineering process?
what stage/s of the development lifecycle should end users be involved?
Discuss operations of CAD and CAM system.
What are the Rules of Desktop Publishing?
