Gossip Chain - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 25-35 mins
  • 🛠️ Topics: Graphs, Depth First Search (DFS), Arrival and Departure Times

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 do the connections represent?
    • A: Each connection [u, v] means that celebrity u spreads the rumor to celebrity v.
  • Q: What are the arrival and departure times?
    • A: The arrival time of a celebrity is when they hear the rumor for the first time, and the departure time is when they have finished spreading the rumor to all their connected celebrities.
  • Q: What should be the arrival and departure times for celebrities who never hear the rumor?
    • A: Their arrival and departure times should be (-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.

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 Arrival and Departure Times problems, we want to consider the following approaches:

  • DFS (Depth First Search): This is ideal for traversing through the graph structure and recording the arrival and departure times of each node (celebrity).
  • Graph Construction: Use an adjacency list to represent the graph and manage connections between celebrities.

3: P-lan

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

  • Forgetting to handle isolated celebrities who never receive the rumor, leading to incorrect times being recorded.
  • Failing to update the departure time correctly after visiting all neighbors.

4: I-mplement

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 result

5: R-eview

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

  • 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""]
]

print(rumor_spread_times(connections, 7, ""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)
}

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 vertices (celebrities) and E is the number of edges (connections).
  • Space Complexity: O(V + E) for storing the graph and the arrival/departure dictionaries.