Maximum Good People Based on Statements

Maximum Good People Based on Statements

What is this problem about?

The Maximum Good People Based on Statements coding problem gives you n people, each of whom is either "good" (always tells the truth) or "bad" (can say anything). Each person makes statements about every other person, claiming them to be good or bad. Your goal is to find the maximum number of people who could be good, given a consistent assignment of good/bad labels that doesn't contradict any good person's statements.

Why is this asked in interviews?

Oracle and TuSimple include this problem to evaluate logical reasoning under constraints and bit manipulation skills. With n ≤ 15, a brute-force enumeration over all 2^n subsets is feasible, but candidates must know how to implement it cleanly and verify consistency efficiently. It tests the ability to translate a verbal logic problem into a concrete algorithmic check.

Algorithmic pattern used

The approach uses bit manipulation enumeration (bitmask). For each possible subset of people assumed to be "good" (represented as a bitmask), you verify consistency: for each person marked as good in the subset, every statement they make must agree with the subset (they say person j is good iff j is in the subset, they say person j is bad iff j is not). If the subset is consistent, update the answer with the count of bits set. The complexity is O(2^n * n²), which is acceptable for n ≤ 15.

Example explanation

Suppose n = 2. Person 0 says person 1 is good. Person 1 says person 0 is good.

• Subset {}: trivially consistent (no good people to contradict). Count = 0.
• Subset {0}: Person 0 says person 1 is good, but 1 is not in subset. Inconsistent.
• Subset {1}: Person 1 says person 0 is good, but 0 is not in subset. Inconsistent.
• Subset {0, 1}: Person 0 says 1 is good ✓. Person 1 says 0 is good ✓. Consistent. Count = 2.
• Answer = 2.

Common mistakes candidates make

• Only checking good people's statements: Bad people's statements are irrelevant to consistency; only good people must be truthful. Checking bad people's statements adds incorrect constraints.
• Confusing "good says bad" with "bad says good": Statement values of 0 (bad) and 1 (good) must be mapped to subset membership correctly.
• Overcounting: Including subsets where good people contradict each other without noticing.

Interview preparation tip

For the Array Enumeration Backtracking Bit Manipulation interview pattern, build the bitmask enumeration skeleton first, then focus on writing a clean isValid(mask) function. This separation of concerns makes the code readable and debug-friendly. Practice similar problems where you enumerate subsets and verify a property.