The problem
Design a tiny Twitter: users can post, follow, unfollow, and get a news feed of the 10 most recent posts from themselves and the people they follow.
Input: post 1 5, feed 1, follow 1 2, post 2 6, post 1 7, feed 1, unfollow 1 2, feed 1 Output: [5], [7, 6, 5], [7, 5]
Picture it
Picture each user with their own stack of posts, newest on top, each stamped with a time. To build a feed, look at the top post of your own pile and of each person you follow, and put those into a heap ordered by time. Repeatedly take the newest, and replace it with the next post from the same person’s pile.
How to recognise it
- It is a design problem: a class with several operations (postTweet, follow, unfollow, getNewsFeed) and a hidden question about which one is hot.
- The feed needs the 10 most recent items out of several sources (you and everyone you follow). Each source is already in time order.
- "Merge several sorted lists and stop after a few items" is the signal for a heap (a tree stored in a list with O(log n) push and pop) or a partial sort.
- Following and unfollowing are add and remove on a set of people, so a hash set per user gives O(1) for both.
- The limits are up to 3 × 10^4 calls and at most 500 users, so a feed must not scan every post ever made.
Start with brute force
Keep one global list of all posts. For a feed, filter the posts written by you or someone you follow, sort them newest first, and take 10.
from collections import defaultdict
class TwitterBrute:
def __init__(self):
self.time = 0
self.all_posts = [] # (time, user, tweet)
self.follows = defaultdict(set)
def postTweet(self, user, tweet):
self.time += 1
self.all_posts.append((self.time, user, tweet))
def getNewsFeed(self, user):
people = self.follows[user] | {user}
mine = [p for p in self.all_posts if p[1] in people]
mine.sort(reverse=True)
return [tweet for _, _, tweet in mine[:10]]
def follow(self, a, b): self.follows[a].add(b)
def unfollow(self, a, b): self.follows[a].discard(b)
Every feed touches all posts and sorts the relevant ones: O(P log P) for P posts. With 10^4 posts and 10^4 feed calls that is about 10^4 × 10^4 × 13, roughly 10^9 steps. Space is O(P).
From brute force to the idea
- Find the waste. Only 10 posts are shown, yet the brute force sorts everything.
- Split posts by author. Each user keeps their own list, already in time order because posts are appended with an increasing time stamp.
- Only the last 10 of each person can matter. The newest 10 overall can include at most 10 from any single author, so take
posts[p][-10:]. - Select the 10 newest of the candidates. Build tuples
(-time, tweet); the most negative is the newest.nsmallest(10, ...)uses a heap of size 10 internally and returns them newest first. - Use sets for people.
follows[user] | {user}adds yourself without storing a self-follow.
This is the key idea: per-user post lists, at most 10 candidates from each followed person, and a heap-based selection of the 10 newest.
The key idea
Merge k sorted lists with a heap, stopping after 10 posts. Follow sets are hash sets.
Python solution
class Twitter:
def __init__(self):
self.time = 0
self.posts = defaultdict(list) # user -> [(time, id)]
self.follows = defaultdict(set)
def postTweet(self, user, tweet):
self.time += 1
self.posts[user].append((self.time, tweet))
def getNewsFeed(self, user):
people = self.follows[user] | {user}
heap = [(-t, id) for p in people for t, id in self.posts[p][-10:]]
return [id for _, id in nsmallest(10, heap)] # newest first
def follow(self, a, b): self.follows[a].add(b)
def unfollow(self, a, b): self.follows[a].discard(b)LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict from heapq import nsmallest
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | postTweet O(1); getNewsFeed O(P log P) for all P posts; follow and unfollow O(1) | O(P) |
Per-user lists and nsmallest (shown code) | postTweet, follow, unfollow O(1) on average; getNewsFeed O(F · 10) to collect candidates, then about O(F · 10 · log 10) to select, F = people followed | O(P) for all posts, O(F) extra per feed |
Edge cases
- New user with no posts or follows:
getNewsFeedreturns[]. - Following yourself or unfollowing someone you never followed: harmless;
discarddoes not raise. Your own posts stay in your feed even afterunfollow(1, 1), becausegetNewsFeedadds you back. - Unfollow removes their posts at once: a feed is rebuilt each call, so nothing stale remains.
- Fewer than 10 posts: you get all of them.
- Example: post 1 → 5, feed gives
[5]; follow 2, post 2 → 6, post 1 → 7, feed gives[7, 6, 5]; unfollow 2, feed gives[7, 5]. - Imports: the snippet needs
from collections import defaultdictandfrom heapq import nsmallest(LeetCode adds them for you).
Common mistakes
- Taking the oldest 10 of each user (
posts[p][:10]) instead of the newest. A user with 12 posts then shows tweets 10 down to 1. - Sorting by tweet id instead of by a time stamp. Ids need not grow with time.
- Using a list for follows so the same follow is stored twice.
- Forgetting to include the user's own posts.
Change getNewsFeed so the caller chooses the length: getNewsFeed(user, m) returns the m newest posts. Describe what changes, then write it if you like.
Compare with our answer
Both places that mention 10 must become m: the slice of each person's list and the selection. If you only change the selection, a user with more than 10 posts would still contribute at most 10 candidates and the feed would come up short.
from heapq import nsmallest
def getNewsFeed(self, user, m):
people = self.follows[user] | {user}
heap = [(-t, id) for p in people for t, id in self.posts[p][-m:]]
return [id for _, id in nsmallest(m, heap)] # newest first
Time is O(F · m) to collect and about O(F · m · log m) to select. For large m, merging the per-user lists lazily with a heap that holds one entry per person does better, because it never looks at more than m posts in total.
A strong answer mentions: changing both the per-person slice and the selection, why one of them alone is a bug, and the cost in terms of F and m.
1. A forum shows each reader the 20 newest comments out of the threads they watch (each thread's comments are stored oldest to newest). Which approach fits best?
Only the last 20 of any one thread can reach the top 20, so a small candidate set and a heap-based selection avoid scanning history. The second and third options touch every comment, and storing one list per reader is much more write work.
2. What does nsmallest(10, heap) cost in the shown getNewsFeed, if the candidate list has c entries?
It scans all c candidates once and keeps a heap of the best 10, so each candidate costs at most log 10. It does not sort everything, and it cannot ignore candidates it has not seen.
3. A learner changes self.posts[p][-10:] to self.posts[p][:10]. Which test exposes the bug?
The change takes each person's first 10 posts, not the last 10. That only matters when someone has more than 10 posts: with 12, the feed shows tweets 10 down to 1 instead of 12 down to 3. In the other tests nobody has more than 5 posts, so the slice covers everything.
Score 60% or more and the lesson is marked complete.