One-way flight trip problem

Question

You are going on a one-way indirect flight trip that includes billions an unknown very large number of transfers.

• You are not stopping twice in the same airport.
• You have 1 ticket for each part of your trip.
• Each ticket contains src and dst airport.
• All the tickets you have are randomly sorted.
• You forgot the original departure airport (very first src) and your destination (last dst).

Design an algorithm to reconstruct your trip with minimum big-O complexity.

---

Attempting to solve this problem I have started to use a symmetric difference of two sets, Srcs and Dsts:

1)Sort all src keys in array Srcs
2)Sort all dst keys in array Dsts
3)Create an union set of both arrays to find non-duplicates - they are your first src and last dst
4)Now, having the starting point, traverse both arrays using the binary search.

But I suppose there must be another more effective method.

Answer 1

Construct a hashtable and add each airport into the hash table.

<key,value> = <airport, count>

Count for the airport increases if the airport is either the source or the destination. So for every airport the count will be 2 ( 1 for src and 1 for dst) except for the source and the destination of your trip which will have the count as 1.

You need to look at each ticket at least once. So complexity is O(n).

Answer 2

Summary: below a single-pass algorithm is given. (I.e., not just linear, but looks each ticket exactly once, which of course is optimal number of visits per ticket). I put the summary because there are many seemingly equivalent solutions and it would be hard to spot why I added another one. :)

I was actually asked this question in an interview. The concept is extremely simple: each ticket is a singleton list, with conceptually two elements, src and dst.

We index each such list in a hashtable using its first and last elements as keys, so we can find in O(1) if a list starts or ends at a particular element (airport). For each ticket, when we see it starts where another list ends, just link the lists (O(1)). Similarly, if it ends where another list starts, another list join. Of course, when we link two lists, we basically destroy the two and obtain one. (The chain of N tickets will be constructed after N-1 such links).

Care is needed to maintain the invariant that the hashtable keys are exactly the first and last elements of the remaining lists.

All in all, O(N).

And yes, I answered that on the spot :)

Edit Forgot to add an important point. Everyone mentions two hashtables, but one does the trick as well, because the algorithms invariant includes that at most one ticket list starts or begins in any single city (if there are two, we immediately join the lists at that city, and remove that city from the hashtable). Asymptotically there is no difference, it's just simpler this way.

Edit 2 Also of interest is that, compared to solutions using 2 hashtables with N entries each, this solution uses one hashtable with at most N/2 entries (which happens if we see the tickets in an order of, say, 1st, 3rd, 5th, and so on). So this uses about half memory as well, apart from being faster.