LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 39 OF 42

Design a Social Network Like Facebook: LLD in Java

A social network designed and coded: profiles, friend requests and follows, posts with public, friends and only me privacy, likes and comments, a news feed built by a k-way merge of recent posts, notifications as observers, blocking, name search, mutual friends and first, second and third degree connections with BFS, and races on likes and friend lists, with full Java 17 code.

Reported atIntuitRazorpay

Patterns usedObserverStrategy

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 22

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 527 lines, with a small main() demo. Save it as SocialNetwork.java, then run javac SocialNetwork.java && java SocialNetwork.

import java.time.Instant;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Supplier;

/**
 * A social network core: friend requests and follows, posts with privacy, likes and comments, a news feed
 * built by a k-way merge of per-author post lists, notifications as observers, blocking, name search,
 * mutual friends and degrees of connection with BFS.
 */
public final class SocialNetwork {

    // ---------- the model ----------
    enum Visibility { PUBLIC, FRIENDS, ONLY_ME }

    enum RequestStatus { PENDING, ACCEPTED, DECLINED, CANCELLED }

    static final class User {
        final long id;
        final String name;
        final String headline;
        // Ids, not object references: cheap, and easy to move to a database later.
        final Set<Long> friends = ConcurrentHashMap.newKeySet();
        final Set<Long> following = ConcurrentHashMap.newKeySet();
        final Set<Long> followers = ConcurrentHashMap.newKeySet();
        final Set<Long> blocked = ConcurrentHashMap.newKeySet();
        final List<Post> posts = new CopyOnWriteArrayList<>();   // append only, oldest first

        User(long id, String name, String headline) {
            this.id = id;
            this.name = name;
            this.headline = headline;
        }
    }

    record Comment(long id, long authorId, String text, Instant at) {}

    static final class Post {
        final long id;
        final long authorId;
        final String text;
        final Visibility visibility;
        final Instant at;
        final Set<Long> likes = ConcurrentHashMap.newKeySet();   // one like per user by construction
        final List<Comment> comments = new CopyOnWriteArrayList<>();

        Post(long id, long authorId, String text, Visibility visibility, Instant at) {
            this.id = id;
            this.authorId = authorId;
            this.text = text;
            this.visibility = visibility;
            this.at = at;
        }
    }

    static final class FriendRequest {
        final long id;
        final long from;
        final long to;
        final AtomicReference<RequestStatus> status = new AtomicReference<>(RequestStatus.PENDING);

        FriendRequest(long id, long from, long to) {
            this.id = id;
            this.from = from;
            this.to = to;
        }
    }

    record Pair(long from, long to) {}

    record FeedPage(List<Post> posts, Post cursor) {}

    // ---------- Observer ----------
    enum EventType { FRIEND_REQUEST, FRIEND_ACCEPTED, NEW_FOLLOWER, LIKE, COMMENT }

    record Event(EventType type, long recipientId, String message) {}

    interface Listener {
        void onEvent(Event e);
    }

    // ---------- the service ----------
    private static final Comparator<Post> NEWEST_FIRST =
            Comparator.comparing((Post p) -> p.at).thenComparingLong(p -> p.id).reversed();

    private final Supplier<Instant> clock;
    private final AtomicLong ids = new AtomicLong();
    private final Map<Long, User> users = new ConcurrentHashMap<>();
    private final Map<Long, Post> posts = new ConcurrentHashMap<>();
    private final Map<Long, FriendRequest> requests = new ConcurrentHashMap<>();
    private final Map<Pair, FriendRequest> openRequests = new ConcurrentHashMap<>();
    private final Map<String, Set<Long>> namePrefixes = new ConcurrentHashMap<>();
    private final List<Listener> listeners = new CopyOnWriteArrayList<>();

    SocialNetwork(Supplier<Instant> clock) { this.clock = clock; }

    void subscribe(Listener l) { listeners.add(l); }

    User register(String name, String headline) {
        User u = new User(ids.incrementAndGet(), name, headline);
        users.put(u.id, u);
        for (String word : name.toLowerCase().split("\\s+"))
            for (int len = 1; len <= Math.min(10, word.length()); len++)
                namePrefixes.computeIfAbsent(word.substring(0, len), k -> ConcurrentHashMap.newKeySet())
                        .add(u.id);
        return u;
    }

