There and Back - 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, Adjacency List, Bidirectional Graph Check

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 list represent?
    • A: Each element of the adjacency list flights[i] represents destinations reachable from destination i.
  • Q: Are we checking for bidirectional flights for every pair of destinations?
    • A: Yes, for each flight from destination i to j, there must be a flight from j to i.
  • Q: Can there be destinations with no outgoing flights?
    • A: Yes, some destinations might have no flights leading out.
HAPPY CASE
Input: flights = [1, 2], [0], [0, 3], [2](/codepath/compsci_guides/wiki/1,-2],-[0],-[0,-3],-[2)
Output: True
Explanation: All flights between destinations have return flights.

EDGE CASE
Input: flights = [1, 2], [], [0], [2](/codepath/compsci_guides/wiki/1,-2],-[],-[0],-[2)
Output: False
Explanation: There is no flight from destination 1 or 2 back to 0.

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

  • Graph Traversal: Traverse through each pair of connected nodes and check if the reverse connection exists.
  • Adjacency List Check: Since we are working with adjacency lists, we can directly access the list of connected nodes for any node i and check for bidirectionality.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to check that for every destination i, if there is a flight to destination j, then there should also be a flight from j back to i. We will iterate through each destination's adjacency list and ensure this condition holds for all flights.

1) Determine the number of destinations (length of `flights`).
2) For each destination `i`, loop through all destinations `j` that are reachable from `i` (i.e., in `flights[i]`).
3) For each destination `j`, check if destination `i` is in `flights[j]`.
4) If any destination `j` does not have a return flight to `i`, return False.
5) If all checks pass, return True.

⚠️ Common Mistakes

  • Forgetting that flights[i] may contain an empty list, meaning there are no outgoing flights from i.
  • Not checking both directions (i.e., from i to j and from j to i).
  • Assuming the graph is undirected when it is directed in this case.

4: I-mplement

Implement the code to solve the algorithm.

def bidirectional_flights(flights):
    n = len(flights)  # Number of destinations

    # Iterate over each destination i
    for i in range(n):
        # Iterate over each destination j reachable from i
        for j in flights[i]:
            # Check if destination j has a flight back to i
            if i not in flights[j]:
                return False  # If not bidirectional, return False
    return True  # All flights are bidirectional, return True

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 = [1, 2], [0], [0, 3], [2](/codepath/compsci_guides/wiki/1,-2],-[0],-[0,-3],-[2)

  • Expected output: True

  • Input: flights2 = [1, 2], [], [0], [2](/codepath/compsci_guides/wiki/1,-2],-[],-[0],-[2)

  • Expected output: False

Example trace for flights1:

  • From destination 0, we can fly to 1 and 2, both have return flights.
  • From destination 1, there's a flight back to 0.
  • From destination 2, we can fly to 0 and 3, both have return flights.
  • All flights are bidirectional, return True.

6: E-valuate

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

  • Time Complexity: O(N + E) where N is the number of destinations (nodes) and E is the number of flights (edges). We visit each edge twice, once for each direction.
  • Space Complexity: O(N + E) because we store the adjacency list for the graph, which holds up to N destinations and E flights.