Notes
Requirements
Fix the scope. Each user has a profile. Friendship needs a request that the other person accepts or declines, while following is one-sided and needs no approval. Posts can be public, friends only, or only me. Anyone who can see a post can like it once or comment. The news feed shows recent posts from friends and followed people, newest first, a page at a time. We also need notifications, blocking, search by name, mutual friends and degrees of connection.
Ask the questions that shape the code. If two people send each other a request, treat it as accepted. Sending twice still makes one request. Friends see friends-only posts, but followers only see public ones. Blocking removes the friendship and follows, and hides both people from each other everywhere. The feed is in time order for now; ranking comes later. Groups, pages, messaging and photo uploads are out of scope.
- profile: name, headline
- friend request: send, accept,
- decline
- follow without approval
- post: public, friends, only me
- like once, comment
- news feed: newest first, paged
- notifications
- block a user
- search people by name
- mutual friends, 1st/2nd/3rd
- both send a request at once?
- treat it as accepted
- request twice? still one
- friends see friends-only posts
- followers do not
- block: unfriend, unfollow,
- hide each other everywhere
- feed: time order, not ranked
- ranking is an extension
- out of scope: groups, pages,
- messaging, media upload
Entities
Underline the nouns: user, profile, friend request, post, comment, like, feed. A user owns its profile fields and four sets of ids: friends, people they follow, followers, and people they blocked. A friend request has a sender, a receiver and a status. A post has an author, text, a visibility and a time, plus a set of likers and a list of comments. A like is not a class at all: it is just a user id inside the post's like set.
Class diagram
Here are the types. Users point at each other by id, never by object, so the graph is just sets of numbers that are cheap to copy and easy to store in a database later. Each set is a concurrent set. A user's posts are an append-only list, oldest first, which the feed will walk backwards. A post's likes are a set of user ids, which makes one like per user true by construction. A request holds its status in an atomic reference.
class User {
final long id; final String name;
Set<Long> friends, following,
followers, blocked;
List<Post> posts; // oldest first
}
class Post { id, authorId, text,
Visibility v, Instant at,
Set<Long> likes, List<Comment> }
class FriendRequest { from, to,
AtomicReference<RequestStatus> } Flow: friend request
Walk the friend request flow. Sending rejects yourself, a blocked user, or an existing friend. If the other person already sent you a request, we simply accept theirs. Otherwise we put the request in a map keyed by sender and receiver with put if absent, so a double click still makes one request. To answer, only the receiver may respond, and a compare and set from pending to accepted or declined means a request is answered exactly once.
reject self, blocked, already friends
reverse request open? accept it
openRequests.putIfAbsent(pair, r)
// a double click sends one
respond(user, id, accept):
only the receiver may answer
status.compareAndSet(PENDING, next)
or throw: already answered
if accepted: link both users Friend lists
Friendship is mutual, so both sets must change together. If Asha accepts Ben while Ben blocks Asha, we must not end with Asha listing Ben and Ben not listing Asha. So every change to a pair takes both users' locks. Two threads locking Asha then Ben and Ben then Asha could deadlock, so we always lock the lower id first. One fixed lock order is the classic, simple cure for deadlock, and it is worth saying out loud.
User first = a.id < b.id ? a : b;
User second = first == a ? b : a;
synchronized (first) {
synchronized (second) {
a.friends.add(b.id);
b.friends.add(a.id);
}
}
unfriend and block use the same
ordering: no deadlock Privacy
Privacy lives in exactly one method: can view. The author always sees their own post. A block in either direction hides it. Otherwise a public post is visible to everyone, a friends post only to the author's friends, and an only me post to nobody else. The feed, likes and comments all call this one method. If each feature wrote its own check, one of them would eventually forget, and that is how private posts leak.
if (post.authorId == viewer) return true;
if (blockedEitherWay(..)) return false;
return switch (post.visibility) {
case PUBLIC -> true;
case FRIENDS -> author.friends
.contains(viewer);
case ONLY_ME -> false;
}; News feed: k-way merge
Now the news feed. We use the pull model: build the feed when the user opens the app. The sources are friends, people they follow, and themselves, minus anyone blocked. Each author's posts are already in time order. So this is the classic merge of k sorted lists. Put one cursor per author, pointing at their newest post, into a max heap ordered by time. Poll the newest, keep it if the viewer may see it, step that cursor back, and push it again until the page is full.
- sources: friends + following
- + me, minus blocked
- each author: posts oldest first
- one cursor per author at the
- newest post
- max-heap ordered by the cursor
- post time
- poll newest, add if canView,
- step that cursor back, re-add
- stop after one page
Flow: read the feed
Here is the read in code. For each source, find the newest post older than the page cursor and add a cursor to the heap. Then poll, filter with can view, step back and re-add, until the page is full. With k authors and a page of n posts, that is about n log k work after setup, not a sort of everything. The last post returned becomes the cursor for the next page, so scrolling down never repeats or skips a post, even if new posts arrive meanwhile.
for each source author:
i = last index older than before
if (i >= 0) heap.add(new Cursor(..))
while (out.size() < limit) {
Cursor c = heap.poll();
if (canView(viewer, c.head()))
out.add(c.head());
if (c.stepBack()) heap.add(c);
}
return page + last post as cursor Pull vs push
Know the trade-off, because it is the most common follow-up. Pull, which we built, does the work when someone reads: writes are cheap, reads do a merge. Push copies each new post id into every follower's feed list when it is written: reads are instant, but an account with millions of followers makes every post very expensive. Large systems use a hybrid: push for normal users, pull for very popular accounts, and merge the two at read time.
- pull (fan-out on read):
- merge at read time
- cheap writes, slower reads
- push (fan-out on write):
- copy each post id into every
- follower's feed list
- fast reads, costly for stars
- hybrid: push for most authors,
- pull for very popular ones
Likes and comments
Likes are simple once a like is a set entry. Check can view first. Adding the user id to the concurrent like set returns true only for the first add, so a double click, or two devices tapping at once, still counts one like, and only the first one sends a notification to the author. Unlike removes the id. Comments are immutable records in a copy-on-write list, and each new comment notifies the post's author.
if (!canView(user, post)) throw boolean added = post.likes.add(user); if (added && user != post.authorId) publish(LIKE to the author); return post.likes.size(); comments: CopyOnWriteArrayList of Comment records
Observer: notifications
Notifications use the Observer pattern. The network publishes small events, such as a friend request, an accepted request, a new follower, a like or a comment, each addressed to one recipient. An in-app inbox is one listener. A push sender or a daily email digest are more listeners. The core never learns about phones or email, and adding a channel never touches the friend or post code.
enum EventType { FRIEND_REQUEST,
FRIEND_ACCEPTED, NEW_FOLLOWER,
LIKE, COMMENT }
record Event(type, recipientId, msg)
interface Listener {
void onEvent(Event e);
}
Inbox, PushSender, EmailDigest:
each is one more listener Blocking
Blocking is stronger than unfriending. Under both locks, in id order, it records the block, removes the friendship and the follows in both directions, and cancels any open request between them. After that, a single helper, blocked either way, is checked by can view, search, sending requests, liking, commenting and the degree check. Checking both directions matters: if Ben blocks Asha, Asha must not see Ben either.
- under both locks, in id order:
- a.blocked.add(b)
- remove friendship both ways
- remove follows both ways
- cancel open requests
- everywhere else:
- blockedEitherWay(a, b) hides
- posts, search hits, requests,
- likes, comments, degrees
Degrees of connection
LinkedIn shows first, second and third degree connections. That is breadth first search over the friend graph, one level at a time: friends are level one, their friends level two, and so on. We stop at three, because the number of people grows very fast with each level. Mutual friends is simpler: walk the smaller friend set and keep ids that are also in the larger one. People you may know ranks second degree users by how many mutual friends they share.
frontier = [from]; seen = {from}
for depth 1..max:
next = []
for u in frontier:
for f in friends(u):
if (f == to) return depth;
if (seen.add(f)) next.add(f);
frontier = next
return -1 // out of network
mutual: intersect two friend sets Search by name
Search by name uses a prefix index. When a user registers, each word of their name is lower-cased and every prefix, up to ten letters, maps to their id. A query intersects the sets for its words. We drop the viewer and anyone blocked either way, then rank the hits by degree of connection, so your friends come first, then friends of friends, then everyone else. A real system would use a search engine fed by profile change events.
- index: each name word, each
- prefix up to 10 letters
- "chen" -> c, ch, che, chen
- query words: intersect sets
- drop self and blocked
- rank: 1st degree, then 2nd,
- then 3rd, then everyone else,
- then by name
Concurrency
Give every shared field a safe home. Likes, friends and follows are concurrent key sets, so adds and removes are atomic and the count is just the size. A request's status changes with one compare and set, so two devices accepting at once give one friendship and one error. Changes to a pair of users take two locks in id order. Posts, comments and listeners are copy-on-write lists, read far more than written. Ids come from an atomic counter.
- likes, friends, follows:
- ConcurrentHashMap key sets
- request status: AtomicReference
- compareAndSet once
- pair changes: two locks,
- lower id first
- posts, comments, listeners:
- CopyOnWriteArrayList
- ids: AtomicLong
- name index: concurrent sets
Extensibility
Interviewers will add features. Groups are a new audience: a group has members, and a group post is visible to its members. Pages are authors that only have followers, never friends. Ranking is a feed ranker strategy: merge a few hundred candidates by time, then score them by closeness, likes and freshness. A close friends audience is a custom list on the post. Even the push model can be added as a listener that copies new post ids into followers' feed lists.
- groups: a Group with members
- and its own visibility
- pages: a User-like author that
- only has followers
- ranking: a FeedRanker Strategy
- over the merged candidates
- close friends: a custom
- audience list on Post
- push feed: a listener that
- fans out post ids
Testing
The full code is below the player. A fake clock gives every post a predictable time, so the feed order is the same on every run. The demo builds a small friend graph, shows a request answered twice being rejected, two people requesting each other, degrees and mutual friends, a two page feed that skips an only me post, a like blocked by privacy, a block that removes Ben everywhere, and races on likes and on accepting two hundred requests.
Chen and Eli asked each other: friends Asha to Ben 1st, Chen 2nd, Dina 3rd, Farah out of network Mutual Asha and Chen: [Ben, Eli] Feed page 1: Ben: New job!, ... Rejected: Farah cannot see this post After block: Ben is gone from feed, search and friends Race: 301 likes, 200 friends
Follow-ups
Expect follow-ups. At a billion users the friend graph moves to a sharded store keyed by user id, and recent feed entries sit in a cache per user. Celebrities break push feeds, so use the hybrid model. Third degree search on a big graph is slow, so search from both ends at once and meet in the middle. If a user changes a post from public to friends, it must disappear at once, which is why we check can view at read time instead of storing visible copies.
- a billion users?
- graph in a sharded store,
- feed in a cache per user
- celebrity posts? hybrid feed
- third degree is too slow?
- bidirectional BFS, or cap
- friends per level
- privacy change after posting?
- check canView at read time
- unread notification count
Say it like this
Here is the short version to say out loud. Users hold sets of ids for friends, follows and blocks. A friend request changes status exactly once with a compare and set, and updates to a pair of users lock both in id order. One can view method guards every read. The feed is a k-way merge of per-author post lists with a heap, notifications are observers, and breadth first search gives first, second and third degree connections.
- "Users hold id sets for friends,
- follows and blocks; requests
- change status once with CAS;
- pair updates lock in id order.
- One canView guards everything.
- The feed merges per-author
- lists with a heap, observers
- notify, BFS gives degrees."