How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement Social Graph Snapshot Queries

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a read-only snapshot of a social network. The snapshot is represented as a directed graph where an edge `(u, v)` means user `u` follows user `v`. Implement a data structure or set of functions that supports the following operations efficiently: 1. `follows(a, b)` -> return whether user `a` follows user `b` in this snapshot. 2. `followers(user)` and `followees(user)` -> return the list of users who follow `user`, and the list of users that `user` follows. 3. `recommend(user, k)` -> return the top `k` recommended users for `user` based on second-degree connections. For the recommendation query: - A candidate is a user reachable by exactly two follow steps: `user -> x -> candidate`. - Exclude the user themself. - Exclude users already directly followed by `user`. - If the same candidate is reached through multiple intermediate users, rank that candidate higher. - Break ties by smaller user id first. You may assume the graph snapshot is static after construction, and there can be many queries after the snapshot is loaded. Describe the expected time and space complexity of your approach.

Quick Answer: This question evaluates understanding of graph data structures, query-efficient indexing, and algorithmic trade-offs for static directed graphs, including handling neighborhood queries and recommendation ranking based on second-degree connections.

You are given a static snapshot of a social network with users labeled from 0 to n-1. The snapshot is a directed graph where an edge (u, v) means user u follows user v. Implement a function `solution(n, edges, queries)` that builds the snapshot once and answers many queries efficiently. Each query is one of the following: - `('follows', a, b)`: return whether user `a` follows user `b`. - `('followers', user)`: return the list of users who follow `user`, sorted in ascending order. - `('followees', user)`: return the list of users that `user` follows, sorted in ascending order. - `('recommend', user, k)`: return up to `k` recommended users for `user`. Recommendation rules: - A candidate must be reachable by exactly two follow steps: `user -> x -> candidate`. - Exclude the user themself. - Exclude users already directly followed by `user`. - If the same candidate is reached through multiple different intermediate users `x`, that candidate ranks higher. - Break ties by smaller user id first. - Return only the user ids, in ranked order. The graph is read-only after construction. Duplicate edges may appear in the input and should be treated as a single follow relationship.

Constraints

1 <= n <= 100000
0 <= len(edges) <= 200000
0 <= len(queries) <= 100000
0 <= u, v, user, a, b < n
0 <= k <= n
Duplicate edges should be ignored

Examples

Input: (6, [(0, 1), (0, 2), (1, 3), (2, 3), (2, 4), (4, 5)], [('follows', 0, 1), ('followers', 3), ('followees', 2), ('recommend', 0, 3)])

Expected Output: [True, [1, 2], [3, 4], [3, 4]]

Explanation: 0 follows 1. Users 1 and 2 follow 3. User 2 follows 3 and 4. For recommendations from 0, the two-step candidates are 3 (through 1 and 2) and 4 (through 2), so 3 ranks above 4.

Input: (5, [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (1, 4), (2, 4), (2, 0)], [('recommend', 0, 5), ('follows', 2, 0), ('followers', 0), ('followees', 0)])

Expected Output: [[3, 4], True, [2], [1, 2]]

Explanation: For user 0, candidate 2 is reachable in two steps but is already directly followed, so it is excluded. Users 3 and 4 are each reached through both 1 and 2, and tie-break by smaller id gives [3, 4].

Input: (4, [], [('follows', 0, 1), ('followers', 2), ('followees', 3), ('recommend', 1, 2)])

Expected Output: [False, [], [], []]

Explanation: With no edges, nobody follows anyone and there are no second-degree recommendations.

Input: (6, [(0, 1), (0, 1), (0, 2), (1, 3), (1, 4), (2, 3), (2, 5), (2, 5), (4, 5)], [('followers', 1), ('recommend', 0, 1), ('recommend', 0, 3)])

Expected Output: [[0], [3], [3, 4, 5]]

Explanation: Duplicate edges are ignored. User 0 reaches 3 through both 1 and 2, while 4 and 5 are each reached once, so the ranking is 3 first, then 4 and 5 by user id.

Input: (3, [(0, 1), (1, 2)], [('recommend', 0, 0), ('recommend', 0, 5), ('follows', 0, 2)])

Expected Output: [[], [2], False]

Explanation: When k = 0, return an empty list. With a larger k, user 2 is the only valid two-step recommendation for user 0. User 0 does not directly follow 2.

Hints

Store each user's outgoing neighbors in a hash set so `follows(a, b)` and recommendation exclusions are fast.
Also build the reverse graph for `followers(user)`, and for `recommend(user, k)` count second-degree candidates with a hash map before sorting by `(-count, user_id)`.

Quick Overview

This question evaluates understanding of graph data structures, query-efficient indexing, and algorithmic trade-offs for static directed graphs, including handling neighborhood queries and recommendation ranking based on second-degree connections.