Find Itinerary - codepath/compsci_guides GitHub Wiki

Unit 10 Session 1 Standard (Click for link to problem statements)

Unit 10 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-30 mins
🛠️ Topics: Graphs, Directed Acyclic Graph (DAG), Topological Sort

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: What does each element in the boarding_passes list represent?
- A: Each element (departure, arrival) represents a flight from departure to arrival.
Q: What is the goal of the problem?
- A: To reconstruct the travel itinerary in the correct order, starting from the first departure and ending at the final destination.
Q: How can we find the starting point of the itinerary?
- A: The starting point is the airport that does not appear as an arrival in any of the flights.

HAPPY CASE
Input: boarding_passes = [
                    (""JFK"", ""ATL""),
                    (""SFO"", ""JFK""),
                    (""ATL"", ""ORD""),
                    (""LAX"", ""SFO"")]
Output: ['LAX', 'SFO', 'JFK', 'ATL', 'ORD']
Explanation: The correct itinerary starts at LAX, then proceeds to SFO, JFK, ATL, and finally ORD.

EDGE CASE
Input: boarding_passes = [
                    (""LAX"", ""DXB""),
                    (""DFW"", ""JFK""),
                    (""LHR"", ""DFW""),
                    (""JFK"", ""LAX"")]
Output: ['LHR', 'DFW', 'JFK', 'LAX', 'DXB']
Explanation: The correct itinerary starts at LHR, proceeds to DFW, JFK, LAX, and finally DXB.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Graph Traversal problems, we want to consider the following approaches:

Topological Sort: Since we are working with a Directed Acyclic Graph (DAG), we can map each flight to reconstruct the itinerary in a sorted order without cycles.
Graph Construction: We can construct a graph from the list of flights and trace the itinerary from the first departure airport to the final destination.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will first create a mapping from each departure to its corresponding arrival. Then, we identify the starting point of the itinerary, which is the airport that never appears as an arrival. Finally, we trace the entire itinerary in the correct order.

1) Create a dictionary `flight_map` where the key is the departure airport and the value is the arrival airport.
2) Identify the starting airport by finding a departure airport that never appears in the list of arrival airports.
3) Starting from this airport, build the itinerary by following the flights using the `flight_map`.
4) Continue following the flights until the last airport (which has no outgoing flights).
5) Return the constructed itinerary.

⚠️ Common Mistakes

Forgetting to account for airports that appear only as departures but not as arrivals (the starting point).
Assuming the order of flights is already given when it needs to be constructed.

4: I-mplement

Implement the code to solve the algorithm.

def find_itinerary(flights):
    # Step 1: Create a mapping from departure to arrival
    flight_map = {}
    all_arrivals = set()
    
    for departure, arrival in flights:
        flight_map[departure] = arrival
        all_arrivals.add(arrival)
    
    # Step 2: Find the starting point (departure that is not an arrival)
    start = None
    for departure, arrival in flights:
        if departure not in all_arrivals:
            start = departure
            break
    
    # Step 3: Trace the itinerary
    itinerary = []
    while start:
        itinerary.append(start)
        start = flight_map.get(start)
    
    return itinerary

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input:

boarding_passes_1 = [
                    (""JFK"", ""ATL""),
                    (""SFO"", ""JFK""),
                    (""ATL"", ""ORD""),
                    (""LAX"", ""SFO"")]
print(find_itinerary(boarding_passes_1))

Output: ['LAX', 'SFO', 'JFK', 'ATL', 'ORD']
Input:

boarding_passes_2 = [
                    (""LAX"", ""DXB""),
                    (""DFW"", ""JFK""),
                    (""LHR"", ""DFW""),
                    (""JFK"", ""LAX"")]
print(find_itinerary(boarding_passes_2))

Output: ['LHR', 'DFW', 'JFK', 'LAX', 'DXB']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity: O(n), where n is the number of boarding passes. We iterate through the list of flights once to build the flight map and once more to trace the itinerary.
Space Complexity: O(n) for storing the flight map and the itinerary.