Maximizing Zombie Avoidance - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 45 mins
  • 🛠️ Topics: Dijkstra’s Algorithm, Graph Representation

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?
  • What is the graph representing?
    • The nodes represent safe zones and the edges represent roads between them with probabilities of survival.
  • How should we find the safest path?
    • Use a graph traversal algorithm like Dijkstra's to find the path with the highest probability of survival.
HAPPY CASE
Input: edges = [0, 1], [1, 2], [0, 2](/codepath/compsci_guides/wiki/0,-1],-[1,-2],-[0,-2), succ_prob = [0.5, 0.5, 0.2], n = 3, start = 0, end = 2
Output: 0.25
Explanation: The safest path is 0 -> 1 -> 2, with probability 0.5 * 0.5 = 0.25.

EDGE CASE
Input: edges = [0, 1](/codepath/compsci_guides/wiki/0,-1), succ_prob = [0.5], n = 2, start = 0, end = 1
Output: 0.5
Explanation: There's only one path, so the probability is 0.5.

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 Shortest Path (Max Probability) problems, we want to consider the following approaches:

  • Dijkstra’s Algorithm: Instead of finding the shortest path, use Dijkstra’s algorithm to maximize the probability of survival.
  • Heap (Priority Queue): Use a max-heap to prioritize the paths with the highest probability of success.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use Dijkstra’s algorithm with a max-heap to traverse the graph. Starting from the start zone, explore all possible paths, updating the survival probabilities as you go. Stop when you reach the end zone or exhaust all possible paths.

1) Build the graph as an adjacency list where each node points to its neighbors along with the survival probability of the connecting edge.
2) Initialize a max-heap where each element represents a zone and the current maximum probability of survival to reach that zone.
3) Start with the `start` zone with a probability of 1 (safe) and explore its neighbors.
4) For each neighbor, update the probability of survival if a better path is found.
5) If the `end` zone is reached, return the survival probability. If not, return 0 (indicating no path exists).
6) Use the heap to always process the zone with the current highest probability of survival.

⚠️ Common Mistakes

  • Forgetting to multiply probabilities along paths.
  • Not using a max-heap to ensure the best paths are processed first.

4: I-mplement

Implement the code to solve the algorithm.

import heapq

# Main function to find the maximum survival probability
def max_survival_probability(n, edges, succ_prob, start, end):
    # Build the graph as an adjacency list with probabilities
    graph = {i: [] for i in range(n)}
    
    for (u, v), prob in zip(edges, succ_prob):
        graph[u].append((v, prob))
        graph[v].append((u, prob))  # Undirected graph, so add both directions
    
    # Max-heap (priority queue) for Dijkstra's algorithm
    max_heap = [(-1, start)]  # Start with a probability of 1 (negative for max-heap behavior)
    
    # Distance array to store max probability to each node
    prob_to = {i: 0 for i in range(n)}
    prob_to[start] = 1  # Starting node has a survival probability of 1
    
    # Perform modified Dijkstra's algorithm
    while max_heap:
        current_prob, u = heapq.heappop(max_heap)
        current_prob = -current_prob  # Convert back to positive
        
        # If we reached the end node, return the probability
        if u == end:
            return round(current_prob, 2)
        
        # Visit each neighbor of the current node
        for v, prob in graph[u]:
            new_prob = current_prob * prob  # Probability through this path
            if new_prob > prob_to[v]:  # If this path gives a better probability
                prob_to[v] = new_prob
                heapq.heappush(max_heap, (-new_prob, v))  # Push with negative for max-heap
    
    # If the end node is not reachable, return 0
    return 0

5: R-eview

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

Example 1:

  • Input: edges = [0, 1], [1, 2], 0, 2, succ_prob = [0.5, 0.5, 0.2], start = 0, end = 2
  • Expected Output: 0.25
  • Watchlist:
    • Ensure that Dijkstra’s algorithm correctly computes the maximum survival probability.
    • Verify that all paths are considered and only the best path is chosen.

6: E-valuate

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

Assume E is the number of edges and V is the number of zones (nodes).

  • Time Complexity: O(E log V) because each edge is processed once and the heap operations take log V time.
  • Space Complexity: O(E + V) due to the graph representation and heap.