Network Lookup - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-30 mins
🛠️ Topics: Graphs, Adjacency Matrix, Mapping

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 each element in the clients list represent?
- A: Each element [celebrity_a, celebrity_b] represents that celebrity_a and celebrity_b have worked together.
Q: What is the goal of the problem?
- A: Return a dictionary mapping each celebrity to a unique ID and an adjacency matrix that represents the connections between the celebrities based on the IDs.
Q: How should the adjacency matrix be populated?
- A: For each pair [celebrity_a, celebrity_b], set matrix[i][j] and matrix[j][i] to 1 (assuming undirected relationships).

HAPPY CASE
Input: clients = [
                    [""Yalitza Aparicio"", ""Julio Torres""], 
                    [""Julio Torres"", ""Fred Armisen""], 
                    [""Bowen Yang"", ""Julio Torres""],
                    [""Bowen Yang"", ""Margaret Cho""],
                    [""Margaret Cho"", ""Ali Wong""],
                    [""Ali Wong"", ""Fred Armisen""], 
                    [""Ali Wong"", ""Bowen Yang""]
                 ]
Output:
id_map = {
  'Fred Armisen': 0,
  'Yalitza Aparicio': 1,
  'Margaret Cho': 2,
  'Bowen Yang': 3,
  'Ali Wong': 4,
  'Julio Torres': 5
}
adj_matrix = [
  [0, 0, 0, 0, 1, 1],  # Fred Armisen
  [0, 0, 0, 0, 0, 1],  # Yalitza Aparicio
  [0, 0, 0, 1, 1, 0],  # Margaret Cho
  [0, 0, 1, 0, 1, 1],  # Bowen Yang
  [1, 0, 1, 1, 0, 0],  # Ali Wong
  [1, 1, 0, 1, 0, 0]   # Julio Torres
]
Explanation: The dictionary maps celebrities to IDs and the adjacency matrix shows their connections.

EDGE CASE
Input: clients = []
Output: {}, []
Explanation: No relationships exist, so the result is an empty dictionary and an empty matrix.

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 Graph Representation problems, we want to consider the following approaches:

Adjacency Matrix: The problem specifically asks for the creation of an adjacency matrix based on the relationships between celebrities.
Mapping: We need to map each unique celebrity to a unique integer ID for efficient representation in the adjacency matrix.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will first create a mapping of celebrities to unique integer IDs. Then, using this mapping, we will construct an adjacency matrix where matrix[i][j] is 1 if the celebrity with ID i has worked with the celebrity with ID j, and 0 otherwise.

1) Create an empty set `unique_celebs` to store all unique celebrities.
2) Iterate through the `clients` list and add each celebrity to the `unique_celebs` set.
3) Create a dictionary `celeb_to_id` by mapping each unique celebrity to an integer ID.
4) Initialize an `n x n` adjacency matrix, where `n` is the number of unique celebrities, with all values set to 0.
5) For each pair `[celebrity_a, celebrity_b]` in `clients`, use the `celeb_to_id` mapping to get their IDs and set `matrix[i][j]` and `matrix[j][i]` to 1.
6) Return both the `celeb_to_id` dictionary and the adjacency matrix.

⚠️ Common Mistakes

Forgetting to map celebrities to IDs correctly, which can lead to incorrect matrix construction.
Not handling the case where no relationships exist.

4: I-mplement

Implement the code to solve the algorithm.

def get_adj_matrix(clients):
    # Step 1: Create a set of all unique celebrities
    unique_celebs = set()
    for pair in clients:
        unique_celebs.update(pair)
    
    # Step 2: Create a map of celebrities to IDs
    celeb_to_id = {celebrity: idx for idx, celebrity in enumerate(unique_celebs)}
    
    # Step 3: Initialize an adjacency matrix of size n x n, where n is the number of unique celebrities
    n = len(celeb_to_id)
    adj_matrix = [[0] * n for _ in range(n)]
    
    # Step 4: Populate the adjacency matrix
    for celeb_a, celeb_b in clients:
        id_a = celeb_to_id[celeb_a]
        id_b = celeb_to_id[celeb_b]
        adj_matrix[id_a][id_b] = 1
        adj_matrix[id_b][id_a] = 1  # Assuming connections are bidirectional
    
    return celeb_to_id, adj_matrix

5: R-eview

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

Input:

clients = [
    [""Yalitza Aparicio"", ""Julio Torres""], 
    [""Julio Torres"", ""Fred Armisen""], 
    [""Bowen Yang"", ""Julio Torres""],
    [""Bowen Yang"", ""Margaret Cho""],
    [""Margaret Cho"", ""Ali Wong""],
    [""Ali Wong"", ""Fred Armisen""], 
    [""Ali Wong"", ""Bowen Yang""]
]
id_map, adj_matrix = get_adj_matrix(clients)
print(id_map)
print(adj_matrix)

Output:

{
  'Fred Armisen': 0,
  'Yalitza Aparicio': 1,
  'Margaret Cho': 2,
  'Bowen Yang': 3,
  'Ali Wong': 4,
  'Julio Torres': 5
}
[
  [0, 0, 0, 0, 1, 1],  # Fred Armisen
  [0, 0, 0, 0, 0, 1],  # Yalitza Aparicio
  [0, 0, 0, 1, 1, 0],  # Margaret Cho
  [0, 0, 1, 0, 1, 1],  # Bowen Yang
  [1, 0, 1, 1, 0, 0],  # Ali Wong
  [1, 1, 0, 1, 0, 0]   # Julio Torres
]

6: E-valuate

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

Time Complexity: O(n) where n is the number of clients (pairs of celebrities). We iterate through the clients list to build the adjacency matrix and the mapping.
Space Complexity: O(n^2) for storing the adjacency matrix and O(n) for the mapping dictionary.