    // ---------- friends, follows, blocks ----------
    FriendRequest sendFriendRequest(long fromId, long toId) {
        User a = user(fromId);
        User b = user(toId);
        if (fromId == toId) throw new IllegalArgumentException("cannot befriend yourself");
        if (blockedEitherWay(fromId, toId))
            throw new IllegalStateException("cannot send a request to this user");
        if (a.friends.contains(toId)) throw new IllegalStateException("already friends");
        FriendRequest reverse = openRequests.get(new Pair(toId, fromId));
        if (reverse != null) {          // both asked: treat it as accepted
            respond(fromId, reverse.id, true);
            return reverse;
        }
        FriendRequest r = new FriendRequest(ids.incrementAndGet(), fromId, toId);
        FriendRequest existing = openRequests.putIfAbsent(new Pair(fromId, toId), r);
        if (existing != null) return existing;   // a double click still makes one request
        requests.put(r.id, r);
        publish(new Event(EventType.FRIEND_REQUEST, toId, a.name + " sent you a friend request"));
        return r;
    }

    void respond(long userId, long requestId, boolean accept) {
        FriendRequest r = requests.get(requestId);
        if (r == null) throw new IllegalArgumentException("no request " + requestId);
        if (r.to != userId) throw new IllegalStateException("only the receiver can answer a request");
        RequestStatus next = accept ? RequestStatus.ACCEPTED : RequestStatus.DECLINED;
        // Compare-and-set: a request is answered exactly once, even if two devices answer together.
        if (!r.status.compareAndSet(RequestStatus.PENDING, next))
            throw new IllegalStateException("request already " + r.status.get());
        openRequests.remove(new Pair(r.from, r.to));
        if (!accept) return;
        User a = user(r.from);
        User b = user(r.to);
        withBothLocked(a, b, () -> {
            if (a.blocked.contains(b.id) || b.blocked.contains(a.id)) return;
            a.friends.add(b.id);
            b.friends.add(a.id);
        });
        publish(new Event(EventType.FRIEND_ACCEPTED, r.from, b.name + " accepted your request"));
    }

    void unfriend(long aId, long bId) {
        User a = user(aId);
        User b = user(bId);
        withBothLocked(a, b, () -> {
            a.friends.remove(b.id);
            b.friends.remove(a.id);
        });
    }

    void follow(long followerId, long targetId) {
        if (followerId == targetId) throw new IllegalArgumentException("cannot follow yourself");
        if (blockedEitherWay(followerId, targetId))
            throw new IllegalStateException("cannot follow this user");
        User f = user(followerId);
        User t = user(targetId);
        boolean added = f.following.add(t.id);
        t.followers.add(f.id);
        if (added) publish(new Event(EventType.NEW_FOLLOWER, t.id, f.name + " follows you"));
    }

    void block(long blockerId, long targetId) {
        User a = user(blockerId);
        User b = user(targetId);
        withBothLocked(a, b, () -> {
            a.blocked.add(b.id);
            a.friends.remove(b.id);
            b.friends.remove(a.id);
            a.following.remove(b.id);
            b.followers.remove(a.id);
            b.following.remove(a.id);
            a.followers.remove(b.id);
        });
        for (Pair p : List.of(new Pair(a.id, b.id), new Pair(b.id, a.id))) {
            FriendRequest r = openRequests.remove(p);
            if (r != null) r.status.compareAndSet(RequestStatus.PENDING, RequestStatus.CANCELLED);
        }
    }

    boolean blockedEitherWay(long a, long b) {
        return user(a).blocked.contains(b) || user(b).blocked.contains(a);
    }

    /** Both sides of a pair change together. Locks are always taken lower id first, so no deadlock. */
    private static void withBothLocked(User a, User b, Runnable change) {
        User first = a.id < b.id ? a : b;
        User second = first == a ? b : a;
        synchronized (first) {
            synchronized (second) {
                change.run();
            }
        }
    }

    // ---------- posts, privacy, likes, comments ----------
    Post post(long authorId, String text, Visibility visibility) {
        User author = user(authorId);
        Post p = new Post(ids.incrementAndGet(), authorId, text, visibility, clock.get());
        posts.put(p.id, p);
        author.posts.add(p);
        return p;
    }

