Network Strength - 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), Strongly Connected Components

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 adjacency dictionary represent?
    • A: Each key is a celebrity, and its value is a list of other celebrities they ""like"".
  • Q: What does it mean for a group of celebrities to be strongly connected?
    • A: It means every celebrity in the network can reach every other celebrity, either directly or indirectly.
  • Q: What traversal method should we use to verify strong connectivity?
    • A: We can use Depth First Search (DFS) to check if all celebrities are reachable from any starting point.
HAPPY CASE
Input: 
celebrities1 = {
    ""Dev Patel"": [""Meryl Streep"", ""Viola Davis""],
    ""Meryl Streep"": [""Dev Patel"", ""Viola Davis""],
    ""Viola Davis"": [""Meryl Streep"", ""Viola Davis""]
}
Output: True
Explanation: Every celebrity can reach every other celebrity directly or indirectly.

EDGE CASE
Input: 
celebrities2 = {
    ""John Cho"": [""Rami Malek"", ""Zoe Saldana"", ""Meryl Streep""],
    ""Rami Malek"": [""John Cho"", ""Zoe Saldana"", ""Meryl Streep""],
    ""Zoe Saldana"": [""Rami Malek"", ""John Cho"", ""Meryl Streep""],
    ""Meryl Streep"": []
}
Output: False
Explanation: ""Meryl Streep"" cannot reach anyone, and no one can reach her, making the network not strongly connected.

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 Strongly Connected Components problems, we want to consider the following approaches:

  • DFS (Depth First Search): We can use DFS to verify whether all celebrities are reachable from any starting point and also check connectivity in a transposed graph.
  • Transpose the Graph: Reversing the direction of all edges allows us to check if all nodes are reachable when we traverse backward.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: The group of celebrities is strongly connected if:

  1. We can reach all celebrities starting from any celebrity.
  2. All celebrities can reach each other in the reverse direction (i.e., a reversed graph).

We will perform the following steps:

  1. Perform a DFS from any celebrity to check if we can visit all celebrities.
  2. Create a transposed version of the graph (reverse edges).
  3. Perform a DFS on the transposed graph to ensure we can visit all celebrities in the reversed direction.
1) Define a helper function `dfs(graph, start, visited)` to perform DFS from the given starting point.
2) Perform DFS on the original graph starting from any celebrity. Track the visited celebrities.
3) If not all celebrities are visited, return `False`.
4) Create a transposed graph where the edges are reversed.
5) Perform DFS on the transposed graph starting from the same celebrity.
6) If all celebrities are visited in the transposed graph, return `True`, otherwise return `False`.

⚠️ Common Mistakes

  • Forgetting to handle disconnected celebrities (those who do not like anyone or are not liked by anyone).
  • Not creating the transposed graph correctly, leading to inaccurate DFS results.

4: I-mplement

Implement the code to solve the algorithm.

def is_strongly_connected(celebrities):
    def dfs(graph, start, visited):
        stack = [start]
        while stack:
            celeb = stack.pop()
            if celeb not in visited:
                visited.add(celeb)
                stack.extend(graph[celeb])

    # Step 1: Perform DFS from any celebrity
    all_celebs = set(celebrities.keys())
    start = next(iter(all_celebs))  # Get any starting celebrity
    visited = set()
    dfs(celebrities, start, visited)
    
    # Check if we visited all celebrities
    if visited != all_celebs:
        return False
    
    # Step 2: Create a transposed graph (reverse edges)
    transposed_graph = {celeb: [] for celeb in celebrities}
    for celeb, likes in celebrities.items():
        for liked_celeb in likes:
            transposed_graph[liked_celeb].append(celeb)
    
    # Step 3: Perform DFS on the transposed graph
    visited = set()
    dfs(transposed_graph, start, visited)
    
    # Check if we visited all celebrities in the transposed graph
    return visited == all_celebs

5: R-eview

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

  • Input:
celebrities1 = {
    ""Dev Patel"": [""Meryl Streep"", ""Viola Davis""],
    ""Meryl Streep"": [""Dev Patel"", ""Viola Davis""],
    ""Viola Davis"": [""Meryl Streep"", ""Viola Davis""]
}

celebrities2 = {
    ""John Cho"": [""Rami Malek"", ""Zoe Saldana"", ""Meryl Streep""],
    ""Rami Malek"": [""John Cho"", ""Zoe Saldana"", ""Meryl Streep""],
    ""Zoe Saldana"": [""Rami Malek"", ""John Cho"", ""Meryl Streep""],
    ""Meryl Streep"": []
}

print(is_strongly_connected(celebrities1))  # Output: True
print(is_strongly_connected(celebrities2))  # Output: False

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 (likes). We perform DFS twice, once on the original graph and once on the transposed graph.
  • Space Complexity: O(V + E) for storing the graph, transposed graph, and visited sets.