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 Follow Recommendations

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an in-memory social network graph with three operations: - `follow(followerId, followeeId)`: record that one user follows another user. Duplicate follows should not create duplicate edges. Self-follow can be ignored or rejected, but state your choice. - `unfollow(followerId, followeeId)`: remove the follow edge if it exists. Removing a non-existent edge should be a no-op. - `recommend(userId, k)`: return up to `k` recommended users using a friend-of-friend rule. A candidate is any user followed by someone that `userId` follows. Exclude `userId` and users already followed by `userId`. Rank recommendations by the number of distinct intermediate users that connect `userId` to the candidate. Break ties deterministically, for example by smaller user id or lexicographic order. Discuss the data structures you would use and the time complexity of each operation.

Quick Answer: This question evaluates graph data structure design and traversal, set-based aggregation and ranking logic, and the ability to justify data structure choices with time and space complexity analysis.

You are given a sequence of operations for an initially empty in-memory social network graph. Each directed edge `A -> B` means user `A` follows user `B`. Implement these rules: - `follow(followerId, followeeId)`: add the directed follow edge. Duplicate follows must not create duplicate edges. - `unfollow(followerId, followeeId)`: remove the edge if it exists. If it does not exist, do nothing. - `recommend(userId, k)`: return up to `k` recommended user IDs using a friend-of-friend rule. For `recommend(userId, k)`: - A candidate is any user followed by someone that `userId` already follows. - Exclude `userId` themself. - Exclude users already followed by `userId`. - Rank candidates by the number of distinct intermediate users that connect `userId` to the candidate, in descending order. - Break ties by smaller user ID first. In this problem, self-follow operations are ignored. Write a function that processes all queries in order and returns the results of every `recommend` query, in the same order they appear. An efficient approach should use hash-based adjacency sets so that `follow` and `unfollow` are fast, while `recommend` counts how many followed intermediates point to each candidate.

Constraints

1 <= len(queries) <= 20000
1 <= userId, followerId, followeeId <= 10^9
0 <= k <= 10000
Duplicate follow operations must not create duplicate edges
Self-follow operations are ignored
Removing a non-existent edge is a no-op

Examples

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

Expected Output: [[4, 5, 6]]

Explanation: User 1 follows 2 and 3. Candidate 4 is reached through both 2 and 3, so it has score 2. Candidates 5 and 6 each have score 1, so tie-breaking by smaller ID gives [4, 5, 6].

Input: [('follow', 1, 1), ('follow', 1, 2), ('follow', 1, 2), ('follow', 2, 1), ('follow', 2, 3), ('recommend', 1, 5), ('unfollow', 1, 4), ('unfollow', 1, 2), ('recommend', 1, 5)]

Expected Output: [[3], []]

Explanation: Self-follow is ignored and duplicate follows do not matter. First, user 1 follows only 2, and 2 follows 3, so recommendation is [3]. Unfollowing a non-existent edge does nothing. After user 1 unfollows 2, user 1 follows nobody, so there are no candidates.

Input: [('follow', 10, 20), ('follow', 10, 30), ('follow', 20, 40), ('follow', 20, 50), ('follow', 30, 50), ('follow', 30, 60), ('follow', 30, 40), ('recommend', 10, 2)]

Expected Output: [[40, 50]]

Explanation: Candidates 40 and 50 each have score 2 because both are reached through 20 and 30. Candidate 60 has score 1. With k = 2, return the top two, breaking the tie by smaller ID: [40, 50].

Input: [('follow', 1, 2), ('follow', 1, 3), ('follow', 2, 3), ('follow', 2, 4), ('follow', 3, 4), ('recommend', 1, 10)]

Expected Output: [[4]]

Explanation: Candidate 3 is excluded because user 1 already follows 3. Candidate 4 is reached through both 2 and 3, so it is the only recommendation.

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

Expected Output: [[]]

Explanation: When k is 0, the recommendation result must be an empty list even if candidates exist.

Hints

Store the graph as a hash map from user ID to a set of followees so that follow, unfollow, and membership checks are efficient.
For a recommendation query, iterate through the user's direct followees, count how many distinct intermediates reach each candidate, then sort by `(-count, userId)`.

Quick Overview

This question evaluates graph data structure design and traversal, set-based aggregation and ranking logic, and the ability to justify data structure choices with time and space complexity analysis.