Round 1
Questions: You are given a list[list[str]] which represents boarding passes for an itinerary. You optimized for the lowest cost for the trip, and hence you chose multiple layovers (including cyclic flight paths). Each item in the list is a [source_airport, destination_airport].
Example:
boarding_passes = [ ["LAS", "SLC"], ["DFW", "JFK"], ["SLC", "LAX"], ["LAX", "LAS"], ["LAX", "DFW"], ["SFO", "LAX"], ]
Your task:
- Find the source and destination from the above itinerary.
- Find the actual path travelled.
- Find the shortest path that you could have taken if you did not optimize for cost of the trip.
Candidate's Approach
-
To find the source and target:
- Method 1: source = set(sources) - set(targets); target = set(targets) - set(sources).
- Method 2: Construct a graph from the edges, find a node with indegree=0 (which is the source) and outdegree=0 (which would be the target).
-
Finding the actual path travelled:
- The actual path will be the DFS path that has all nodes of the graph.
- The challenge is accounting for cycles in DFS to avoid infinite loops.
- Seeking clarification if this is a Hamiltonian path finding problem.
-
Finding the shortest path without optimizing for cost can be done using BFS.
Interviewer's Feedback
No feedback provided.