Can Rebook Flight II - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graph Traversal, 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:

  • Depth First Search (DFS): This is useful for exploring all paths from a starting node until we find the destination or exhaust all options.
  • Breadth First Search (BFS): This was used in the previous solution, but here we will focus on DFS to explore all possible paths.

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 DFS to recursively explore the paths from the source location and check if we can reach dest. If we find the destination, return True; otherwise, return False after all paths have been explored.

1) Create a visited list to track locations we have already checked.
2) Define a recursive DFS function:
   a) If the current location is `dest`, return True.
   b) Mark the current location as visited.
   c) Explore all neighbors of the current location.
   d) If we find the destination through one of the neighbors, return True.
3) If the DFS function completes without finding the destination, return False.
4) Call the DFS function starting from `source`.

⚠️ Common Mistakes

  • Forgetting to mark locations as visited, which could lead to infinite recursion.
  • Not handling edge cases where there is no possible path or flights.

4: I-mplement

Implement the code to solve the algorithm.

def can_rebook(flights, source, dest):
    n = len(flights)  # Number of locations (nodes)
    visited = [False] * n
    
    def dfs(current):
        # If we reach the destination, return True
        if current == dest:
            return True
        
        visited[current] = True
        
        # Explore neighbors
        for neighbor in range(n):
            if flights[current][neighbor] == 1 and not visited[neighbor]:
                if dfs(neighbor):
                    return True
        
        return False  # No path found
    
    # Start DFS from the source
    return dfs(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:
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 the recursion stack in DFS.