Fixing Flight Booking Software - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Graph Traversal, BFS, Shortest Path

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 represent?
    • A: The dictionary represents the available flights, where each key is a location, and the value is a list of locations (neighbors) to which there are direct flights.
  • Q: Can the same location be visited multiple times?
    • A: No, once a location has been visited, it should not be revisited.
  • Q: What should the function return if no path is found?
    • A: It should return an empty list [].
HAPPY CASE
Input: 
flights = {
    'LAX': ['SFO'],
    'SFO': ['LAX', 'ORD', 'ERW'],
    'ERW': ['SFO', 'ORD'],
    'ORD': ['ERW', 'SFO', 'MIA'],
    'MIA': ['ORD']
}
start = 'LAX'
destination = 'MIA'

Output:
['LAX', 'SFO', 'ORD', 'MIA']
Explanation: The path LAX -> SFO -> ORD -> MIA is the shortest path with the least layovers.

EDGE CASE
Input: 
flights = {
    'LAX': ['SFO'],
    'SFO': ['LAX'],
    'MIA': []
}
start = 'LAX'
destination = 'MIA'

Output:
[]
Explanation: There is no possible path from LAX to MIA.

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

  • Breadth First Search (BFS): BFS is ideal for finding the shortest path in an unweighted graph, which this problem represents since each edge (flight) represents one step.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use BFS to explore the shortest path from the source to the destination. At each step, keep track of the path taken so far. When the destination is reached, return the path.

1) Initialize a queue with the `source` location and the path containing only the `source`.
2) Create a `visited` set to track locations that have already been visited to avoid cycles.
3) While the queue is not empty:
   a) Dequeue the current location and its corresponding path.
   b) If the current location is the `destination`, return the path.
   c) For each neighbor of the current location, if it has not been visited, enqueue it with the updated path and mark it as visited.
4) If the queue is exhausted and no path is found, return an empty list `[]`.

⚠️ Common Mistakes

  • Not keeping track of the current path correctly, resulting in incomplete or incorrect paths.
  • Forgetting to check if the source is the same as the destination for early termination.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def find_shortest_path(flights, source, destination):
    queue = deque([(source, [source])])  # Start with source in the path
    visited = set()

    while queue:
        current, path = queue.popleft()

        if current == destination:
            return path

        visited.add(current)

        for neighbor in flights.get(current, []):
            if neighbor not in visited:
                queue.append((neighbor, path + [neighbor]))  # Add neighbor to the path

    return []

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(find_shortest_path(flights, 'LAX', 'MIA'))  # Expected output: ['LAX', 'SFO', 'ORD', 'MIA']
print(find_shortest_path(flights, 'LAX', 'MIA'))  # Should return an empty list if no path is found
  • 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 vertices (locations) and E is the number of edges (flights). Each location is dequeued and processed once, and each flight (edge) is explored once.

  • Space Complexity: O(V) for storing the visited set and queue.

  • Adjacency Matrix vs. Adjacency List: If an adjacency matrix is used, the time complexity would change to O(V^2), since we would need to iterate over all possible locations (V) for each vertex when checking neighbors.