How should I practice Versioned Followers and Followees?

Start by reading the full statement, solve the visible examples, then compare the pattern against related OpenAI phone screen problems in FastPrep.

Is Versioned Followers and Followees associated with OpenAI?

FastPrep tags this as a OpenAI phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Design

Versioned Followers and Followees

Learn this problem

● Medium

OpenAIFULLTIMEPHONE SCREEN

Problem statement

A directed social graph has n users numbered from 0 to n - 1. A relationship u -> v means that user u follows user v.

Process a finite sequence of relationship updates, immutable snapshots, and historical list queries. Every snapshot includes all earlier updates. Later updates never change an earlier snapshot.

Operations

FOLLOW u v activates u -> v. The relationship is inactive immediately before the command.
UNFOLLOW u v deactivates u -> v. The relationship is active immediately before the command.
SNAPSHOT creates the next snapshot. IDs start at 0. Append the ID as a decimal string.
GET_FOLLOWERS user snapshot_id appends all users who followed user at that snapshot.
GET_FOLLOWEES user snapshot_id appends all users whom user followed at that snapshot.

Serialize each relationship list as a string containing ascending user IDs inside brackets, separated by commas and no spaces. Serialize an empty list as []. Only SNAPSHOT, GET_FOLLOWERS, and GET_FOLLOWEES produce output. Return those strings in command order.

Historical Storage

For this exercise, assume each directed relationship is stored as a change history and the whole graph is not copied for each snapshot. Use that authored history model to answer snapshot queries.

Function

getVersionedRelationships(n: int, operations: String[]) → String[]

Examples

Example 1

n = 4operations = ["FOLLOW 0 1","FOLLOW 2 1","SNAPSHOT","GET_FOLLOWERS 1 0","GET_FOLLOWEES 0 0"]return = ["0","[0,2]","[1]"]

At snapshot 0, users 0 and 2 follow user 1. User 0 follows only user 1.

Example 2

n = 3operations = ["SNAPSHOT","GET_FOLLOWERS 1 0","FOLLOW 0 1","FOLLOW 0 2","SNAPSHOT","GET_FOLLOWEES 0 0","GET_FOLLOWEES 0 1"]return = ["0","[]","1","[]","[1,2]"]

Snapshot 0 is empty. The two later follows appear in snapshot 1 without changing snapshot 0.

Example 3

n = 5operations = ["FOLLOW 0 2","SNAPSHOT","FOLLOW 1 2","UNFOLLOW 0 2","FOLLOW 0 3","SNAPSHOT","GET_FOLLOWERS 2 0","GET_FOLLOWERS 2 1","GET_FOLLOWEES 0 1"]return = ["0","1","[0]","[1]","[3]"]

User 0 follows 2 in snapshot 0. Before snapshot 1, user 1 follows 2, while user 0 replaces that relationship with 0 -> 3.

Constraints

1 <= n <= 2000
1 <= operations.length <= 20000
0 <= u, v, user < n and u != v
Every FOLLOW targets an inactive relationship.
Every UNFOLLOW targets an active relationship.
Every list query references a snapshot that has already been created.
Commands contain single spaces between tokens.
At least one command produces output.