    /** The only privacy check. Feed, likes and comments all go through it, at read time. */
    boolean canView(long viewerId, Post p) {
        if (p.authorId == viewerId) return true;
        if (blockedEitherWay(viewerId, p.authorId)) return false;
        return switch (p.visibility) {
            case PUBLIC -> true;
            case FRIENDS -> user(p.authorId).friends.contains(viewerId);
            case ONLY_ME -> false;
        };
    }

    int like(long userId, long postId) {
        Post p = visiblePost(userId, postId);
        if (p.likes.add(userId) && userId != p.authorId)     // only the first like notifies
            publish(new Event(EventType.LIKE, p.authorId, user(userId).name + " liked: " + p.text));
        return p.likes.size();
    }

    int unlike(long userId, long postId) {
        Post p = visiblePost(userId, postId);
        p.likes.remove(userId);
        return p.likes.size();
    }

    Comment comment(long userId, long postId, String text) {
        Post p = visiblePost(userId, postId);
        Comment c = new Comment(ids.incrementAndGet(), userId, text, clock.get());
        p.comments.add(c);
        if (userId != p.authorId)
            publish(new Event(EventType.COMMENT, p.authorId, user(userId).name + " commented: " + text));
        return c;
    }

    private Post visiblePost(long userId, long postId) {
        Post p = posts.get(postId);
        if (p == null) throw new IllegalArgumentException("no post " + postId);
        if (!canView(userId, p)) throw new IllegalStateException(user(userId).name + " cannot see this post");
        return p;
    }

    // ---------- news feed: pull model, k-way merge ----------
    /** A position in one author's post list, walking from newest to oldest. */
    private static final class Cursor {
        final List<Post> list;
        int index;

        Cursor(List<Post> list, int index) {
            this.list = list;
            this.index = index;
        }

        Post head() { return list.get(index); }

        boolean stepBack() { return --index >= 0; }
    }

    /** Newest first. Pass the previous page's cursor as before (null for the first page). */
    FeedPage feed(long viewerId, int limit, Post before) {
        User me = user(viewerId);
        Set<Long> sources = new HashSet<>(me.friends);
        sources.addAll(me.following);
        sources.add(viewerId);
        PriorityQueue<Cursor> heap = new PriorityQueue<>(Comparator.comparing(Cursor::head, NEWEST_FIRST));
        for (long authorId : sources) {
            if (authorId != viewerId && blockedEitherWay(viewerId, authorId)) continue;
            List<Post> list = user(authorId).posts;  // append only: indexes below size() never change
            int i = list.size() - 1;
            while (i >= 0 && before != null && NEWEST_FIRST.compare(list.get(i), before) <= 0) i--;
            if (i >= 0) heap.add(new Cursor(list, i));
        }
        List<Post> out = new ArrayList<>();
        while (out.size() < limit && !heap.isEmpty()) {
            Cursor c = heap.poll();
            Post p = c.head();
            if (canView(viewerId, p)) out.add(p);
            if (c.stepBack()) heap.add(c);
        }
        return new FeedPage(List.copyOf(out), out.size() == limit ? out.get(out.size() - 1) : null);
    }

    // ---------- graph queries ----------
    /** 1 = friend, 2 = friend of a friend, 3 = one more hop; -1 = further away or blocked. */
    int degree(long fromId, long toId, int maxDepth) {
        if (fromId == toId) return 0;
        if (blockedEitherWay(fromId, toId)) return -1;
        Set<Long> seen = new HashSet<>(List.of(fromId));
        List<Long> frontier = List.of(fromId);
        for (int depth = 1; depth <= maxDepth; depth++) {
            List<Long> next = new ArrayList<>();
            for (long u : frontier)
                for (long f : user(u).friends) {
                    if (f == toId) return depth;
                    if (seen.add(f)) next.add(f);
                }
            frontier = next;
        }
        return -1;
    }

    List<String> mutualFriends(long aId, long bId) {
        Set<Long> a = user(aId).friends;
        Set<Long> b = user(bId).friends;
        Set<Long> small = a.size() <= b.size() ? a : b;
        Set<Long> large = small == a ? b : a;
        List<String> out = new ArrayList<>();
        for (long id : small) if (large.contains(id)) out.add(user(id).name);
        out.sort(null);
        return out;
    }

