Snapchat·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Snapchat SWE interview with a classic graph/celebrity problem. Pretty focused session, one meaty algorithmic question with a follow-up on verification logic.

Questions Asked (1)

Given n people labeled 0 to n-1, find the 'celebrity' using an API that tells you whether person A knows person B. A celebrity is known by everyone but knows no one. Solve it in O(n) API calls, or return -1 if no celebrity exists.

Algorithms & Data StructuresAPI & Integrations

Author's notes

The O(n) constraint is what makes this interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-phase elimination strategy: first, find a candidate celebrity by iterating through all people and eliminating anyone who is known by someone else, which takes at most n-1 API calls. Then, verify the candidate by checking that they know no one and everyone knows them, which takes at most 2(n-1) API calls. If verification fails, return -1.

Pro tip: Emphasize that the elimination phase reduces the candidate set to one person in linear time, and the verification phase is crucial to avoid false positives. Mention that the total API calls are bounded by 3n-3, which is O(n).

1. Understand the problem and API

Clarify that the API knows(A, B) returns true if A knows B, and that a celebrity knows no one and is known by everyone. Note that there can be at most one celebrity.

2. Elimination phase to find a candidate

Initialize candidate = 0. For each person i from 1 to n-1, if knows(candidate, i) is true, then candidate cannot be a celebrity (since a celebrity knows no one), so set candidate = i. Otherwise, i cannot be a celebrity (since a celebrity is known by everyone), so keep candidate. This uses n-1 API calls.

3. Verification phase

For the candidate, check that they know no one: for each person i, if knows(candidate, i) is true, return -1. Also check that everyone knows the candidate: for each person i, if i != candidate and knows(i, candidate) is false, return -1. This uses at most 2(n-1) API calls.

4. Return result

If both checks pass, return the candidate as the celebrity. Otherwise, return -1.

5. Analyze complexity and edge cases

Discuss that total API calls are O(n), and handle edge cases like n=0 or n=1. For n=1, the single person is a celebrity by definition (knows no one and is known by everyone vacuously).

Key Points to Mention

At most one celebrity can exist, which justifies the elimination approach.
The elimination phase uses a tournament-style comparison to reduce the candidate set.
Verification is necessary because the elimination only guarantees that the candidate is not known by anyone else, but doesn't guarantee they know no one or are known by everyone.
Total API calls: n-1 for elimination, up to 2(n-1) for verification, so O(n).
Edge cases: n=0 (return -1), n=1 (return 0).
The algorithm is optimal in terms of API calls, as any algorithm must make at least n-1 calls to eliminate n-1 people.

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