Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Google SWE interview with a graph propagation problem that looked straightforward until the same-timestamp grouping requirement came up. The problem has a few classic solution paths but the tricky part is knowing which constraints actually matter.

Questions Asked (1)

Given n people and a list of meetings (person a, person b, time t), where person 0 knows a secret and shares it with one other person at time 0, figure out who knows the secret after all meetings. The catch: meetings at the same timestamp must be processed together as a group before moving on.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The base logic clicked pretty fast for me but I almost missed the grouped-timestamp requirement entirely.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the meetings by timestamp and process them in groups of equal time, using a set to track who knows the secret. For each group, collect all people who will learn the secret from current knowers, then update the set after processing the entire group to avoid spreading within the same timestamp.

Pro tip: Mention that this is essentially a graph reachability problem with time-ordered edges, and that grouping by timestamp prevents incorrect propagation within the same time step. Also, note that using a set for known people gives O(1) lookups and the overall complexity is dominated by sorting, O(m log m).

1. Clarify and restate the problem

Confirm that person 0 initially knows the secret, and that meetings at the same time must be processed as a batch. Ask if the secret spreads transitively within the same timestamp (it should not).

2. Choose data structures

Use a set to track people who know the secret, and sort the meetings by time. Group meetings by equal timestamps using a list of lists or by iterating with a pointer.

3. Process each time group

For each group of meetings at the same time, identify all new people who will learn the secret from current knowers. Collect them in a temporary set, then after processing the entire group, add them to the known set.

4. Return the final set

After all meetings are processed, return the set of people who know the secret. Optionally, convert to a sorted list if needed.

5. Analyze complexity and edge cases

Discuss time complexity: O(m log m) due to sorting, where m is number of meetings; space O(n + m). Mention edge cases: no meetings, multiple meetings at same time, person 0 not in any meeting, etc.

Key Points to Mention

Sorting meetings by timestamp is crucial for correct order.
Grouping by timestamp prevents incorrect propagation within the same time step.
Use a set for O(1) membership checks and updates.
The problem is a variant of graph reachability with time-ordered edges.
Time complexity is O(m log m) due to sorting; space O(n + m).
Edge cases: no meetings, multiple meetings at same time, person 0 not involved.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.