Design Twitter

1. Problem & Core Objective

Design a simplified Twitter supporting four operations:

void postTweet(int userId, int tweetId)
List<Integer> getNewsFeed(int userId)   // the 10 most recent tweets from the user
                                        // and everyone they follow, newest first
void follow(int followerId, int followeeId)
void unfollow(int followerId, int followeeId)

Constraints: 1 <= userId, tweetId <= 10^4 · at most 3 × 10^4 calls total · a user may follow themselves but a feed always includes their own tweets

What's actually being tested: recognising getNewsFeed as merge k sorted lists, take the first 10 — the same problem as Merge K Sorted Lists, but where you only need a prefix, so a heap beats a full merge. Plus ordinary API design: picking the right containers for follow/unfollow.

2. First-Principles Thought Process

Ordering needs a global clock

"Most recent" must be comparable across users, so a per-user counter won't do. A single monotonically increasing timestamp, incremented on every post, gives a total order over all tweets.

private int time = 0;
tweets.get(userId).add(new int[]{time++, tweetId});

Each user's tweets are already sorted

Because timestamps only increase, appending to a per-user list keeps it sorted by time — newest last. So each user's tweet list is a sorted sequence, and no sorting is ever needed.

That's the same structural gift as the Time Based Key-Value Store in Section 5: a monotonic counter means insertion preserves order.

The feed is a k-way merge

A feed draws from the user plus everyone they follow — call it k sources, each already sorted newest-last. Finding the 10 newest across all of them is exactly merge k sorted lists, stopping after 10.

Two ways:

Because only 10 items are wanted, the heap's advantage is large — it never looks past the newest handful of each list.

The bounded feed changes the storage too

Since a feed never shows more than 10 tweets, a user's older tweets can never appear. So each user's list can be capped at 10 entries, bounding memory regardless of how much anyone posts.

That's an application-level version of the same idea as the size-k heap in question 1: discard what can never be part of an answer.

Choosing the containers

• Map<Integer, List<int[]>> tweets — user → their tweets, in time order
• Map<Integer, Set<Integer>> following — user → who they follow

follow and unfollow must both be O(1), and duplicates must not accumulate — that's a Set, not a list. Using a list would make unfollow O(n) and allow a double-follow to inflate the feed.

3. Solution Paths

Approach 1 — Collect all relevant tweets and sort (brute force)

public List<Integer> getNewsFeed(int userId) {
    List<int[]> all = new ArrayList<>();
    Set<Integer> sources = new HashSet<>(following.getOrDefault(userId, Set.of()));
    sources.add(userId);                                  // always include yourself

    for (int uid : sources)
        all.addAll(tweets.getOrDefault(uid, List.of()));

    all.sort((a, b) -> b[0] - a[0]);                      // newest first

    List<Integer> feed = new ArrayList<>();
    for (int i = 0; i < Math.min(10, all.size()); i++) feed.add(all.get(i)[1]);
    return feed;
}

• Time O(T log T) where T is the total tweets across all sources · Space O(T)

Counter-questions on this approach

⭐ "What's wasteful here?"

It gathers and fully sorts every tweet from every followee to read the first 10. If someone follows 100 users who have each posted 100 tweets, that's 10,000 items sorted to produce 10.

And it ignores the structure it was given — each user's list is already sorted. Sorting the concatenation throws that away and re-derives it.

⭐ "The lists are already sorted. What should you do instead?"

A k-way merge. The newest tweet overall must be the newest tweet of some source, so I only need each source's head — k candidates, not T items. A heap over those heads gives the newest in O(log k), and I repeat 10 times.

That's O(k + 10 log k) instead of O(T log T). Same reasoning as Merge K Sorted Lists, except that stopping after 10 makes the saving much larger.

"(a, b) -> b[0] - a[0] — safe?"

Timestamps are bounded by the call count, 3 × 10^4, so the difference can't overflow. But Comparator.comparingInt(a -> a[0]).reversed() is safer by construction and states the intent. I'd write that.

Approach 2 — Heap over the k source heads (optimal)

class Twitter {
    private int time = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>();      // user -> {time, tweetId}
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public void postTweet(int userId, int tweetId) {
        List<int[]> list = tweets.computeIfAbsent(userId, k -> new ArrayList<>());
        list.add(new int[]{time++, tweetId});
        if (list.size() > 10) list.remove(0);          // a feed never shows more than 10
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> sources = new HashSet<>(following.getOrDefault(userId, Set.of()));
        sources.add(userId);                            // your own tweets always count

        // max-heap of {time, tweetId, sourceUser, indexInThatList}, newest first
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            Comparator.comparingInt((int[] e) -> e[0]).reversed());

