Topics › Heaps › Hard Problems

Design Twitter

Medium TUF ID 565 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Design a tiny version of Twitter that supports four operations:

• postTweet(userId, tweetId): the user posts a new tweet. Every tweetId is unique.
• getNewsFeed(userId): return the IDs of the 10 most recent tweets that the user can see, newest first. A user sees their own tweets and the tweets of everyone they follow.
• follow(followerId, followeeId): the follower starts following the followee.
• unfollow(followerId, followeeId): the follower stops following the followee.

Constraints: user IDs up to 500, tweet IDs up to 10^4, at most 3 · 10^4 calls in total. Following is one-directional. “Most recent” means the order in which postTweet was called. Tweet IDs are not increasing, so they cannot be used as timestamps.

Example 1

postTweet(1, 5)
getNewsFeed(1)      -> [5]
follow(1, 2)
postTweet(2, 6)
getNewsFeed(1)      -> [6, 5]     // 6 was posted after 5
unfollow(1, 2)
getNewsFeed(1)      -> [5]        // user 2's tweets disappear from the feed

Example 2

postTweet(1, 10), postTweet(2, 20), follow(1, 2)
getNewsFeed(1)      -> [20, 10]
getNewsFeed(2)      -> [20]       // user 2 does not follow user 1

All three designs implement the same interface, so one test script drives all of them:

interface Twitter {
    void postTweet(int userId, int tweetId);
    List<Integer> getNewsFeed(int userId);
    void follow(int followerId, int followeeId);
    void unfollow(int followerId, int followeeId);
}

static final int FEED_SIZE = 10;

Some decisions are shared by every version:

• The follow graph is a Map<Integer, Set<Integer>> from a user to the set of people they follow. A HashSet makes follow and unfollow O(1) and ignores duplicate follows.
• A user always sees their own tweets. Self-follows are ignored, so a later “self-unfollow” cannot hide a user’s own tweets.
• Recency comes from a counter clock that increases on every post, or from the position in a single global list.

Approach 1: Brute force, one global log

Intuition. Append every tweet, as {userId, tweetId}, to one global list. The list is in posting order, so reading it backwards visits tweets from newest to oldest. To build a feed, walk backwards and keep each tweet whose author is the user or someone they follow. Stop after 10 matches.

Algorithm.

1. postTweet: append {userId, tweetId} to log.
2. getNewsFeed(u): for i from the last index down to 0, while the feed has fewer than 10 items, add log[i].tweetId if log[i].userId is u or is in u’s follow set.
3. follow / unfollow: add to or remove from the follower’s set (creating it on first use).