    /** People you may know: friends of friends, ranked by how many mutual friends they share. */
    List<String> suggestions(long userId, int limit) {
        User me = user(userId);
        Map<Long, Integer> mutualCount = new HashMap<>();
        for (long f : me.friends)
            for (long ff : user(f).friends)
                if (ff != userId && !me.friends.contains(ff) && !blockedEitherWay(userId, ff))
                    mutualCount.merge(ff, 1, Integer::sum);
        return mutualCount.entrySet().stream()
                .sorted(Map.Entry.<Long, Integer>comparingByValue().reversed()
                        .thenComparing(e -> user(e.getKey()).name))
                .limit(limit).map(e -> user(e.getKey()).name + " (" + e.getValue() + " mutual)").toList();
    }

    /** Prefix search on name words, ranked by degree of connection, then by name. */
    List<String> search(long viewerId, String query) {
        Set<Long> hits = null;
        for (String word : query.toLowerCase().trim().split("\\s+")) {
            String key = word.length() > 10 ? word.substring(0, 10) : word;
            Set<Long> ids = new HashSet<>(namePrefixes.getOrDefault(key, Set.of()));
            ids.removeIf(id -> !hasWordStartingWith(user(id).name, word));
            if (hits == null) hits = ids;
            else hits.retainAll(ids);
        }
        if (hits == null) return List.of();
        hits.removeIf(id -> id == viewerId || blockedEitherWay(viewerId, id));
        Map<Long, Integer> rank = new HashMap<>();
        for (long id : hits) {
            int d = degree(viewerId, id, 3);
            rank.put(id, d < 0 ? 9 : d);
        }
        return hits.stream()
                .sorted(Comparator.comparing((Long id) -> rank.get(id)).thenComparing(id -> user(id).name))
                .map(id -> user(id).name + (rank.get(id) < 9 ? " (" + rank.get(id) + ")" : "")).toList();
    }

    private static boolean hasWordStartingWith(String name, String prefix) {
        for (String w : name.toLowerCase().split("\\s+")) if (w.startsWith(prefix)) return true;
        return false;
    }

    private void publish(Event e) { for (Listener l : listeners) l.onEvent(e); }

    User user(long id) {
        User u = users.get(id);
        if (u == null) throw new IllegalArgumentException("no user " + id);
        return u;
    }

    // ---------- demo ----------
    /** An observer that keeps an inbox per user; push or email would be other listeners. */
    static final class Inbox implements Listener {
        final Map<Long, List<String>> messages = new ConcurrentHashMap<>();

        @Override
        public void onEvent(Event e) {
            messages.computeIfAbsent(e.recipientId(), k -> new CopyOnWriteArrayList<>())
                    .add(e.type() + ": " + e.message());
        }

        List<String> of(User u) { return messages.getOrDefault(u.id, List.of()); }
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    static void expectRejected(Runnable action) {
        try {
            action.run();
            throw new AssertionError("should have been rejected");
        } catch (IllegalArgumentException | IllegalStateException e) {
            System.out.println("Rejected: " + e.getMessage());
        }
    }

    static String show(SocialNetwork net, FeedPage page) {
        return page.posts().stream()
                .map(p -> net.user(p.authorId).name.split(" ")[0] + ": " + p.text).toList().toString();
    }

    static void befriend(SocialNetwork net, User a, User b) {
        net.respond(b.id, net.sendFriendRequest(a.id, b.id).id, true);
    }

