Design Twitter — HashMap, Heap, and Social Graph in One Problem

Problem Statement#

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in their news feed.

Implement the Twitter class:

• Twitter() Initialises your twitter object.
• void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will use a unique tweetId.
• List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themselves. Tweets must be ordered from most recent to least recent.
• void follow(int followerId, int followeeId) The user with ID followerId starts following the user with ID followeeId.
• void unfollow(int followerId, int followeeId) The user with ID followerId starts unfollowing the user with ID followeeId.

Constraints:

• 1 <= userId, followerId, followeeId <= 500
• 0 <= tweetId <= 10^4
• All tweets have unique IDs.
• At most 3 × 10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow.

Examples:

Twitter twitter = new Twitter();
twitter.postTweet(1, 5);      // user 1 posts tweet 5
twitter.getNewsFeed(1);        // returns [5]
twitter.follow(1, 2);          // user 1 follows user 2
twitter.postTweet(2, 6);      // user 2 posts tweet 6
twitter.getNewsFeed(1);        // returns [6, 5] (most recent first)
twitter.unfollow(1, 2);        // user 1 unfollows user 2
twitter.getNewsFeed(1);        // returns [5] (tweet 6 no longer in feed)

Why This Problem Matters#

Design Twitter is a compact system design problem that tests your ability to combine multiple data structures: hash maps for the social graph and tweet storage, and a min-heap (or max-heap) for merging k sorted tweet lists. It's a favourite at Meta and Amazon because it mirrors real product engineering challenges.

The "10 most recent" requirement is the algorithmic heart of the problem. If users follow hundreds of people, and each has thousands of tweets, you can't afford to gather all tweets and sort them. The efficient approach uses a k-way merge — the same algorithm used in merge sort and external sorting. By maintaining a heap of "current candidates" (one per followee), you extract the most recent tweet one at a time until you have 10.

At Meta, this problem is a gateway to discussions about their actual news feed algorithm, which uses similar k-way merge logic over multiple content types with additional ranking signals. At Amazon, it appears in system design loops for services like Amazon Storefront's activity feeds.

The problem also tests your understanding of the social graph: storing following as a hash map of sets allows O(1) follow/unfollow and O(f) iteration over followees (where f = number of followees). This is the adjacency list representation for directed social graphs.

The Core Insight#

Data structures needed:

1. tweets: userId → list of (timestamp, tweetId) — per-user tweet timeline, appended in chronological order.
2. following: userId → set of followeeIds — the social graph (adjacency list).
3. A global monotonic timestamp to order tweets across users.

For getNewsFeed:

Gather all followees (plus the user themselves). For each, take the last (most recent) tweet from their list and push it into a max-heap (keyed by timestamp). Then pop up to 10 times: each pop gives the next most recent tweet, and if that user has more tweets, push their previous tweet onto the heap.

This is the classic k-way merge algorithm. Time complexity is O(f log f + 10 log f) where f = number of followees. The 10 is a constant, so this is O(f log f).

The heap stores (-timestamp, tweetId, userId, tweet_index) — using negative timestamps because Python's heapq is a min-heap, and we want max (most recent = highest timestamp).

Visual Dry Run#

After postTweet(1, 5), follow(1, 2), postTweet(2, 6), postTweet(1, 7):

tweets = {1: [(0, 5), (2, 7)], 2: [(1, 6)]}  (timestamp, tweetId)
following = {1: {2}}

getNewsFeed(1) — users to consider: {1, 2}

Initial heap: push last tweet from each user:

• User 1: tweet (2, 7) → push (-2, 7, 1, index=1)
• User 2: tweet (1, 6) → push (-1, 6, 2, index=0)

Feed: [7, 6, 5]. Correct!

Solution (Optimal)#

import heapq
from collections import defaultdict
 
class Twitter:
    def __init__(self):
        self.time = 0
        # userId -> list of (timestamp, tweetId)
        self.tweets = defaultdict(list)
        # followerId -> set of followeeIds
        self.following = defaultdict(set)
 
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1
 
    def getNewsFeed(self, userId: int) -> list[int]:
        # Collect all users whose tweets to consider
        users = self.following[userId] | {userId}
        # Max-heap (negate time for Python's min-heap)
        heap = []
        for u in users:
            lst = self.tweets[u]
            if lst:
                idx = len(lst) - 1
                t, tid = lst[idx]
                heapq.heappush(heap, (-t, tid, u, idx))
 
        feed = []
        while heap and len(feed) < 10:
            t, tid, u, idx = heapq.heappop(heap)
            feed.append(tid)
            # Push the previous tweet from this user
            if idx > 0:
                nt, ntid = self.tweets[u][idx - 1]
                heapq.heappush(heap, (-nt, ntid, u, idx - 1))
 
        return feed
 
    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)
 
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

