Unit 11 Session 2 Advanced (Click for link to problem statements)
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?
HAPPY CASE
Input: edges = [[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]], 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.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:
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
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 0Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example 1:
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).
O(E log V) because each edge is processed once and the heap operations take log V time.O(E + V) due to the graph representation and heap.