Design Twitter

Problem in Plain English

Design a mini Twitter where users post tweets, follow and unfollow others, and read the 10 most recent tweet ids from themselves and everyone they follow. Recency is decided by posting order rather than by tweet id.

Problem Statement

Design a simplified version of Twitter where users post tweets, follow or unfollow other users, and view the 10 most recent tweets in their news feed.

Implement the Twitter class with void postTweet(userId, tweetId), which records a tweet with a unique tweetId; List getNewsFeed(userId), which returns up to 10 tweet ids from the user and everyone they follow, ordered from most recent to least recent; void follow(followerId, followeeId); and void unfollow(followerId, followeeId). A global posting order decides recency.

Constraints

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 10^4
All tweet ids are unique.
At most 3 * 10^4 calls will be made to postTweet, getNewsFeed, follow and unfollow.
The public contract disallows following yourself; these implementations defensively ignore self-follow and self-unfollow.

Examples

Example 1

Input: ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"] [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]
Output: [null,null,[5],null,null,[6,5],null,[5]]

User 1 posts tweet 5, follows user 2, then sees [6,5] after user 2 posts tweet 6. After unfollowing user 2, the feed shrinks back to [5].

Example 2

Input: ["Twitter","getNewsFeed","follow","getNewsFeed","unfollow","getNewsFeed"] [[],[1],[1,2],[1],[1,2],[1]]
Output: [null,[],null,[],null,[]]

Neither user has posted. Following and later unfollowing user 2 changes visibility but creates no tweets, so every feed is empty. Querying a previously unseen user must work without creating persistent state.

Example 3

Input: ["Twitter","postTweet","postTweet","follow","follow","getNewsFeed","unfollow","getNewsFeed","follow","getNewsFeed"] [[],[2,100],[1,3],[1,2],[1,2],[1],[1,2],[1],[1,2],[1]]
Output: [null,null,null,null,null,[3,100],null,[3],null,[3,100]]

Tweet 3 is newer than 100 despite its smaller ID. Duplicate follows add one author, not two copies of that author's posts. Unfollow hides 100, while following again exposes the same historical tweet; neither operation deletes history.

Intuition

A feed combines your own posting history with the histories of users you currently follow. Give each post an increasing timestamp: tweet IDs are labels, not clocks. In Example 1, tweet 6 has timestamp 1, so it precedes tweet 5 at timestamp 0; unfollowing user 2 hides 6 without deleting it. Each history is already ordered, so a heap can compare only the newest remaining post from each visible author.

Approaches

Collect and Sort

Solution Details

Reveal Collect and Sort: intuition, complexity, and code

Intuition

Each user already owns their tweets in posting order, so a feed can be built by gathering every visible tweet and sorting the pile by timestamp. The sort is simple to write but repeats the full ordering work on every single feed request.

Step-by-Step Logic

Store each post as (timestamp, tweetId) in its author's history, incrementing a global clock; in Example 1 user 1 receives (0,5) and the clock becomes 1.
For a feed, copy the follow set, add the requester locally, and gather those histories without changing stored tweets or follows. The first query gathers [(0,5)] and returns [5].
Sort the gathered records by descending timestamp and return at most ten IDs. After follow(1,2) and postTweet(2,6), the clock is 2, authors are {1,2}, and gathering produces [(0,5),(1,6)].
The second sort produces [(1,6),(0,5)], so the feed is [6,5]. Unfollow removes 2 from user 1's follow set while retaining both histories.
The final query gathers only [(0,5)] and returns [5]; all operation results are [null,null,[5],null,null,[6,5],null,[5]].

Why It Works

For a query, build the set of currently followed authors plus the requesting user. A set includes every eligible author exactly once, so collecting each author's entire history includes all and only eligible tweets, without duplicates. Every post receives a distinct increasing timestamp. Descending sorting therefore places all collected posts in exact recency order, and taking the first ten returns precisely the required feed. Follow and unfollow only change the eligibility set, preserving historical tweets for a later re-follow.

Dry Run