static class GlobalLogTwitter implements Twitter {
    private final List<int[]> log = new ArrayList<>();                      // {userId, tweetId}, oldest first
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public void postTweet(int userId, int tweetId) {
        log.add(new int[]{userId, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> followees = following.getOrDefault(userId, Set.of());
        List<Integer> feed = new ArrayList<>();
        for (int i = log.size() - 1; i >= 0 && feed.size() < FEED_SIZE; i--) {
            int[] t = log.get(i);
            if (t[0] == userId || followees.contains(t[0])) feed.add(t[1]);
        }
        return feed;
    }

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

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

Complexity. postTweet, follow and unfollow take O(1). getNewsFeed takes O(T) in the worst case, where T is the total number of tweets ever posted. If a user follows nobody active, the scan reads the whole history to find nothing. Space O(T + E) for the log and the E follow edges.

The problem is that the feed’s cost depends on everybody’s tweets, while the answer depends only on the user’s own small circle.

Approach 2: Better, per-user lists and a sort

Intuition. Store tweets per author instead: userId -> list of {time, tweetId}, oldest first. A feed then only touches its sources, meaning the user plus everyone they follow.

One more observation keeps the work small. Only the newest 10 tweets of any single source can make the feed, because if a source’s 11th-newest tweet were in the top 10, that source’s 10 newer tweets would be too, which is 11 tweets. So collect at most the last 10 tweets of each source, sort the candidates by time (newest first), and keep the first 10.

Algorithm.

1. postTweet: append {clock++, tweetId} to the author’s list.
2. getNewsFeed(u): build sources as a copy of u’s follow set plus u. For each source, add its last (up to) 10 tweets to candidates. Sort by time, descending, and return the first 10 tweet IDs.
3. follow / unfollow: as before.

static class SortFeedTwitter implements Twitter {
    private int clock = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>();      // userId -> {time, tweetId}, oldest first
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{clock++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> sources = new HashSet<>(following.getOrDefault(userId, Set.of()));
        sources.add(userId);
        List<int[]> candidates = new ArrayList<>();
        for (int u : sources) {
            List<int[]> list = tweets.getOrDefault(u, List.of());
            for (int i = Math.max(0, list.size() - FEED_SIZE); i < list.size(); i++) candidates.add(list.get(i));
        }
        candidates.sort((a, b) -> Integer.compare(b[0], a[0]));            // newest first
        List<Integer> feed = new ArrayList<>();
        for (int i = 0; i < candidates.size() && i < FEED_SIZE; i++) feed.add(candidates.get(i)[1]);
        return feed;
    }

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

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

Complexity. getNewsFeed is O(F log F) where F is the number of sources: there are at most 10F candidates to sort. The other operations are O(1). Space O(T + E).

This no longer depends on the total number of tweets. It still sorts up to 10F items to keep only 10, so most of the sorting work is thrown away.

Approach 3: Optimal, k-way merge with a max-heap

Intuition. Each source’s list is already sorted by time, because tweets are appended in posting order. The feed is the first 10 items of the merge of F sorted lists, which is exactly the Merge K Sorted Lists pattern. We can stop as soon as 10 items have come out.

Put each source’s newest tweet into a max-heap ordered by time. The heap top is the newest tweet that has not been taken yet across all sources. Pop it into the feed, then push the next older tweet of the same author, because that tweet is the only new candidate the pop has made eligible. Repeat until the feed has 10 items or the heap is empty.

A heap entry needs to know where it came from, so it stores {time, tweetId, userId, indexInThatUsersList}.

Algorithm.

1. postTweet: append {clock++, tweetId} to the author’s list.
2. getNewsFeed(u): build sources (a copy of the follow set, plus u). For each source with tweets, push its last tweet with its index.
3. While the heap is non-empty and the feed has fewer than 10 items: pop the top, append its tweetId, and if index - 1 >= 0, push that author’s tweet at index - 1.
4. follow / unfollow: as before.

static class HeapMergeTwitter implements Twitter {
    private int clock = 0;
    private final Map<Integer, List<int[]>> tweets = new HashMap<>();      // userId -> {time, tweetId}, oldest first
    private final Map<Integer, Set<Integer>> following = new HashMap<>();

    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{clock++, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> sources = new HashSet<>(following.getOrDefault(userId, Set.of()));
        sources.add(userId);
        // heap entry {time, tweetId, userId, indexInThatUsersList}; newest tweet on top
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        for (int u : sources) {
            List<int[]> list = tweets.get(u);
            if (list == null || list.isEmpty()) continue;
            int last = list.size() - 1;
            pq.add(new int[]{list.get(last)[0], list.get(last)[1], u, last});
        }
        List<Integer> feed = new ArrayList<>();
        while (!pq.isEmpty() && feed.size() < FEED_SIZE) {
            int[] top = pq.poll();
            feed.add(top[1]);
            int prev = top[3] - 1;                                         // next older tweet of the same user
            if (prev >= 0) {
                int[] older = tweets.get(top[2]).get(prev);
                pq.add(new int[]{older[0], older[1], top[2], prev});
            }
        }
        return feed;
    }

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

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

Dry run. Posts in order: (1, 101) at time 0, (2, 201) at 1, (3, 301) at 2, (2, 202) at 3, (1, 102) at 4. User 1 follows users 2 and 3. Heap entries are written time:tweetId.

Complexity. getNewsFeed is O(F log F) to seed the heap, plus at most 10 pops and 10 pushes at O(log F) each. postTweet, follow and unfollow are O(1). Space O(T + E) overall, plus O(F) for the heap during a feed request.

The seeding step could be made O(F) with a bottom-up heapify, but for at most 500 users the difference does not matter. What matters is that the work after seeding is bounded by the feed size, 10, and not by how many tweets exist.

Edge cases and pitfalls

• Timestamps. Tweet IDs are arbitrary and unique, not increasing. Sorting by tweetId gives a wrong order. Use a global counter or the global log position.
• Never modify the stored follow set while building a feed. following.getOrDefault(u, Set.of()) may return an immutable empty set, and adding u to it throws UnsupportedOperationException. Adding u to the real set would also silently change the follow graph. Copy it first, as the code does.
• Self-follow and self-unfollow. Ignoring them keeps a user’s own tweets visible no matter what calls arrive. Using a Set for sources also prevents merging the same author twice, which would duplicate tweets.
• Unfollowing someone you never followed, or unfollowing when the user has no follow set at all, must be a no-op. Check for null.
• Fewer than 10 tweets. Return whatever exists, possibly an empty list. All the loops stop on the heap or list being exhausted.
• Unbounded storage. Only the newest 10 tweets per author can ever appear in a feed. A production version could drop older ones, which would make approaches 2 and 3 use O(10U + E) space.

Related problems

• Merge K sorted Lists is the k-way merge that approach 3 stops after 10 steps.
• Merge K Sorted Arrays is the same merge on arrays, which is exactly how tweets are stored here.
• Kth largest element in a stream of running integers is another design class backed by a heap.
• LRU Cache is a classic design problem built from a hash map and a list.
• LFU Cache extends that design with frequency buckets.