Get Flight Itinerary - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Graph Traversal, DFS, Backtracking

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 the adjacency dictionary flights represent?
  • A: Each key in flights is an airport, and the value is a list of airports that can be reached via direct flights from that key.
• Q: Can there be multiple valid paths from source to destination?
  • A: Yes, and the problem allows any valid path to be returned.
• Q: What should be returned if no path is found?
  • A: The function should return None if no valid path exists from source to destination.

HAPPY CASE
Input: 
flights = {
    'LAX': ['SFO'],
    'SFO': ['LAX', 'ORD', 'ERW'],
    'ERW': ['SFO', 'ORD'],
    'ORD': ['ERW', 'SFO', 'MIA'],
    'MIA': ['ORD']
}
source = 'LAX'
dest = 'MIA'

Output:
['LAX', 'SFO', 'ORD', 'MIA']
Explanation: The path LAX -> SFO -> ORD -> MIA is valid, though LAX -> SFO -> ERW -> ORD -> MIA is also valid.

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 Flight Itinerary problems, we want to consider the following approaches:

• Depth First Search (DFS) with backtracking: This is ideal for exploring all possible paths from source to destination. DFS allows us to explore each path and backtrack if we reach a dead end.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all possible paths from the source airport to the destination. At each step, recursively attempt to extend the current path by exploring neighboring airports. If a valid path is found, return it. If no valid path is found, backtrack to explore alternative routes.

1) Define a recursive DFS function that takes the current airport and the current path as parameters.
2) If the current airport is the `destination`, return the current path.
3) If the current airport has no outgoing flights, return None.
4) For each neighboring airport, recursively attempt to extend the current path by visiting the neighbor.
   a) If a valid path is found, return it.
   b) If no valid path is found, backtrack and explore other neighbors.
5) Start DFS from the `source` airport.

⚠️ Common Mistakes

• Not properly handling the case where an airport has no outgoing flights, leading to infinite recursion.
• Forgetting to backtrack after exploring an invalid path, which can lead to incorrect results.

4: I-mplement

Implement the code to solve the algorithm.

def get_itinerary(flights, source, dest):
    def dfs(current, path):
        # If we've reached the destination, return the path
        if current == dest:
            return path
        
        # If the current airport has no outgoing flights, return None
        if current not in flights:
            return None
        
        # Explore each neighboring airport
        for neighbor in flights[current]:
            result = dfs(neighbor, path + [neighbor])
            if result:
                return result
        
        # If no path is found, return None
        return None

    # Start DFS from the source
    return dfs(source, [source])

5: R-eview

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

• Input:

flights = {
    'LAX': ['SFO'],
    'SFO': ['LAX', 'ORD', 'ERW'],
    'ERW': ['SFO', 'ORD'],
    'ORD': ['ERW', 'SFO', 'MIA'],
    'MIA': ['ORD']
}

print(get_itinerary(flights, 'LAX', 'MIA'))  # Expected output: ['LAX', 'SFO', 'ORD', 'MIA']

• Output:

['LAX', 'SFO', 'ORD', 'MIA']

6: E-valuate

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

• Time Complexity: O(V + E), where V is the number of airports (vertices) and E is the number of flights (edges). Each airport and flight is visited once in the DFS traversal.
• Space Complexity: O(V) for storing the current path and the recursion stack.