How should I practice Versioned Social Network?

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

Is Versioned Social Network associated with OpenAI?

FastPrep tags this as a OpenAI coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Design

Versioned Social Network

Learn this problem

● HardOpenAIFULLTIMEONSITE INTERVIEW

Problem statement

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

Relationships change over time. The network can create immutable snapshots and later answer whether a relationship existed at a particular snapshot. A snapshot must not copy the entire graph. Instead, keep a history of changes for each directed relationship.

Every snapshot includes all preceding updates. Later updates never change an earlier snapshot. If the same relationship changes more than once before the next snapshot, that snapshot records its state after the last such change.

Operations

Process the commands in order:

FOLLOW u v: add the directed relationship u -> v. The relationship is guaranteed to be inactive immediately before this command.
UNFOLLOW u v: remove the directed relationship u -> v. The relationship is guaranteed to be active immediately before this command.
SNAPSHOT: save the current network state. Snapshot IDs start at 0 and increase by 1. Append the new ID to the output.
IS_FOLLOWING u v snapshot_id: append true if u followed v when that snapshot was created; otherwise append false. A relationship that had not yet been followed is inactive.

Only SNAPSHOT and IS_FOLLOWING produce output. Return their outputs in command order as strings.

Performance Requirements

FOLLOW, UNFOLLOW, and SNAPSHOT must each run in expected O(1) time. A historical query for one relationship must run in O(log h) time, where h is the number of recorded changes for that relationship. The total auxiliary space must be O(c), where c is the number of follow and unfollow commands.

Further Interview Stages

The reports also described listing relationships at a snapshot, recommending friends, and comparing two snapshots. The exact recommendation rule and snapshot-difference output were not provided.

Function

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

Examples

Example 1

n = 4operations = ["FOLLOW 0 1", "FOLLOW 0 2", "SNAPSHOT", "UNFOLLOW 0 1", "SNAPSHOT", "IS_FOLLOWING 0 1 0", "IS_FOLLOWING 0 1 1", "IS_FOLLOWING 0 2 1"]return = ["0", "1", "true", "false", "true"]

Snapshot 0 contains both relationships from user 0. Snapshot 1 is created after 0 unfollows 1, while the relationship 0 -> 2 remains active.

Example 2

n = 3operations = ["FOLLOW 1 2", "UNFOLLOW 1 2", "FOLLOW 1 0", "SNAPSHOT", "IS_FOLLOWING 1 2 0", "IS_FOLLOWING 1 0 0"]return = ["0", "false", "true"]

Both changes to 1 -> 2 occur before the first snapshot, so its final state in snapshot 0 is inactive. The relationship 1 -> 0 is active.

Example 3

n = 3operations = ["SNAPSHOT", "FOLLOW 2 1", "SNAPSHOT", "UNFOLLOW 2 1", "FOLLOW 2 1", "SNAPSHOT", "IS_FOLLOWING 2 1 0", "IS_FOLLOWING 2 1 1", "IS_FOLLOWING 2 1 2"]return = ["0", "1", "2", "false", "true", "true"]

The relationship is absent in snapshot 0 and present in snapshot 1. It is removed and restored before snapshot 2, so its snapshot 2 state is active.

Constraints

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