Find All People With Secret

Find All People With Secret

What is this problem about?

The Find All People With Secret interview question is a complex connectivity problem. You start with person 0 sharing a secret with person firstPerson at time 0. You are then given a list of meetings [person1, person2, time]. If someone who knows the secret meets someone else at a specific time, the secret is shared. A key rule is that secrets can spread instantaneously among everyone meeting at the same time. You need to return a list of everyone who knows the secret after all meetings.

Why is this asked in interviews?

This "Hard" problem is asked by Google, Microsoft, and Amazon to evaluate a candidate's mastery of graph theory and time-ordered processing. It tests the ability to handle Graph interview patterns where the graph structure changes over time. It evaluation your proficiency with Union Find or BFS/DFS and your ability to correctly group events by timestamps.

Algorithmic pattern used

This problem is best solved using Union Find with Reset or BFS per Timestamp.

1. Sort all meetings by time.
2. Group meetings that occur at the same timestamp.
3. For each timestamp group:
   • Build a temporary graph of connections or use Union Find to link the people meeting.
   • Identify who among these people already knows the secret (from previous times).
   • Use BFS/DFS or Union Find's find to spread the secret to everyone in their connected components.
   • Crucially, if a group doesn't end up knowing the secret, "un-link" them (reset Union Find) so they don't incorrectly stay connected for future timestamps.

Example explanation

Meetings: [[1, 2, 5], [2, 3, 5], [3, 4, 10]]. Initial secret: {0, 1}.

1. Time 5: Meetings {1, 2} and {2, 3}.
2. 1 knows the secret. Since 1 meets 2, 2 now knows. Since 2 meets 3, 3 now knows.
3. Time 10: Meeting {3, 4}.
4. 3 knows the secret from time 5. 3 meets 4, so 4 now knows. Everyone: {0, 1, 2, 3, 4}.

Common mistakes candidates make

• Not sorting by time: Processing meetings in the order given rather than chronologically.
• Ignoring instantaneous spread: Treating meetings as sequential rather than realize that if A meets B and B meets C at the same time, the secret goes A $o$ B $o$ C immediately.
• Failing to reset Union Find: Letting people stay connected across different timestamps, which leads to "time-traveling" secrets.

Interview preparation tip

When dealing with "dynamic connectivity" (connections that only exist at certain times), always process events in time buckets. Union Find is great for this, but remember to "undo" connections that didn't lead to a secret-sharing event.