Exposing Superman - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Graph Theory, Array Manipulation

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?

• The function expose_superman() should identify the citizen who fits the description of Superman, who trusts no one and is trusted by everyone else. If such a citizen does not exist, return -1.

HAPPY CASE
Input: n = 2, trust = [1, 2](/codepath/compsci_guides/wiki/1,-2)
Expected Output: 2

Input: n = 3, trust = [1, 3], [2, 3](/codepath/compsci_guides/wiki/1,-3],-[2,-3)
Expected Output: 3

EDGE CASE
Input: n = 1, trust = []
Expected Output: 1

Input: n = 3, trust = [1, 3], [2, 3], [3, 1](/codepath/compsci_guides/wiki/1,-3],-[2,-3],-[3,-1)
Expected Output: -1

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two arrays to track the number of people each person trusts and the number of people who trust each person. Identify the person who trusts no one and is trusted by everyone else.

1. If `n` is 1, return 1 since the only person must be Superman.
2. Initialize two arrays `trust_counts` and `trusted_by_counts` of size `n + 1` with all elements set to 0.
3. Iterate through the `trust` array:
   a. For each pair `[a, b]` in `trust`, increment `trusted_by_counts[a]` and `trust_counts[b]`.
4. Iterate through each person from 1 to `n`:
   a. If `trust_counts[i] == n - 1` and `trusted_by_counts[i] == 0`, return `i`.
5. If no such person is found, return `-1`

⚠️ Common Mistakes

• Not properly initializing or updating the trust_counts and trusted_by_counts arrays.
• Incorrectly checking the conditions for identifying Superman.

I-mplement

Implement the code to solve the algorithm.

def expose_superman(trust, n):
    if n == 1:
        return 1  # If there's only one person, they are Superman by default.
    
    trust_counts = [0] * (n + 1)
    trusted_by_counts = [0] * (n + 1)
    
    for a, b in trust:
        trusted_by_counts[a] += 1
        trust_counts[b] += 1
    
    for i in range(1, n + 1):
        if trust_counts[i] == n - 1 and trusted_by_counts[i] == 0:
            return i
    
    return -1