Openai·Software Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Got a system design question at OpenAI for a software engineer role, centered on building a friend recommendation feature similar to what you'd see on any major social platform. Pretty classic graph traversal problem but the scoring and complexity discussion is where it gets interesting.

Questions Asked (1)

Given a social network graph and a target user X, design a system to recommend the top K second-degree connections (friends-of-friends) that X doesn't already follow. The score for each candidate is the number of mutual first-degree connections with X. Walk through your approach including traversal strategy, scoring, ranking, and complexity analysis.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I started with BFS up to depth 2 which felt right, but I fumbled a bit explaining why BFS over DFS here.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints (graph size, degree distribution, memory limits) and then propose a two-hop traversal from X to collect candidates, scoring each by mutual connections. Discuss trade-offs between BFS/DFS, in-memory vs. distributed processing, and use a min-heap to efficiently maintain top K. Conclude with complexity analysis and potential optimizations for large-scale graphs.

Pro tip: Mention that in real social networks, the number of second-degree connections can be huge, so you'd likely need to cap the traversal or use approximate algorithms; also highlight that mutual connection count can be computed via set intersection of neighbor lists, which is efficient if neighbor lists are sorted or stored as hash sets.

1. Clarify requirements and constraints

Ask about graph size, average degree, memory limits, and whether the graph is static or dynamic. Confirm that the score is exactly the number of mutual first-degree connections and that we need the top K candidates.

2. Choose traversal strategy

Decide between BFS or DFS for exploring second-degree connections. BFS is natural for level-by-level exploration, but for large graphs, you might limit the traversal to a subset of X's neighbors or use sampling.

3. Score candidates efficiently

For each candidate, compute mutual connections by intersecting X's neighbor set with the candidate's neighbor set. Use hash sets for O(1) lookups or sorted lists for merge-based intersection.

4. Rank and select top K

Use a min-heap of size K to keep the top K candidates by score, updating as you traverse. This avoids sorting all candidates and gives O(N log K) time where N is number of candidates.

5. Analyze complexity and discuss optimizations

Derive time and space complexity: O(deg(X) * avg_deg) for traversal and scoring, plus O(N log K) for heap operations. Discuss optimizations like pruning low-degree neighbors, parallelization, or using approximate counting for very large graphs.

Key Points to Mention

Graph representation: adjacency list vs. adjacency matrix, and why adjacency list is preferred for sparse social graphs.
Traversal strategy: BFS from X to depth 2, but avoid revisiting X's direct neighbors and X itself.
Scoring: mutual connections = |neighbors(X) ∩ neighbors(candidate)|, computed via set intersection.
Top-K selection: min-heap of size K to maintain top candidates without full sort.
Complexity: time O(deg(X) * avg_deg + N log K), space O(N) for candidates and O(K) for heap.
Scalability: distributed processing (e.g., MapReduce) or approximate algorithms for massive graphs.

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