Collect and Sort: variable states at each step
operation	clock after	histories (time,id)	follows of 1	local query authors	collected then sorted	return
Twitter()	0	{}	absent	—	—	null
postTweet(1,5)	1	1:[(0,5)]	absent	—	—	null
getNewsFeed(1)	1	1:[(0,5)]	absent	{1}	[(0,5)] → [(0,5)]	[5]
follow(1,2)	1	1:[(0,5)]	{2}	—	—	null
postTweet(2,6)	2	1:[(0,5)], 2:[(1,6)]	{2}	—	—	null
getNewsFeed(1)	2	1:[(0,5)], 2:[(1,6)]	{2}	{1,2}	[(0,5),(1,6)] → [(1,6),(0,5)]	[6,5]
unfollow(1,2)	2	1:[(0,5)], 2:[(1,6)]	{}	—	—	null
getNewsFeed(1)	2	1:[(0,5)], 2:[(1,6)]	{}	{1}	[(0,5)] → [(0,5)]	[5]
full operation output	2	histories retained	{}	—	—	[null,null,[5],null,null,[6,5],null,[5]]

Complexity Analysis

Time Complexity

O(F + T \log(T+1))

Space Complexity

O(F + T)

For one feed, F counts distinct visible authors including yourself and T counts their total tweets. Copying the author set and scanning histories costs O(F+T); sorting costs O(T log(T+1)), including the empty-history case. The copied set, gathered references, and sort workspace use O(F+T) auxiliary space; the result has at most ten IDs. Across the object, P posts, E follow edges, and U represented users occupy O(P+E+U) persistent space. postTweet is amortized O(1), and follow/unfollow are expected O(1) with hash tables. Array resizing can make one post O(P); these bounds assume expected hash operations.

Code

Solution.java

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.HashSet;4import java.util.List;5import java.util.Map;6import java.util.Set;7
8class Twitter {9    private int time = 0;10    private Map<Integer, List<int[]>> tweets = new HashMap<>();11    private Map<Integer, Set<Integer>> follows = new HashMap<>();12
13    public void postTweet(int userId, int tweetId) {14        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{time++, tweetId});15    }16
17    public List<Integer> getNewsFeed(int userId) {18        // Add self only to a local set: reading a feed must not change follows.19        Set<Integer> authors = new HashSet<>(follows.getOrDefault(userId, java.util.Collections.emptySet()));20        authors.add(userId);21        List<int[]> visible = new ArrayList<>();22        for (int id : authors) {23            if (tweets.containsKey(id)) {24                visible.addAll(tweets.get(id));25            }26        }27        // Sort the local reference list, leaving each author history in posting order.28        visible.sort((a, b) -> Integer.compare(b[0], a[0]));29        List<Integer> res = new ArrayList<>();30        for (int i = 0; i < Math.min(10, visible.size()); i++) {31            res.add(visible.get(i)[1]);32        }33        return res;34    }35
36    public void follow(int followerId, int followeeId) {37        if (followerId != followeeId) {38            follows.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);39        }40    }41
42    public void unfollow(int followerId, int followeeId) {43        if (followerId != followeeId && follows.containsKey(followerId)) {44            follows.get(followerId).remove(followeeId);45        }46    }47}

Hints

Hint 1

Stamp every tweet with a global counter when it is posted so recency never depends on tweet ids.

Hint 2

A feed merges one sorted tweet list per followed user, which is exactly the merge-k-sorted-lists setup.

Hint 3

Keep one heap entry per followed user and refill from the same user after each pop to walk the lists newest-first.

Edge Cases

No posts from any visible author: return [] without registering that user in a map.
More than ten visible tweets: return exactly ten, even if all ten come from one author; fewer than ten returns all.
Repeated follow and unfollow of a missing relationship are idempotent. Re-following reveals old posts because history is retained.
Small tweet IDs can be newer than large IDs. Use the global clock, including when different authors interleave posts.
Repeated feeds return the same IDs until posting or visibility changes. A caller modifying the returned list must not corrupt stored posts.
Self operations are outside the follow contract but safely ignored; own posts remain visible regardless of follow state.

Common Mistakes and Interview Tips

Sorting by tweet ID, or resetting time per author: both confuse labels with global posting order.
Adding self directly to a stored follow set during getNewsFeed, or reading missing defaultdict keys: either turns a query into a persistent mutation.
Using a list for follows: duplicate follows then duplicate an author's tweets. Use a set and a local self-inclusive copy.
Popping the stored history itself during a feed: subsequent reads lose tweets. Use a separate candidate and an integer cursor.
After a heap pop, advancing every author or using index+1: only the popped author advances backward to its next older post.
Claiming linear heap seeding while calling push repeatedly, or ignoring the copied follow set when most followees have no posts.

Key Takeaway

When each source is already sorted, merging with a heap seeded once per source beats re-sorting the union on every query.