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
- 6492 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
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.
why is testing neccessary?
what are the stages of software system engineering process?
What is the role of the W3C in Web accessibility?
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”
How would you create a footprint in your PCB designer software (say, Altium)?
Why is packaging and distribution important?
What is Make to Order, and what is the difference between Make to order and Make to Cash
how to downlaod image to target system? what is the vi editor?
What are the difference phases of software development? Explain briefly?
what do you mean by Foreign exchange domain
What are virtual platforms for software development?
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
How can authoring tools support the production of accessible Web content?
Ford Software engineer interview process and model questions
