Unit 10 Session 1 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?
[u, v] means that celebrity u spreads the rumor to celebrity v.(-1, -1).HAPPY CASE
Input:
connections = [
[""Amber Gill"", ""Greg O'Shea""],
[""Amber Gill"", ""Molly-Mae Hague""],
[""Greg O'Shea"", ""Molly-Mae Hague""],
[""Greg O'Shea"", ""Tommy Fury""],
[""Molly-Mae Hague"", ""Tommy Fury""],
[""Tommy Fury"", ""Ovie Soko""],
[""Curtis Pritchard"", ""Maura Higgins""]
]
n = 7
start = ""Amber Gill""
Output:
{
""Amber Gill"": (1, 12),
""Greg O'Shea"": (2, 11),
""Molly-Mae Hague"": (3, 8),
""Tommy Fury"": (4, 7),
""Ovie Soko"": (5, 6),
""Curtis Pritchard"": (-1, -1),
""Maura Higgins"": (-1, -1)
}
Explanation: The rumor starts with ""Amber Gill"" and spreads to other connected celebrities. ""Curtis Pritchard"" and ""Maura Higgins"" never hear the rumor.
EDGE CASE
Input:
connections = [
[""Amber Gill"", ""Greg O'Shea""],
[""Amber Gill"", ""Molly-Mae Hague""]
]
n = 4
start = ""Molly-Mae Hague""
Output:
{
""Amber Gill"": (-1, -1),
""Greg O'Shea"": (-1, -1),
""Molly-Mae Hague"": (1, 2)
}
Explanation: The rumor only starts with ""Molly-Mae Hague"" and does not reach the other celebrities.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 Arrival and Departure Times problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will perform a DFS starting from the start celebrity, and for each celebrity, record their arrival time (when the rumor reaches them) and their departure time (when they finish spreading the rumor to all their neighbors). If a celebrity is never visited, their arrival and departure times remain (-1, -1).
1) Build an adjacency list `graph` from the list of connections to represent the directed graph.
2) Initialize `arrival` and `departure` dictionaries with all times set to `-1` for all celebrities.
3) Define a recursive DFS function that:
a) Marks the arrival time of the current celebrity.
b) Recursively visits all unvisited neighbors.
c) Marks the departure time when all neighbors are visited.
4) Start DFS from the `start` celebrity.
5) Return the arrival and departure times for each celebrity.⚠️ Common Mistakes
Implement the code to solve the algorithm.
from collections import defaultdict
def rumor_spread_times(connections, n, start):
# Step 1: Build the graph
graph = defaultdict(list)
for u, v in connections:
graph[u].append(v)
# Step 2: Initialize arrival and departure dictionaries with default values (-1)
arrival = {}
departure = {}
all_celebrities = set([u for u, _ in connections] + [v for _, v in connections])
for celeb in all_celebrities:
arrival[celeb] = -1
departure[celeb] = -1
# Step 3: DFS Function to track time
time = [0] # Keep track of the time as a list so it's mutable in the dfs
def dfs(celeb):
# Set arrival time
time[0] += 1
arrival[celeb] = time[0]
# Explore all neighbors
for neighbor in graph[celeb]:
if arrival[neighbor] == -1: # Only visit if not already visited
dfs(neighbor)
# Set departure time
time[0] += 1
departure[celeb] = time[0]
# Step 4: Start DFS from the given starting celebrity
if start in all_celebrities:
dfs(start)
# Step 5: Return the results
result = {celeb: (arrival[celeb], departure[celeb]) for celeb in all_celebrities}
return resultReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
connections = [
[""Amber Gill"", ""Greg O'Shea""],
[""Amber Gill"", ""Molly-Mae Hague""],
[""Greg O'Shea"", ""Molly-Mae Hague""],
[""Greg O'Shea"", ""Tommy Fury""],
[""Molly-Mae Hague"", ""Tommy Fury""],
[""Tommy Fury"", ""Ovie Soko""],
[""Curtis Pritchard"", ""Maura Higgins""]
]
print(rumor_spread_times(connections, 7, ""Amber Gill"")){
""Amber Gill"": (1, 12),
""Greg O'Shea"": (2, 11),
""Molly-Mae Hague"": (3, 8),
""Tommy Fury"": (4, 7),
""Ovie Soko"": (5, 6),
""Curtis Pritchard"": (-1, -1),
""Maura Higgins"": (-1, -1)
}Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(V + E), where V is the number of vertices (celebrities) and E is the number of edges (connections).O(V + E) for storing the graph and the arrival/departure dictionaries.