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
- 6327 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
Where we have to use RCVF and where we have to use SNDRCVF. Basically what is difference between RCVF and SNDRCVF?
what is fact finding methods
Do you just jump in and start coding or do you sit down with a few collagues and create a designthen quickly prototype it?
What are the advantages Information System Architecture Framework in term of analysis and system design
How can authoring tools support the production of accessible Web content?
Why is packaging and distribution important?
What are the difference phases of software development? Explain briefly?
What may be the different component of Build phase? Build is not directly phase in SDLC, but its major part of SDLC, so need to know the different components for this including dcoument process.
How to Design a Good Newsletter?
If Web site developer want to evaluate their current authoring tool, where would they start?
How would you create a footprint in your PCB designer software (say, Altium)?
Discuss operations of CAD and CAM system.
What is Make to Order, and what is the difference between Make to order and Make to Cash
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)
