#355 Design Twitter
frequently reported atAdobeSalesforcePayPalAmazonGoogleApple
the problem
In plain words
Implement postTweet(userId, tweetId), getNewsFeed(userId) — the 10 most recent tweet ids from the user and the people they follow, newest first — follow and unfollow.
in post(1,5); feed(1); follow(1,2); post(2,6); feed(1); unfollow(1,2); feed(1)
out [5], [6,5], [5]
- 1 ≤ userId, followerId, followeeId ≤ 500
- 0 ≤ tweetId ≤ 10⁴, all unique
- At most 3·10⁴ calls in total
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternK-way merge
Each user's tweets are already sorted by time. The feed is "merge k sorted lists, but stop after 10" — a k-way merge with a max-heap of each followee's newest tweet.
solutions
From brute force to optimal
Walk all tweets from newest to oldest and keep the first 10 by relevant authors.
- postTweet appends (user, tweet).
- getNewsFeed scans backwards, filtering by the follow set.
May scan every tweet ever posted when the user follows quiet people.
All tweets plus follow sets.
class Twitter { private final List<int[]> tweets = new ArrayList<>(); // [userId, tweetId], oldest first private final Map<Integer, Set<Integer>> following = new HashMap<>(); public void postTweet(int userId, int tweetId) { tweets.add(new int[] {userId, tweetId}); } public List<Integer> getNewsFeed(int userId) { Set<Integer> follows = following.getOrDefault(userId, Set.of()); List<Integer> feed = new ArrayList<>(); for (int i = tweets.size() - 1; i >= 0 && feed.size() < 10; i--) { // newest first int author = tweets.get(i)[0]; if (author == userId || follows.contains(author)) feed.add(tweets.get(i)[1]); } return feed; } public void follow(int followerId, int followeeId) { following.computeIfAbsent(followerId, x -> new HashSet<>()).add(followeeId); } public void unfollow(int followerId, int followeeId) { Set<Integer> set = following.get(followerId); if (set != null) set.remove(followeeId); }}Seed a max-heap (by timestamp) with the newest tweet of each followee and yourself; pop 10, pushing each popped user's next-older tweet.
- Global clock stamps every tweet.
- Feed: heap of [time, tweetId, user, index].
- Pop up to 10; after each pop offer that user's previous tweet.
F = followees + 1 seeds the heap; then 10 pops/offers of O(log F). post/follow/unfollow are O(1).
Tweets, follow sets, and a heap of ≤ F cursors.
class Twitter { private int clock = 0; // global timestamp private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // user → [time, tweetId], oldest first private final Map<Integer, Set<Integer>> following = new HashMap<>(); public void postTweet(int userId, int tweetId) { tweets.computeIfAbsent(userId, x -> 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); // max-heap of cursors [time, tweetId, userId, index] — newest tweet on top (k-way merge) PriorityQueue<int[]> heap = 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()) { int last = list.size() - 1; heap.offer(new int[] {list.get(last)[0], list.get(last)[1], u, last}); } } List<Integer> feed = new ArrayList<>(); while (!heap.isEmpty() && feed.size() < 10) { int[] top = heap.poll(); feed.add(top[1]); int prev = top[3] - 1; // that user's next-older tweet if (prev >= 0) { int[] t = tweets.get(top[2]).get(prev); heap.offer(new int[] {t[0], t[1], top[2], prev}); } } return feed; } public void follow(int followerId, int followeeId) { following.computeIfAbsent(followerId, x -> new HashSet<>()).add(followeeId); } public void unfollow(int followerId, int followeeId) { Set<Integer> set = following.get(followerId); if (set != null) set.remove(followeeId); }}in the room
How to say it in the interview
talk track
- Name the pattern: "the feed is a k-way merge of sorted per-user timelines."
traps
- Letting a user unfollow themselves remove their own tweets — always include userId in the sources.
- Ordering by tweetId instead of a timestamp — ids are not chronological.
what they ask next
Follow-ups
Return the newest k tweets instead of 10?
Same merge, just stop after k pops: O(F log F + k log F) per feed, with F = followees + 1.
What if one user has millions of followers?
Two classic options. Fan-out on write: on post, push the tweet id into every follower's stored feed, so reads are cheap. Fan-out on read: merge at read time, as here. Big systems mix them — push for normal users, merge on read for very popular ones.
before you submit
Edge cases to test
- The user follows nobody: the feed is just their own tweets.
- Unfollowing someone you don't follow must not crash, and you always see your own tweets.
- Tweet ids are not in time order — order by a timestamp, never by id.
practise next
Similar problems
- #23Merge k Sorted ListsHardin Heaps
- #146LRU CacheMediumin Linked Lists