Can Rebook Flight - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15-25 mins
  • 🛠️ Topics: Graph Traversal, BFS, DFS

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 a 1 in the flights matrix signify?
    • A: It means there is a direct flight from location i to location j.
  • Q: Can the source and destination be the same?
    • A: Yes, if source == dest, we can return True because no travel is required.
  • Q: Are there any restrictions on the number of locations?
    • A: The problem doesn't specify limits, but we can assume it will fit into memory.
HAPPY CASE
Input: 
flights = [
    [0, 1, 0],  # Flight 0
    [0, 0, 1],  # Flight 1
    [0, 0, 0]   # Flight 2
]
source = 0
dest = 2

Output:
True
Explanation: There is a path from location 0 to 2 through location 1.

EDGE CASE
Input: 
flights = [
    [0, 0],
    [0, 0]
]
source = 0
dest = 1

Output:
False
Explanation: There is no flight available from location 0 to location 1.

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:

  • Breadth First Search (BFS): This is useful for finding the shortest path or verifying if there exists any path between two nodes (locations).
  • Depth First Search (DFS): This can also be used to explore all possible paths, but BFS might be more intuitive here since we only care about finding if a path exists.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Treat the flight routes as a graph represented by the adjacency matrix flights. Use BFS to traverse from the source location and check if a path exists to dest. If the destination is reached, return True; otherwise, return False after all possibilities are explored.

1) If `source == dest`, return True immediately (no travel required).
2) Initialize a queue with the `source` location to perform BFS.
3) Create a `visited` list to keep track of locations already visited to avoid cycles.
4) Perform BFS by:
   a) Dequeue the current location.
   b) Explore all possible destinations from the current location.
   c) If a flight exists to `dest`, return True.
   d) If not visited, mark the location as visited and enqueue it for further exploration.
5) If BFS completes without finding the destination, return False.

⚠️ Common Mistakes

  • Forgetting to handle the case where source == dest early.
  • Not marking locations as visited, which could lead to infinite loops or redundant checks.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def can_rebook(flights, source, dest):
    n = len(flights)  # Number of locations (nodes)
    
    # If source is same as destination, no need to search
    if source == dest:
        return True
    
    # Use a queue to perform BFS
    queue = deque([source])
    visited = [False] * n
    visited[source] = True
    
    while queue:
        current = queue.popleft()
        
        # Explore neighbors
        for neighbor in range(n):
            if flights[current][neighbor] == 1 and not visited[neighbor]:
                if neighbor == dest:
                    return True  # Path found
                queue.append(neighbor)
                visited[neighbor] = True
    
    return False  # No path found

5: R-eview

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

  • Input:
flights1 = [
    [0, 1, 0],  # Flight 0
    [0, 0, 1],  # Flight 1
    [0, 0, 0]   # Flight 2
]

flights2 = [
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

print(can_rebook(flights1, 0, 2))  # True
print(can_rebook(flights2, 0, 2))  # False
  • Output:
True
False

6: E-valuate

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

  • Time Complexity: O(V^2) where V is the number of locations (vertices). This is because for each location, we check all other locations in the adjacency matrix.
  • Space Complexity: O(V) for the visited list and BFS queue.