A professional network computes "people you may know" from the connection graph. Some accounts have hundreds of thousands of connections. What breaks?

What the interviewer is testing

Whether you recognise that graph traversal cost is driven by degree distribution, which is extremely skewed in social graphs.

What breaks

Two-hop traversal explodes on high-degree nodes. For a typical user with 500 connections, expanding two hops touches perhaps 250,000 candidates — expensive but bounded. For an account with 300,000 connections, the second hop is astronomically large.

Social graphs follow a heavy-tailed degree distribution, so these accounts are rare and they dominate total computation. A query that is fast for 99% of users can be effectively unbounded for the remainder, and if computation is synchronous those users' requests time out or consume disproportionate resources.

The mitigations

Cap the expansion. Sample or limit connections considered per hop, ordered by a relevance or recency signal rather than arbitrarily. Recommendations do not require exhaustive traversal — they require good candidates.

Precompute rather than traverse at query time. Candidate generation runs offline in batch, producing a bounded candidate set per user which is then ranked at request time. This converts an unbounded traversal into a lookup, and it is the standard approach.

Weight by edge quality. A connection with interaction history is more informative than one without, so expanding only meaningful edges reduces both cost and noise.

Handle high-degree nodes as a distinct case, since they are also less informative — a shared connection with someone who knows 300,000 people says almost nothing about a relationship.

What a strong answer adds

The partitioning consequence: graph data partitioned across nodes makes traversal a distributed operation, and a high-degree node's edges span many partitions, so one hop becomes a scatter-gather. Storing the adjacency list for a node together — and replicating very high-degree nodes — is what keeps traversal affordable.

And the general lesson: degree skew is to graphs what key skew is to partitioned stores. Any algorithm whose cost scales with degree needs an explicit answer for the tail, and the answer is usually to bound it rather than to make it faster.

Common weak answers

A more powerful graph database. Timing out the expensive queries, which denies the feature to exactly the most connected users.