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
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you design a friend suggestion system for a social network?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Friend suggestions are computed as “friends of friends not yet connected” (2nd-degree connections), ranked by number of mutual friends. Algorithm: for each friend F of user U, iterate F’s friends. For each friend-of-friend X: if X is not already U’s friend and X is not U, increment X’s score. After processing all friends, sort candidates by score descending and return top-N. Time complexity: O(D^2) where D = average degree (connections per user). For typical social networks with D=300, this is 90,000 operations per user — acceptable for on-demand computation. For high-scale (LinkedIn, Facebook): precompute suggestions asynchronously. A daily batch job (Spark on the full graph) computes suggestions for all users and stores them in Redis (sorted set per user, score = mutual friend count, TTL=24h). The live API reads from Redis, not the graph database. Refinement signals beyond mutual friends: shared employer/school (LinkedIn), geographic proximity, mutual group membership, profile view history. Blocked users and existing friends are filtered out at the application layer before returning results.”}},{“@type”:”Question”,”name”:”How do you find the shortest path between users in a social graph?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”BFS (Breadth-First Search) finds the shortest path in an unweighted graph. Implementation: start from user A, explore neighbors level by level. Track visited nodes and parent pointers to reconstruct the path. In Python: use a deque, start with [(user_a, [user_a])], and pop from the left. For each neighbor: if it’s the target, return path + [target]. If not visited, add to queue with extended path. Stop when queue is empty (no path exists). LinkedIn’s “degrees of separation” uses this concept. LinkedIn shows 1st (direct connections), 2nd (friends of friends), and 3rd+ degree connections. In practice, at LinkedIn scale (900M users), BFS on the live graph is too slow for real-time. Solutions: (1) BFS limited to 3 degrees (covers ~99.9% of the connected world). (2) Bidirectional BFS: run BFS from both endpoints simultaneously, meeting in the middle. This reduces the search space from O(B^D) to O(B^(D/2)) where B = branching factor and D = path length. (3) Precomputed “common connections” stored in a distributed cache. For the OOP interview, standard BFS with path tracking is the expected answer.”}},{“@type”:”Question”,”name”:”How do you handle blocking in a social network?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Blocking must cascade across multiple systems: (1) Remove existing friendship — if A and B are friends and A blocks B, unfriend both. (2) Cancel pending requests — if A has a pending request to B or vice versa, cancel it. (3) Prevent future requests — any attempt by A to send a request to B (or B to A) should fail silently. (4) Hide from suggestions — neither user should appear in the other’s friend suggestions. (5) Hide content — A’s posts should not appear in B’s feed and vice versa (feed filtering layer). (6) Block is one-directional by default: A blocking B means A doesn’t see B, but B can still see A’s public content (unless they also block). Some platforms (Twitter mute vs block) distinguish between hiding someone’s content and preventing all interaction. Implementation: store a block list per user (dict[str, set[str]]). Check before every interaction: request send, suggestion generation, feed assembly. In a production system, store blocks in a separate “block” table with indexed lookups. Denormalize frequently: cache the block list in Redis (SADD blocked:{user_id}, member) for O(1) SISMEMBER checks in hot paths like feed assembly.”}}]}
🏢 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