Katkat
Back

Design follow/follower classes

UberSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a system for managing directed relationships between users, requiring careful selection of data structures to balance write performance and query latency.

Problem Statement

Design a social graph system that tracks 'following' relationships. You are tasked with creating a class or set of classes that manage users and their connections.

Requirements

  1. follow(follower_id, followee_id): Creates a directed edge from follower_id to followee_id. If the relationship already exists, do nothing (idempotent).
  2. unfollow(follower_id, followee_id): Removes the directed edge. If the relationship does not exist, do nothing.
  3. get_following(user_id): Returns a list of all users user_id follows.
  4. get_followers(user_id): Returns a list of all users who follow user_id.
  5. is_following(follower_id, followee_id): Returns a boolean indicating if the relationship exists.

Constraints

  • User IDs are positive integers.
  • The system must handle millions of users and billions of relationships.
  • Operations should ideally be faster than O(N), where N is the number of total users.

Examples

social = SocialGraph()
social.follow(1, 2)
social.follow(1, 3)
social.follow(2, 1)

print(social.get_following(1)) # Output: [2, 3]
print(social.get_followers(1)) # Output: [2]
print(social.is_following(1, 2)) # Output: True

Edge Cases

  • Users following themselves (self-loops).
  • Attempting to unfollow a non-existent relationship.
  • High-frequency calls for 'celebrity' users with millions of followers.

Hints

Hint 1

Consider using two separate HashMaps or HashSets to store 'following' (outbound) and 'followers' (inbound) relationships for each user.

Hint 2

Using a Set instead of a List for storage will allow O(1) average time complexity for both checking existence and removing relationships.

Hint 3

Think about how to handle data consistency if this were to scale across multiple servers or a distributed database.

Follow-up questions

  • How would your design change if you needed to support 'Mutual Following' checks very frequently?
  • If 'celebrity' users have millions of followers, how would you optimize the `get_followers` operation to avoid memory issues?
  • How would you persist this data in a database (e.g., SQL vs. NoSQL) to handle failures and potential restarts?