Interested to Buy Any Domain ? << Click Here >> for more details...
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
- 6625 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
Discuss operations of CAD and CAM system.
What is platform-driven design?
Why is packaging and distribution important?
Where we have to use RCVF and where we have to use SNDRCVF. Basically what is difference between RCVF and SNDRCVF?
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
what do you mean by Foreign exchange domain
What are the Rules of Desktop Publishing?
What is "System framework" layer in multiple layer programming? (5 layer: UI, Business, Data, Common, "System framework" are layers in this design)
Explain various phases of the SDLC.
Describe your design ability ?what is your Architecture design GPA as it compares your general GPA?
If Web site developer want to evaluate their current authoring tool, where would they start?
vendor out going payment suppose is 10000/- and after some time vendor returned 2000/- as it is excess where this transaction to be posted in fi/ap
What are the best tools available now for creation of accessible Web sites?
What are virtual platforms for software development?
What is Make to Order, and what is the difference between Make to order and Make to Cash
