Get Flight Cost - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30-40 mins
  • 🛠️ Topics: Graph Traversal, DFS, Backtracking, Weighted Graphs

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 flights dictionary represent?
    • A: Each key in flights is a starting location, and each value is a list of tuples where the first item is a destination and the second is the cost of the flight to that destination.
  • Q: Can there be multiple valid paths between start and dest?
    • A: Yes, there may be multiple valid paths, and the problem asks for any valid answer.
  • Q: What should be returned if no valid path is found?
    • A: If no valid path exists, return -1.
HAPPY CASE
Input: 
flights = {
    'LAX': [('SFO', 50)],
    'SFO': [('LAX', 50), ('ORD', 100), ('ERW', 210)],
    'ERW': [('SFO', 210), ('ORD', 100)],
    'ORD': [('ERW', 300), ('SFO', 100), ('MIA', 400)],
    'MIA': [('ORD', 400)]
}
start = 'LAX'
dest = 'MIA'

Output:
550
Explanation: One possible path is LAX -> SFO -> ORD -> MIA with total cost 50 + 100 + 400 = 550.

EDGE CASE
Input: 
flights = {
    'LAX': [('SFO', 50)],
    'SFO': [('LAX', 50)],
    'MIA': []
}
start = 'LAX'
dest = 'MIA'

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

  • Depth First Search (DFS) with backtracking: This is useful for exploring all possible paths and calculating the total cost of each.
  • Breadth First Search (BFS) or Dijkstra’s Algorithm: These could also be used to find the shortest path in a weighted graph, though DFS is sufficient if we are just looking for any path.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use DFS to explore all possible paths from start to dest. At each step, keep track of the total cost. If a valid path to the destination is found, return the total cost. If no valid path exists, return -1.

1) Initialize a `visited` set to track locations we have already visited to avoid cycles.
2) Define a recursive DFS function:
   a) If the current location is `dest`, return the total cost.
   b) Mark the current location as visited.
   c) For each neighbor (destination) of the current location, recursively explore the path with the updated total cost.
   d) If a valid path is found, return the total cost.
   e) Backtrack by unmarking the current location as visited.
3) Start the DFS from the `start` location.
4) If no valid path is found, return `-1`.

⚠️ Common Mistakes

  • Not marking locations as visited, which could lead to infinite recursion in cycles.
  • Forgetting to backtrack (unmark locations) when exploring different paths.

4: I-mplement

Implement the code to solve the algorithm.

def calculate_cost(flights, start, dest):
    visited = set()
    
    # Helper function for DFS with backtracking
    def dfs(current, total_cost):
        # If we reach the destination, return the cost
        if current == dest:
            return total_cost
        
        # Mark the current node as visited
        visited.add(current)
        
        # Explore all possible flights from the current location
        for neighbor, cost in flights.get(current, []):
            if neighbor not in visited:
                # Recursively calculate the cost of going to the neighbor
                result = dfs(neighbor, total_cost + cost)
                if result != -1:  # If a valid path is found, return it immediately
                    return result
        
        # Unmark the current node as visited (backtracking)
        visited.remove(current)
        
        # If no valid path is found, return -1
        return -1
    
    # Call DFS starting from the 'start' location
    return dfs(start, 0)

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', 50)],
    'SFO': [('LAX', 50), ('ORD', 100), ('ERW', 210)],
    'ERW': [('SFO', 210), ('ORD', 100)],
    'ORD': [('ERW', 300), ('SFO', 100), ('MIA', 400)],
    'MIA': [('ORD', 400)]
}

print(calculate_cost(flights, 'LAX', 'MIA'))  # Expected output: 550 or 960
print(calculate_cost(flights, 'LAX', 'MIA'))  # Another valid path should return 960
print(calculate_cost(flights, 'LAX', 'MIA'))  # Should return -1 when no path is found
  • Output:
550  # LAX -> SFO -> ORD -> MIA
960  # LAX -> SFO -> ERW -> ORD -> MIA
-1   # No path found

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 locations and E is the number of flights. This accounts for exploring all flights in the worst case.
  • Space Complexity: O(V) for the visited set and recursion stack used in DFS.