Hollywood Stars - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Graphs, Adjacency Dictionary

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 kind of graph representation should be used?
    • A: The problem asks for an adjacency dictionary to represent the graph.
  • Q: Is the graph directed or undirected?
    • A: The graph is undirected.
  • Q: Do all celebrities need to be connected to at least one other celebrity?
    • A: Yes, every celebrity in the example is connected to others.
HAPPY CASE
Input: Create an adjacency dictionary for a graph with nodes representing celebrities (Kevin Bacon, Meryl Streep, Idris Elba, Laverne Cox, Sofia Vergara) and their connections.
Output: {
  'Kevin Bacon': ['Laverne Cox', 'Sofia Vergara'],
  'Meryl Streep': ['Idris Elba', 'Sofia Vergara'],
  'Idris Elba': ['Meryl Streep', 'Laverne Cox'],
  'Laverne Cox': ['Kevin Bacon', 'Idris Elba'],
  'Sofia Vergara': ['Kevin Bacon', 'Meryl Streep']
}
Explanation: Each celebrity is connected to other celebrities based on the graph.

EDGE CASE
Input: A graph with no connections between some celebrities.
Output: The adjacency list should reflect isolated nodes, e.g., `'Kevin Bacon': []` if there are no connections for Kevin Bacon.

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 List: This is the most common and efficient representation when dealing with undirected graphs like this one. Each node (celebrity) is a key, and the value is a list of celebrities they are connected to.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to construct an adjacency dictionary where each celebrity is a key, and the value is a list of other celebrities they know, based on the graph provided.

1) Create a dictionary with keys as the names of the celebrities.
2) For each key, create a list of the other celebrities they are connected to.
3) Return the adjacency dictionary representing the graph.

⚠️ Common Mistakes

  • Forgetting to include both directions of the relationship (i.e., if A knows B, then B knows A).
  • Incorrectly representing connections between celebrities in the dictionary.

4: I-mplement

Implement the code to solve the algorithm.

hollywood_stars = {
    'Kevin Bacon': ['Laverne Cox', 'Sofia Vergara'], 
    'Meryl Streep': ['Idris Elba', 'Sofia Vergara'], 
    'Idris Elba': ['Meryl Streep', 'Laverne Cox'], 
    'Laverne Cox': ['Kevin Bacon', 'Idris Elba'], 
    'Sofia Vergara': ['Kevin Bacon', 'Meryl Streep']
}

5: R-eview

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

  • Input: hollywood_stars
  • Output:
['Kevin Bacon', 'Meryl Streep', 'Idris Elba', 'Laverne Cox', 'Sofia Vergara']
['Laverne Cox', 'Sofia Vergara'], ['Idris Elba', 'Sofia Vergara'], ['Meryl Streep', 'Laverne Cox'], ['Kevin Bacon', 'Idris Elba'], ['Kevin Bacon', 'Meryl Streep'](/codepath/compsci_guides/wiki/'Laverne-Cox',-'Sofia-Vergara'],-['Idris-Elba',-'Sofia-Vergara'],-['Meryl-Streep',-'Laverne-Cox'],-['Kevin-Bacon',-'Idris-Elba'],-['Kevin-Bacon',-'Meryl-Streep')
['Laverne Cox', 'Sofia Vergara']

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 nodes (celebrities). We need to define the relationships for each celebrity.
  • Space Complexity: O(N) for storing the adjacency dictionary.