Casting Call Search - 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: 15-20 mins
🛠️ Topics: Graphs, Breadth First Search (BFS), Pathfinding

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 matrix celebs[i][j] = 1 mean?
- A: It means that celebrity i has a connection to celebrity j.
Q: What traversal method should we use to search for the path?
- A: We should use Breadth First Search (BFS) to explore the connections and find a path from start_celeb to target_celeb.
Q: What should we return if there is no connection between start_celeb and target_celeb?
- A: Return False if no path exists.

HAPPY CASE
Input: celebs = [
            [0, 1, 0, 0, 0, 0, 0, 0], # Celeb 0
            [0, 1, 1, 0, 0, 0, 0, 0], # Celeb 1
            [0, 0, 0, 1, 0, 1, 0, 0], # Celeb 2
            [0, 0, 0, 0, 1, 0, 1, 0], # Celeb 3
            [0, 0, 0, 1, 0, 0, 0, 1], # Celeb 4
            [0, 1, 0, 0, 0, 0, 0, 0], # Celeb 5
            [0, 0, 0, 1, 0, 0, 0, 1], # Celeb 6
            [0, 0, 0, 0, 1, 0, 1, 0]  # Celeb 7
         ]
start_celeb = 0
target_celeb = 6
Output: True
Explanation: There is a path of connections from celebrity 0 to celebrity 6.

EDGE CASE
Input: celebs = [
            [0, 1, 0, 0, 0, 0, 0, 0], # Celeb 0
            [0, 1, 1, 0, 0, 0, 0, 0], # Celeb 1
            [0, 0, 0, 1, 0, 1, 0, 0], # Celeb 2
            [0, 0, 0, 0, 1, 0, 1, 0], # Celeb 3
            [0, 0, 0, 1, 0, 0, 0, 1], # Celeb 4
            [0, 1, 0, 0, 0, 0, 0, 0], # Celeb 5
            [0, 0, 0, 1, 0, 0, 0, 1], # Celeb 6
            [0, 0, 0, 0, 1, 0, 1, 0]  # Celeb 7
         ]
start_celeb = 3
target_celeb = 5
Output: False
Explanation: There is no connection path from celebrity 3 to celebrity 5.

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

Breadth First Search (BFS): Since BFS explores nodes layer by layer and ensures that we find the shortest path first, it is ideal for pathfinding problems like this one.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use BFS to explore the graph starting from the start_celeb, visiting all connected celebrities and marking them as visited. If we reach the target_celeb, we return True. If BFS completes without finding the target, we return False.

1) Initialize a queue with the `start_celeb` and a set `visited` to keep track of the celebrities we have already checked.
2) Perform BFS:
   a) Pop the current celebrity from the queue.
   b) If the current celebrity is the `target_celeb`, return `True`.
   c) For each neighbor of the current celebrity (each connection), if the neighbor has not been visited, add them to the queue and mark them as visited.
3) If the search completes without finding the `target_celeb`, return `False`.

⚠️ Common Mistakes

Forgetting to mark celebrities as visited, which can lead to infinite loops.
Confusing directed and undirected edges in the adjacency matrix, as connections are not symmetric.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def have_connection(celebs, start_celeb, target_celeb):
    n = len(celebs)  # Number of celebrities
    queue = deque([start_celeb])
    visited = set([start_celeb])  # To track visited celebrities

    while queue:
        current = queue.popleft()
        
        # If we reach the target celebrity, return True
        if current == target_celeb:
            return True
        
        # Explore the connections of the current celebrity
        for neighbor in range(n):
            if celebs[current][neighbor] == 1 and neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)
    
    # If we exhaust the search and don't find the target, return False
    return False

5: R-eview

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

Input:

celebs = [
            [0, 1, 0, 0, 0, 0, 0, 0], # Celeb 0
            [0, 1, 1, 0, 0, 0, 0, 0], # Celeb 1
            [0, 0, 0, 1, 0, 1, 0, 0], # Celeb 2
            [0, 0, 0, 0, 1, 0, 1, 0], # Celeb 3
            [0, 0, 0, 1, 0, 0, 0, 1], # Celeb 4
            [0, 1, 0, 0, 0, 0, 0, 0], # Celeb 5
            [0, 0, 0, 1, 0, 0, 0, 1], # Celeb 6
            [0, 0, 0, 0, 1, 0, 1, 0]  # Celeb 7
         ]
print(have_connection(celebs, 0, 6))  # Output: True
print(have_connection(celebs, 3, 5))  # Output: False

6: E-valuate

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

Time Complexity: O(n^2) where n is the number of celebrities. BFS visits each node once, and checking each connection takes O(n) time.
Space Complexity: O(n) for the queue and visited set, as we store up to n celebrities.