        for (int uid : sources) {                       // seed with each source's NEWEST only
            List<int[]> list = tweets.get(uid);
            if (list != null && !list.isEmpty()) {
                int last = list.size() - 1;
                heap.offer(new int[]{list.get(last)[0], list.get(last)[1], uid, last});
            }
        }

        List<Integer> feed = new ArrayList<>();
        while (!heap.isEmpty() && feed.size() < 10) {
            int[] e = heap.poll();
            feed.add(e[1]);
            int nextIdx = e[3] - 1;                     // the next-newest from that same source
            if (nextIdx >= 0) {
                int[] t = tweets.get(e[2]).get(nextIdx);
                heap.offer(new int[]{t[0], t[1], e[2], nextIdx});
            }
        }
        return feed;
    }

    public void follow(int followerId, int followeeId) {
        following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = following.get(followerId);
        if (set != null) set.remove(followeeId);
    }
}

Trace — postTweet(1,5), follow(1,2), postTweet(2,6), getNewsFeed(1):

Result [6, 5] ✓ — newest first.

• Time postTweet O(1) amortized, getNewsFeed O(k·10 + 10 log(k·10)), follow/unfollow O(1) · Space O(users × 10 + follows)

Counter-questions on this approach

⭐ "Why cap each user's list at 10?"

Because a feed never shows more than 10 tweets, so a user's 11th-newest tweet can never appear in anyone's feed — it's beaten by their own 10 newer ones.

That bounds memory per user at 10 entries regardless of posting volume. It's the same principle as the size-k heap in question 1: discard what can never be part of an answer.

One caveat: list.remove(0) on an ArrayList is O(n), though with n = 10 that's trivial. A Deque with removeFirst would be O(1) and is cleaner if the cap were larger.

⭐ "Why Set for following rather than List?"

Two reasons. unfollow must remove a specific id, which is O(1) on a HashSet and O(n) on a list. And following the same person twice must not create a duplicate — a list would let the same user's tweets enter the merge twice, producing repeated entries in the feed.

A Set makes both correct by construction rather than by careful coding.

⭐ "Why add userId to the sources explicitly?"

Because the problem says a feed includes the user's own tweets whether or not they follow themselves. Relying on self-follow would be wrong for any user who hasn't done it, which is most of them.

It's a one-line requirement that's easy to miss, and it fails silently — the feed just quietly omits your own posts.

"Why a global time rather than per-user counters?"

Because tweets must be ordered across users. Per-user counters are only comparable within a user, so merging two users' lists would be meaningless. A single monotonic counter gives a total order.

"Could time overflow?"

At 3 × 10^4 calls, no — it's nowhere near int range. In a real system you'd use a long epoch or a distributed id scheme like Snowflake, which packs a timestamp, a machine id, and a sequence number so ids stay roughly time-ordered across machines.

⭐ "Why seed the heap with only each source's newest tweet rather than all of them?"

Because the newest tweet overall must be the newest of some source — nothing deeper in a list can beat its own head. So k candidates suffice, and I push a source's next-newest only when I've just consumed its head.

That keeps the heap at k entries and makes it O(k + 10 log k). Seeding with everything would be O(10k) entries and would sort tweets I'll never look at.

The entry carries the source id and the index so I know where to pull the replacement from — the same bookkeeping as merging k sorted arrays.

"With lists capped at 10, does any of that matter?"

Honestly, less than it would without the cap — the total candidate set is at most 10k, so even a full sort would pass at these constraints. I'd write the k-way merge anyway because it's the right shape and it's what survives when the cap is lifted or the feed size grows, but I wouldn't oversell the difference at n = 3 × 10^4 calls.

"What's the cost of getNewsFeed in terms of follows?"

Linear in k, the number of people followed, because every source must at least be consulted. With 10,000 followees that's 10,000 map lookups per feed — which is the scaling problem real systems solve by fan-out on write rather than on read.

Comparison

4. Why the Optimal Wins

Sorting the concatenation discards the fact that each user's list is already sorted. The newest tweet overall must be the newest tweet of some source, so only k candidates matter at any moment — not T.

And because only 10 items are wanted, the merge stops almost immediately. The heap is the structure that makes "take the first few of a k-way merge" cheap; a full sort has no notion of stopping early.

The framing worth keeping:

A news feed is a k-way merge of already-sorted lists, truncated to a prefix. A heap over the k heads takes the prefix without producing the rest.

