c - 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).