Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE interview with a graph problem that looks straightforward but has a neat trick buried in it. The solution clicked eventually but I spent way too long thinking about it the wrong way first.

Questions Asked (1)

You have n players with unique hidden rankings from 1 to n. A higher-ranked player always beats a lower-ranked one. Given a list of match results, find every player whose exact rank can be determined, and return their ranks.

Algorithms & Data Structures

Author's notes

My first instinct was to try topological sort and I kept going down that path longer than I should have.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the match results as a directed graph where an edge from A to B means A beats B. The exact rank of a player is determined if and only if the number of players known to be stronger and the number known to be weaker sum to n-1. Use transitive closure (e.g., Floyd-Warshall) to compute all reachability, then for each player count stronger and weaker players.

Pro tip: Mention that this problem is equivalent to finding vertices with a unique position in the total order, and that the condition (stronger + weaker == n-1) is both necessary and sufficient. Also note that the graph is a DAG and transitive closure can be computed efficiently with bitsets for large n.

1. Model as a directed graph

Create a directed graph where each player is a node, and a directed edge from u to v indicates that u beats v. This captures the known dominance relations.

2. Compute transitive closure

Use Floyd-Warshall or bitset-based reachability to determine all pairs (u, v) such that u is known to be stronger than v (directly or indirectly).

3. Count stronger and weaker players

For each player, count the number of players known to be stronger (incoming reachability) and weaker (outgoing reachability).

4. Determine exact ranks

A player's exact rank is determined if and only if stronger + weaker == n - 1. The rank is then stronger + 1.

5. Collect and return ranks

Gather the ranks of all such players and return them in any order (or sorted if required).

Key Points to Mention

The problem reduces to finding vertices with a unique position in the total order based on partial information.
Transitive closure is necessary because indirect dominance relations also constrain ranks.
The condition stronger + weaker == n - 1 is both necessary and sufficient for an exact rank.
Time complexity: O(n^3) with Floyd-Warshall, or O(n^3/word_size) with bitsets; space O(n^2).
The graph is a DAG, so no cycles; topological sorting can be used as an alternative perspective.
Edge cases: no matches, all matches, or disconnected components; handle n=1.

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