Unit 10 Session 1 Standard (Click for link to problem statements)
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?
clients list represent?
[celebrity_a, celebrity_b] represents that celebrity_a and celebrity_b have worked together.[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.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:
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
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_matrixReview the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
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){
'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
]Evaluate the performance of your algorithm and state any strong/weak or future potential work.
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.O(n^2) for storing the adjacency matrix and O(n) for the mapping dictionary.