Answer / 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.

Answer / ivan krivulev

actually, you have a trip going in and out of each city
except the final to (sink) and from (source) cities. the
source and the sink appear only once in the table, the
source in the first column, sink in the second. this can be
found by reading the table once.

then each city must appear exactly once in the two columns.
so you can defenitely take no wrong trip and get stuck so
simplest thing to do is to start looking for the only
possible next flight in the table, starting from original
source. this will take you to your destination in n^2
complexity.

so maybe we can use some clever sorting knowing the maximum
letters in each city and sorting them alphabetically or we
can use some hashmap. one of these might do it in nlogn
probably but a bit dont feel like thinking too much.

if the flights are sorted you can definitely do it in nlogn
since you will use binary search to find the next flight in
the sorted array.which is n times logn.

hope this helped.

Answer / samir

Find the ticket which has a unique TO destination. That
destination should not occur in FROM field in any ticket

:)

discuss about cmmi model capability

1 Answers  

---

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   Google,

---

what is meaning for .net?ten introduction of software tools?

2 Answers   Wipro,

---

How to Design a Good Ad?

0 Answers  

---

Explain how object-oriented analysis and design differ from the traditional approach.

0 Answers  

---

---

waht do you mean by capital market

2 Answers   TATA,

---

What are virtual platforms for software development?

0 Answers  

---

vb.net with Sql sever2005

1 Answers  

---

What are the best tools available now for creation of accessible Web sites?

0 Answers  

---

What is Make to Order, and what is the difference between Make to order and Make to Cash

0 Answers  

---

what are the process colors? what is the space between letters called? what is the space between spaces called?

1 Answers  

---

what are the differences between system fresh and client fresh in SAP?

1 Answers  

---