you are on a biz trip and travelling from one city to another. you have a stack of unsorted flight boarding passes. only departure city and destination city are on the boarding pass. how do you find the first departure city and your final destination city

Your current location is your departure city. Your final destination is the city whose name occurs only once among all the city names minus your departure city.

Why wouldn't you just look at all of the cities listed on the documents and the two which don't ever repeat are your departure and destination city. (For the two that don't repeat, one will only be listed as a departure and the other one will be the one that is only listed as a destination.)

Assume this is a acyclic graph (a city is not visited again once you leave it). Now, arrange the boarding passes and note the number of times a city appears in departure as well as arrival. For all intermediate cities this number will be the same. For the initial city the arrival-departure = -1 and for the destination arrival-departure = +1. Now, you start traversing from there. Form a table where you take each node and note the next node. For cyclic graphs it is more complex. You will still find the initial and destination city the same way but the traversal will be hard.

The question asks for the first departure city and final destination city. Sort the passes in ascending order of departure time using a fixed timezone - let's say EST (I have observed that boarding passes rarely, if at all, specify the local timezone, but this can be deduced from the departure city.) Doesn't matter how many times you repeat the same (departure/destination) city, the earliest departure time in the stack is your departure, the last arrival time in the stack is your destination.

cant u identify it with the departure city which in this case will match with one of the cities u are currently in?

for(Map.Entry entry : map.entrySet()){ if(!map.containsValue(entry.getKey())) { System.out.println("Source:"+entry.getKey()); } if(!map.containsKey(entry.getValue())) { System.out.println("Dest:"+entry.getValue()); } }

O(n)-Add into a hash by departure city, keep the corresponding destination. O(n)-go thru the hash to find the first filled entry, follow departure and keep indexing into subsequent destinations until there are no more departures. Do the reverse and index by departures until there are no more departures- that’s your final destination

- Read source and destination from each boarding pass - Insert these in an alphabetically sorted List of sources and destinations - After all entries are inserted, iterate through the arrays and compare each sources[i]==destinations[i]; - If a mismatch is found, compare sources[i]==destinations[i+1]. If these are equal unique source is found. - mark j=i+1 and continue comparison for remaining sources[i]==destinations[j] or vice versa if unique destination was found. Next mismatch will be the other remaining city. This solution is of order 'n log(n)'. Building sorted list is n log(n) Explanation: - We read and added n elements in an array (nlogn) - We iterated through the (worst case: entire, average case: n/2) array once with 1 additional checks at two points. (n operations, worst case) Overall: nlog(n)+n = 2nlog(n) P.S.: map.contains() inside a for() loop (or similar list.contains() etc.) is n*k which is O(n^2). Even if you keep cancelling the entries while insertion and store in list/maps that is (n-k)log(n-k). That can be a modification to original answer though.

Are you guys kidding? You look at the date and time. LoL.

If you assume some efficiency in the routes -- as in, there isn't backtracking -- you can analyze distances and positions of/ between the cities to map the full route. That will give you the endpoints.

using two arrays and search

I doubt you can assume your current location is your departure. The point of this type of problem is to show multiple solutions and also analyze the time complexity. One natural solution is to take one boarding pass, find the boarding pass with the next one after it, and so on. You would end up with a sorted stack of boarding passes. The method I described (take one, search the rest for the following city, repeat) would take order n squared time - n for the first pass, n-1 for the second pass, and so on. You could exit early, but the worst case time complexity is the sum from 1 to n, which is order n squared. The better solution, as GK wrote, is to take a boarding pass and write down the names of the two cities, and a notation indicating departure or arrival. On the next boarding pass, do the same; if a city is repeated, cross it off the list. At the end you will have two cities. This is order n, with order n storage space.

1. Iterate over set of boarding passes, and maintain a map of city --> occurrence count for source/destination city At end of iterating over passes, you have a map of city --> occurrence count 2. For the keyset of cities, get count for each city. If source count or destination count == 1, city is in the source/destination tuple.

1) Number each boarding pass from 1 to n ... takes O(n) 2) Create one hash table where you index by departure and iterate over boarding passes and enter indices corresponding to departure city ... takes O(n) 3) Now, start at 1 and follow the hash table adding following passes. When you reach the end, see if there are any boarding passes left. If not, you are done. If there are, then start at the first one and keep going until you pre-pend it to the previous sequence ... O(n) Hence, total time is O(n) + O(n) + O(n) = O(n)