Finding All Reachable Destinations - 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, Breadth First Search (BFS)

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: Each key in the dictionary is a city, and the corresponding value is a list of cities directly reachable from that city.
  • Q: Can there be loops or bidirectional flights?
    • A: Yes, some flights may be bidirectional, and there can be loops back to the same city.
  • Q: What traversal method is appropriate for finding all reachable destinations with minimum layovers?
    • A: Breadth First Search (BFS) is best for finding all reachable nodes layer by layer, ensuring ascending order by layovers.
HAPPY CASE
Input: 
flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo"", ""Beijing""],
    ""Beijing"": [""Mexico City"", ""Helsinki""],
    ""Helsinki"": [""Cairo"", ""New York""],
    ""Cairo"": [""Helsinki"", ""Reykjavik""],
    ""Reykjavik"": [""Cairo"", ""New York""],
    ""Mexico City"": [""Sydney""]
}
start = ""Beijing""
Output: ['Beijing', 'Mexico City', 'Helsinki', 'Sydney', 'Cairo', 'New York', 'Tokyo', 'Reykjavik']
Explanation: Starting from Beijing, you can reach all other destinations through direct and connecting flights.

EDGE CASE
Input: 
flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo""]
}
start = ""Tokyo""
Output: ['Tokyo', 'Sydney']
Explanation: Tokyo can only reach Sydney directly, and vice versa.

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): Since we need to find all reachable destinations in order of increasing layovers, BFS is the most suitable method.
  • Graph Representation: The adjacency dictionary is ideal for this problem, as it directly maps out the connections between cities.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use BFS to explore the graph starting from the start city, visiting all reachable cities and keeping track of them in the order of their distance from the start (i.e., the number of layovers).

1) Initialize a queue with the starting city and a set `visited` to track the visited cities.
2) Initialize an empty list `reachable` to store all cities that can be reached.
3) While there are cities in the queue:
   a) Pop the first city from the queue.
   b) Add the city to the `reachable` list.
   c) For each neighbor (connected city) of the current city, if it hasn't been visited:
      - Add the neighbor to the queue and mark it as visited.
4) Return the list of reachable cities.

⚠️ Common Mistakes

  • Not handling cases where there are no connections from the start city.
  • Forgetting to mark cities as visited, leading to infinite loops.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def get_all_destinations(flights, start):
    # Initialize queue for BFS and a set to track visited airports
    queue = deque([start])
    visited = set([start])
    
    # List to store the reachable airports in order of layovers
    reachable = []
    
    # Perform BFS
    while queue:
        # Get the current airport
        current = queue.popleft()
        reachable.append(current)
        
        # Visit all neighbors (connected airports)
        for neighbor in flights.get(current, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return reachable

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 = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo"", ""Beijing""],
    ""Beijing"": [""Mexico City"", ""Helsinki""],
    ""Helsinki"": [""Cairo"", ""New York""],
    ""Cairo"": [""Helsinki"", ""Reykjavik""],
    ""Reykjavik"": [""Cairo"", ""New York""],
    ""Mexico City"": [""Sydney""]
}
print(get_all_destinations(flights, ""Beijing""))

  • Output: ['Beijing', 'Mexico City', 'Helsinki', 'Sydney', 'Cairo', 'New York', 'Tokyo', 'Reykjavik']

  • Input:

flights = {
    ""Tokyo"": [""Sydney""],
    ""Sydney"": [""Tokyo""]
}
print(get_all_destinations(flights, ""Tokyo""))
  • Output: ['Tokyo', 'Sydney']

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 cities (vertices) and E is the number of flights (edges). Each city is visited once, and each flight is checked once.
  • Space Complexity: O(V) for storing the visited cities and the queue.