    public static void main(String[] args) throws Exception {
        AtomicReference<Instant> time = new AtomicReference<>(Instant.parse("2026-05-01T08:00:00Z"));
        SocialNetwork net = new SocialNetwork(() -> time.updateAndGet(t -> t.plusSeconds(60))); // fake clock
        Inbox inbox = new Inbox();
        net.subscribe(inbox);

        User asha = net.register("Asha Verma", "Backend engineer");
        User ben = net.register("Ben Cole", "Product designer");
        User chen = net.register("Chen Wu", "Data analyst");
        User dina = net.register("Dina Shah", "Teacher");
        User eli = net.register("Eli Moss", "Runner and coder");
        User farah = net.register("Farah Ali", "Chef");
        User gopal = net.register("Gopal Iyer", "Student");
        User arun = net.register("Arun Bose", "Hiring manager");

        FriendRequest r = net.sendFriendRequest(asha.id, ben.id);
        check(net.sendFriendRequest(asha.id, ben.id) == r, "a double click makes one request");
        System.out.println("Ben's inbox: " + inbox.of(ben));
        net.respond(ben.id, r.id, true);
        expectRejected(() -> net.respond(ben.id, r.id, true));
        befriend(net, ben, chen);
        befriend(net, chen, dina);
        befriend(net, asha, eli);
        befriend(net, dina, farah);
        net.sendFriendRequest(chen.id, eli.id);
        net.sendFriendRequest(eli.id, chen.id);              // both asked: accepted
        System.out.println("Chen and Eli asked each other: friends = " + chen.friends.contains(eli.id));
        FriendRequest g = net.sendFriendRequest(gopal.id, asha.id);
        net.respond(asha.id, g.id, false);
        System.out.println("Gopal's request is " + g.status.get());

        System.out.println("Degrees from Asha: Ben " + net.degree(asha.id, ben.id, 3) + ", Chen "
                + net.degree(asha.id, chen.id, 3) + ", Dina " + net.degree(asha.id, dina.id, 3) + ", Farah "
                + net.degree(asha.id, farah.id, 3) + " (out of network)");
        System.out.println("Mutual friends of Asha and Chen: " + net.mutualFriends(asha.id, chen.id));
        System.out.println("People Asha may know: " + net.suggestions(asha.id, 3));
        check(net.degree(asha.id, dina.id, 3) == 3 && net.degree(asha.id, farah.id, 3) == -1, "BFS degrees");

        net.follow(asha.id, arun.id);                        // a follow needs no approval
        Post trek = net.post(ben.id, "Weekend trek photos", Visibility.FRIENDS);
        net.post(arun.id, "We are hiring backend engineers", Visibility.PUBLIC);
        net.post(eli.id, "Draft: resume notes", Visibility.ONLY_ME);
        net.post(chen.id, "Friends-only rant about spreadsheets", Visibility.FRIENDS);
        net.post(eli.id, "Ran my first 10k", Visibility.PUBLIC);
        Post hello = net.post(asha.id, "Hello from Asha", Visibility.PUBLIC);
        net.post(ben.id, "New job!", Visibility.PUBLIC);

        FeedPage page1 = net.feed(asha.id, 3, null);
        FeedPage page2 = net.feed(asha.id, 3, page1.cursor());
        System.out.println("Asha's feed page 1: " + show(net, page1));
        System.out.println("Asha's feed page 2: " + show(net, page2));
        check(page1.posts().size() == 3 && page2.posts().size() == 2, "two pages, only me post skipped");

        net.like(ben.id, hello.id);
        net.like(ben.id, hello.id);                          // double click: still one like
        int likes = net.like(chen.id, hello.id);             // public post: anyone may like it
        net.comment(chen.id, hello.id, "Welcome!");
        System.out.println("Likes on Asha's post: " + likes + "; Asha's inbox: " + inbox.of(asha));
        check(likes == 2, "one like per user");
        expectRejected(() -> net.like(farah.id, trek.id));   // friends-only post of a stranger

        System.out.println("Search 'b' as Asha: " + net.search(asha.id, "b"));
        net.block(asha.id, ben.id);
        expectRejected(() -> net.sendFriendRequest(ben.id, asha.id));
        System.out.println("After block, feed: " + show(net, net.feed(asha.id, 10, null)));
        System.out.println("After block, search 'b': " + net.search(asha.id, "b") + ", Chen is still "
                + net.degree(asha.id, chen.id, 3) + " (via Eli)");
        check(!asha.friends.contains(ben.id) && !ben.friends.contains(asha.id), "block unfriends");
        check(net.feed(asha.id, 10, null).posts().stream().noneMatch(p -> p.authorId == ben.id),
                "feed hides a blocked user");

        // Concurrency 1: 300 users like one post at once, and one user double clicks 1000 times.
        Post viral = net.post(arun.id, "Five tips for system design interviews", Visibility.PUBLIC);
        List<User> crowd = new ArrayList<>();
        for (int i = 0; i < 300; i++) crowd.add(net.register("Fan " + i, "reader"));
        ExecutorService pool = Executors.newFixedThreadPool(8);
        List<Future<?>> jobs = new ArrayList<>();
        for (User u : crowd) jobs.add(pool.submit(() -> net.like(u.id, viral.id)));
        for (int t = 0; t < 4; t++)
            jobs.add(pool.submit(() -> { for (int k = 0; k < 250; k++) net.like(asha.id, viral.id); }));
        for (Future<?> f : jobs) f.get();
        jobs.clear();

        // Concurrency 2: 200 requests to one hub, each accepted by two devices at the same moment.
        User hub = net.register("Hub Person", "popular");
        List<FriendRequest> incoming = new ArrayList<>();
        for (int i = 0; i < 200; i++) incoming.add(net.sendFriendRequest(crowd.get(i).id, hub.id));
        AtomicInteger accepted = new AtomicInteger();
        AtomicInteger refused = new AtomicInteger();
        for (FriendRequest req : incoming)
            for (int device = 0; device < 2; device++)
                jobs.add(pool.submit(() -> {
                    try {
                        net.respond(hub.id, req.id, true);
                        accepted.incrementAndGet();
                    } catch (IllegalStateException e) {
                        refused.incrementAndGet();
                    }
                }));
        for (Future<?> f : jobs) f.get();
        pool.shutdown();
        boolean symmetric = net.users.values().stream()
                .allMatch(u -> u.friends.stream().allMatch(f -> net.user(f).friends.contains(u.id)));
        System.out.println("Race: " + viral.likes.size() + " likes, " + hub.friends.size() + " friends, "
                + accepted.get() + " accepts won, " + refused.get() + " refused, symmetric: " + symmetric);
        check(viral.likes.size() == 301 && hub.friends.size() == 200, "exact counts");
        check(accepted.get() == 200 && refused.get() == 200 && symmetric, "one accept per request");
    }
}

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.

Requirements
  • 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
Clarify first
  • 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.

Core types
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.

send and respond
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.

link(a, b)
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.

canView(viewer, post)
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.

Pull model feed
  • 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.

feed(viewer, limit, before)
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.

Two ways to build a feed
  • 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.

like(user, post)
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.

Observer
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.

block(a, b)
  • 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.

degree(from, to, max = 3)
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.

search(viewer, "ch")
  • 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.

Thread safety checklist
  • 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.

Extension points
  • 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.

Run it
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.

Follow-ups to expect
  • 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.

In the interview
  • "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."

Interview questions

How would you build the news feed?

In the pull model, collect the viewer's friends and followed users, take one cursor per author at their newest post, and merge the already sorted lists with a max heap ordered by time, filtering each post through the privacy check. A page of n posts from k authors costs about n log k, and the last post returned is the cursor for the next page.

Pull or push for the feed, and why?

Pull computes the feed at read time, so writes are cheap but reads do more work. Push copies each new post id into every follower's feed when it is written, so reads are fast but very popular accounts are expensive. Large systems use a hybrid: push for normal authors and pull for celebrities, merged at read time.

How do you keep a friendship consistent on both sides?

Every change to a pair of users, such as accept, unfriend or block, takes both users' locks and updates both friend sets together. To avoid deadlock the locks are always taken in the same order, lower user id first.

What happens if a friend request is accepted twice at the same moment?

The request keeps its status in an AtomicReference, and accepting does compareAndSet from PENDING to ACCEPTED. Only one call succeeds and links the users; the other sees the request was already answered and fails cleanly.

Where do privacy checks live?

In one canView method that knows the author, blocks in both directions and the post visibility: public, friends or only me. The feed, likes and comments all call it, and it runs at read time so a changed setting takes effect immediately.

How do you find second and third degree connections?

Breadth first search over the friend graph from the viewer, one level at a time, stopping at depth three because each level grows very quickly. For large graphs, bidirectional search from both users meets in the middle and explores far fewer nodes.

How do you count likes correctly under heavy concurrency?

Store likes as a concurrent set of user ids on the post. Adding is atomic and idempotent, so double clicks or racing devices count once, and the like count is the set size. At larger scale a counter is kept alongside and fixed up from the set.

What does blocking do in your design?

It records the block, removes the friendship and follows in both directions and cancels open requests, all under the pair's locks. A blockedEitherWay check then hides the two users from each other in posts, search, requests, likes, comments and degree queries.

How would you implement search by name?

Keep a prefix index from each lower-cased name word prefix to user ids, intersect the sets for each query word, drop the viewer and blocked users, then rank results by degree of connection and name. At scale this moves to a search engine fed by profile change events.