And the design lesson: a bounded output bounds the storage. Since a feed shows 10 tweets, nobody's 11th-newest tweet can ever matter.

5. Java Prerequisites

Global monotonic clock

private int time = 0;
list.add(new int[]{time++, tweetId});     // post-increment: use, then advance

Max-heap on a field of an array

new PriorityQueue<>(Comparator.comparingInt((int[] t) -> t[0]).reversed());

The explicit (int[] t) is required — inference fails on the chained reversed().

computeIfAbsent for grouping

tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(entry);
following.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);

getOrDefault with an immutable empty

following.getOrDefault(userId, Set.of())    // no allocation for the common miss

Set vs List for membership — HashSet.remove is O(1), ArrayList.remove(Object) is O(n), and only the set prevents duplicates. See 02.

6. Interview Communication Guide

Clarifying questions: Does a feed include the user's own tweets even without self-following (yes — easy to miss)? Can you follow the same person twice (should be idempotent)? Can you unfollow someone you don't follow (should be a no-op)? Are tweet ids unique (assume yes)? Exactly 10, or at most 10 (at most)?

The pitch

"Three design decisions, then the feed algorithm.

First, ordering needs a global clock. 'Most recent' has to be comparable across users, so a per-user counter won't work — I increment one shared timestamp on every post.

Second, because timestamps only increase, appending to a per-user list keeps it already sorted. No sorting is ever needed.

Third, containers: a map from user to their tweets, and a map from user to a Set of who they follow. A set, not a list, because unfollow needs O(1) removal and following someone twice must not duplicate their tweets in the feed.

Then getNewsFeed is merge k sorted lists, take the first 10 — the same problem as merging k linked lists, except I only need a prefix. The newest tweet overall must be the newest of some source, so I only need each source's head: k candidates, not all T tweets. A max-heap on timestamp gives the newest in O(log k), repeated 10 times.

Two details. I add the user's own id to the sources explicitly, because the feed includes their own tweets whether or not they follow themselves — that one fails silently if missed.

And I cap each user's stored list at 10, because a feed never shows more than 10, so a user's 11th-newest tweet can never appear in anyone's feed. That bounds memory per user regardless of posting volume — the same 'discard what can't be an answer' idea as the size-k heap.

postTweet and follow/unfollow are O(1); getNewsFeed is linear in the number of people followed, which is the part a real system would change."

Edge cases to volunteer:

Name the self-inclusion case and the double-follow case. The first is a requirement that silently omits your own posts if missed; the second is what the Set prevents, and a List-based solution returns duplicated tweets.

7. Follow-Up Questions — Modified Constraints

⭐ "A celebrity has 10 million followers. What breaks?"

Nothing on write — postTweet is still O(1). But this design is fan-out on read: each feed request consults every followee. For a user following thousands, that's thousands of lookups per feed load.

Real systems invert it: fan-out on write, pushing each new tweet into precomputed feed caches for every follower. That makes reads O(1) but makes a celebrity's post O(followers) — 10 million cache writes.

Twitter's actual answer is hybrid: fan-out on write for ordinary users, and fan-out on read for celebrities, merging the two at read time. Worth naming, because it's the real engineering trade this toy problem is modelling.

⭐ "Support a feed of size n instead of 10."

The heap logic is unchanged — poll n times. But the storage cap must become n, since a user's (n+1)-th newest tweet can now appear. If n is unbounded you lose the cap entirely and memory grows with post volume.

"Add getTweetsByUser(userId, since)."

The per-user list is sorted by timestamp, so binary search for since and return the suffix — O(log t + output). Exactly the floor-query technique from the Time Based Key-Value Store.

"Make it thread-safe."

ConcurrentHashMap for both maps handles concurrent users. Within a user, postTweet mutating the list races with a concurrent getNewsFeed reading it — a CopyOnWriteArrayList makes reads lock-free at the cost of expensive writes, which suits a read-heavy feed. The time counter needs an AtomicInteger.

"Support deleting a tweet."

Remove it from the author's list, O(10) with the cap. With fan-out on write it's far worse — you'd have to purge it from every follower's cached feed, which is why real systems often mark deleted and filter at read time instead.

"How would you rank the feed by relevance rather than recency?"

The k-way merge dies, because a score isn't monotonic along each user's list — the newest tweet isn't necessarily the highest-scoring, so you can't stop early. You'd have to gather a candidate set and score it, which is O(T) again. That's genuinely why ranked feeds are expensive and chronological ones are cheap.