class Twitter {
    constructor() {
        this.time = 0;
        this.tweets = new Map();  // userId -> [{time, tweetId}]
        this.following = new Map(); // followerId -> Set of followeeIds
    }
 
    postTweet(userId, tweetId) {
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId).push({ time: this.time++, tweetId });
    }
 
    getNewsFeed(userId) {
        // Gather all relevant users
        const users = new Set(this.following.get(userId) || []);
        users.add(userId);
 
        // Simple approach for interview: collect all tweets, sort, take top 10
        // (For larger inputs, use a proper k-way merge with a priority queue)
        const allTweets = [];
        for (const u of users) {
            const lst = this.tweets.get(u) || [];
            for (const t of lst) allTweets.push(t);
        }
 
        // Sort by time descending, take top 10
        allTweets.sort((a, b) => b.time - a.time);
        return allTweets.slice(0, 10).map(t => t.tweetId);
    }
 
    follow(followerId, followeeId) {
        if (!this.following.has(followerId)) this.following.set(followerId, new Set());
        this.following.get(followerId).add(followeeId);
    }
 
    unfollow(followerId, followeeId) {
        if (this.following.has(followerId)) {
            this.following.get(followerId).delete(followeeId);
        }
    }
}

Complexity Analysis:

• postTweet: O(1) — append to list.
• getNewsFeed: O(f log f + 10 log f) with heap merge, O(T log T) with sort (T = total tweets across followees). For most interview settings, the sort approach is acceptable.
• follow/unfollow: O(1) — set operations.
• Space: O(n + f + t) where n = users, f = follow edges, t = tweets.

Common Mistakes#

• Not including the user themselves in the news feed: The user should see their own tweets. users = following[userId] | {userId} handles this.
• Timestamp collision: If two users post tweets in the same call, timestamps must be globally unique and monotonically increasing. Use a single global counter.
• Unfollowing without checking existence: discard (Python) or delete (JavaScript Set) are safe no-ops for non-existent members. remove in Java's HashSet throws if the element is absent — use remove only after contains, or use removeIf.
• Off-by-one in heap index: When pushing the "previous" tweet after a pop, use idx - 1, not idx. Make sure idx > 0 before attempting.
• Getting news feed for a user with no tweets or followees: Return an empty list. The defaultdict(list) and defaultdict(set) handle this gracefully.

Follow-up Questions#

1. How would this design scale to millions of users? (Separate services: tweet storage (Cassandra), social graph (social graph service), news feed generation (pull vs push model).)
2. What is the "pull vs push" trade-off for news feed generation? (Pull: compute feed on read — correct but slow for large followee counts. Push: fan-out on write — fast reads but expensive for celebrities with millions of followers.)
3. How does Twitter actually implement news feed ranking? (Not just chronological — uses a ranking model trained on engagement signals. But the merge step for candidate retrieval is similar.)
4. What if a user follows 10,000 people? (The heap merge becomes O(10000 log 10000) — about 130,000 operations. Still feasible, but you'd want to limit followee counts in practice.)
5. How would you add pagination to getNewsFeed? (Return a cursor (timestamp of last returned tweet) and use it to skip to the right position in subsequent calls.)
6. How would you handle tweet deletion? (Mark tweets as deleted, filter during feed generation. Hard-deleting requires rebuilding the per-user tweet list.)

Related Problems#

• [LC 355] Design Twitter — this exact problem.
• [LC 23] Merge K Sorted Lists — the foundational k-way merge algorithm used in getNewsFeed.
• [LC 295] Find Median from Data Stream — two-heap design for streaming data, similar heap-centric design thinking.
• [LC 146] LRU Cache — another core design interview problem with similar hash map + ordered structure pattern.
• [LC 622] Design Circular Queue — simpler design problem, good warm-up.
• [LC 1603] Design Parking System — simplest design problem in the series, good for building confidence.

Key Takeaways#

• Design Twitter (LC 355) combines a hash map for tweet storage, a hash map of sets for the social graph, and a max-heap for k-way merging of tweet timelines.
• Store tweets as (timestamp, tweetId) pairs per user; a global monotonically increasing counter ensures correct ordering across users.
• Always include the user themselves when computing the news feed — users = following[userId] | {userId}.
• The k-way heap merge is O(f log f + 10 log f) where f = number of followees; it avoids collecting all tweets before sorting.
• Use set.discard() (Python) or Set.delete() (JavaScript) for unfollow — safe no-ops when the followee was never followed.
• The pull model (compute feed on read) is correct but slow for users with many followees; the push model (fan-out on write) is fast to read but expensive for high-follower accounts.
• The same k-way merge pattern used in getNewsFeed appears in "Merge K Sorted Lists" (LC 23) and external sorting algorithms.