Problem Statement
Design a social network graph system like LinkedIn’s connection model or Facebook’s friends graph. Users can send friend requests, accept or reject them, view their friends, get mutual friends with another user, and get friend suggestions (friends of friends not yet connected). The system must efficiently handle large graphs (millions of users, thousands of connections per user).
Core Entities
from dataclasses import dataclass, field
from datetime import datetime
from enum import Enum
from typing import Optional
import uuid
class FriendshipStatus(Enum):
PENDING = "pending" # Request sent, not yet accepted
ACCEPTED = "accepted"
REJECTED = "rejected"
BLOCKED = "blocked"
@dataclass
class User:
user_id: str
name: str
email: str
bio: str = ""
created_at: datetime = field(default_factory=datetime.now)
@dataclass
class FriendRequest:
request_id: str = field(default_factory=lambda: str(uuid.uuid4())[:8])
sender_id: str = ""
receiver_id: str = ""
status: FriendshipStatus = FriendshipStatus.PENDING
created_at: datetime = field(default_factory=datetime.now)
updated_at: datetime = field(default_factory=datetime.now)
Social Graph
from collections import defaultdict, deque
class SocialGraph:
def __init__(self):
self._users: dict[str, User] = {}
# Adjacency list: user_id -> set of friend_ids (accepted connections)
self._friends: dict[str, set[str]] = defaultdict(set)
# Pending requests: (sender_id, receiver_id) -> FriendRequest
self._requests: dict[tuple[str,str], FriendRequest] = {}
# Block list: user_id -> set of blocked user_ids
self._blocked: dict[str, set[str]] = defaultdict(set)
def add_user(self, user: User):
self._users[user.user_id] = user
def send_friend_request(self, sender_id: str,
receiver_id: str) -> Optional[FriendRequest]:
if sender_id == receiver_id:
print("Cannot send request to yourself"); return None
if receiver_id in self._blocked.get(sender_id, set()):
print("You have blocked this user"); return None
if sender_id in self._blocked.get(receiver_id, set()):
print("You have been blocked by this user"); return None
if receiver_id in self._friends[sender_id]:
print("Already friends"); return None
if (sender_id, receiver_id) in self._requests:
print("Request already sent"); return None
# Handle reverse pending request
if (receiver_id, sender_id) in self._requests:
existing = self._requests[(receiver_id, sender_id)]
if existing.status == FriendshipStatus.PENDING:
return self.accept_friend_request(receiver_id, sender_id)
request = FriendRequest(sender_id=sender_id,
receiver_id=receiver_id)
self._requests[(sender_id, receiver_id)] = request
print(f"Friend request sent: {sender_id} -> {receiver_id}")
return request
def accept_friend_request(self, sender_id: str,
receiver_id: str) -> Optional[FriendRequest]:
"""receiver_id accepts the request from sender_id."""
request = self._requests.get((sender_id, receiver_id))
if not request or request.status != FriendshipStatus.PENDING:
print("No pending request found"); return None
# Bidirectional friendship
self._friends[sender_id].add(receiver_id)
self._friends[receiver_id].add(sender_id)
request.status = FriendshipStatus.ACCEPTED
request.updated_at = datetime.now()
print(f"Friendship established: {sender_id} {receiver_id}")
return request
def reject_friend_request(self, sender_id: str,
receiver_id: str) -> bool:
request = self._requests.get((sender_id, receiver_id))
if not request or request.status != FriendshipStatus.PENDING:
return False
request.status = FriendshipStatus.REJECTED
request.updated_at = datetime.now()
return True
def unfriend(self, user_a: str, user_b: str) -> bool:
if user_b not in self._friends[user_a]:
return False
self._friends[user_a].discard(user_b)
self._friends[user_b].discard(user_a)
print(f"Unfriended: {user_a} and {user_b}")
return True
def block_user(self, blocker_id: str, blocked_id: str):
self._blocked[blocker_id].add(blocked_id)
# Remove friendship if it exists
self.unfriend(blocker_id, blocked_id)
# Remove any pending requests between them
self._requests.pop((blocker_id, blocked_id), None)
self._requests.pop((blocked_id, blocker_id), None)
def get_friends(self, user_id: str) -> list[User]:
return [self._users[uid] for uid in self._friends[user_id]
if uid in self._users]
def get_mutual_friends(self, user_a: str, user_b: str) -> list[User]:
"""Return friends common to both user_a and user_b."""
mutual_ids = self._friends[user_a] & self._friends[user_b]
return [self._users[uid] for uid in mutual_ids
if uid in self._users]
def get_friend_suggestions(self, user_id: str,
max_suggestions: int = 10) -> list[tuple[User, int]]:
"""
Suggest friends-of-friends not already connected.
Returns (user, mutual_friend_count) sorted by mutual count descending.
"""
my_friends = self._friends[user_id]
blocked = self._blocked.get(user_id, set())
scores: dict[str, int] = {}
for friend_id in my_friends:
for fof_id in self._friends[friend_id]:
if (fof_id == user_id
or fof_id in my_friends
or fof_id in blocked
or friend_id in self._blocked.get(fof_id, set())):
continue
scores[fof_id] = scores.get(fof_id, 0) + 1
# Sort by mutual friend count descending
ranked = sorted(scores.items(), key=lambda x: x[1], reverse=True)
return [(self._users[uid], count)
for uid, count in ranked[:max_suggestions]
if uid in self._users]
def shortest_path(self, user_a: str, user_b: str) -> list[str]:
"""BFS to find the shortest connection path between two users."""
if user_a == user_b:
return [user_a]
visited = {user_a}
queue = deque([(user_a, [user_a])])
while queue:
curr, path = queue.popleft()
for neighbor in self._friends[curr]:
if neighbor == user_b:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return [] # Not connected
def degree_of_connection(self, user_a: str, user_b: str) -> int:
"""Return degrees of separation (-1 if not connected)."""
path = self.shortest_path(user_a, user_b)
return len(path) - 1 if path else -1
def are_friends(self, user_a: str, user_b: str) -> bool:
return user_b in self._friends[user_a]
Usage Example
def demo():
graph = SocialGraph()
users = [
User("U1", "Alice", "alice@email.com"),
User("U2", "Bob", "bob@email.com"),
User("U3", "Carol", "carol@email.com"),
User("U4", "David", "david@email.com"),
User("U5", "Eve", "eve@email.com"),
]
for u in users:
graph.add_user(u)
# Build social graph
graph.send_friend_request("U1", "U2")
graph.accept_friend_request("U1", "U2") # Alice-Bob friends
graph.send_friend_request("U2", "U3")
graph.accept_friend_request("U2", "U3") # Bob-Carol friends
graph.send_friend_request("U3", "U4")
graph.accept_friend_request("U3", "U4") # Carol-David friends
graph.send_friend_request("U2", "U5")
graph.accept_friend_request("U2", "U5") # Bob-Eve friends
# Mutual friends between Alice and Carol (via Bob)
mutuals = graph.get_mutual_friends("U1", "U3")
print(f"Mutual friends Alice-Carol: {[u.name for u in mutuals]}") # [Bob]
# Suggestions for Alice (friends-of-friends: Carol, Eve)
suggestions = graph.get_friend_suggestions("U1")
for user, count in suggestions:
print(f" Suggest: {user.name} ({count} mutual friends)")
# Degrees of separation: Alice to David = 3 (Alice→Bob→Carol→David)
path = graph.shortest_path("U1", "U4")
print(f"Path Alice→David: {path}")
print(f"Degrees: {graph.degree_of_connection('U1', 'U4')}")
demo()
Design Decisions
- Bidirectional adjacency list: Both users store each other’s ID. Lookup “is X a friend of Y?” is O(1). friends(user) is O(degree). For LinkedIn’s 500+ connections per user, sets are fast.
- Friend suggestions by mutual count: O(friends × friends_of_friends) — acceptable for typical social graphs where degrees are bounded. At scale: precompute suggestions offline (Spark job), store in a Redis sorted set per user, update hourly.
- BFS for degrees: LinkedIn’s “2nd connections” feature uses BFS up to 2 levels. “6 degrees of separation” is 6-level BFS across the full graph — impractical to run live; precomputed with distributed graph processing (Apache Giraph, Spark GraphX).
- Block list: Checked on request send and suggestion generation. Bidirectional: if A blocks B, neither can request the other and neither appears in the other’s suggestions.
Interview Checklist
- Data structure: adjacency list (dict of sets) for O(1) friend check and O(degree) enumeration
- Friendship states: PENDING, ACCEPTED, REJECTED, BLOCKED
- Mutual friends: set intersection O(min(|friends_A|, |friends_B|))
- Suggestions: friends-of-friends ranked by mutual count
- Shortest path: BFS, return path not just distance
- Blocking: remove friendship + prevent future requests + hide from suggestions
- Production: graph database (Neo4j, Amazon Neptune) for deep traversals; denormalized Redis sets for hot path queries
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: LinkedIn Interview Guide 2026: Social Graph Engineering, Feed Ranking, and Professional Network Scale
🏢 Asked at: Twitter / X Interview Guide 2026: Real-Time Systems, Feed Architecture, and Platform Engineering
🏢 Asked at: Snap Interview Guide
🏢 Asked at: Airbnb Interview Guide 2026: Search Systems, Trust and Safety, and Full-Stack Engineering