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:
-
follows(a, b)
-> return whether user
a
follows user
b
in this snapshot.
-
followers(user)
and
followees(user)
-> return the list of users who follow
user
, and the list of users that
user
follows.
-
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.