TL;DR
Per-user tweet lists + follow sets, feed built by a heap k-way merge: getNewsFeed is O(F log F) for F followees; other ops O(1).
Approach 1 — Naive design (one global timeline)
This is a design problem, so there is no brute-force algorithm to speak of. Start with the simplest design that works: store every tweet in one global list and filter it per feed request.
from typing import List
class Twitter:
def __init__(self):
self.timeline: list[tuple[int, int]] = [] # (userId, tweetId), oldest first
self.following: dict[int, set[int]] = {}
def postTweet(self, userId: int, tweetId: int) -> None:
self.timeline.append((userId, tweetId))
def getNewsFeed(self, userId: int) -> List[int]:
allowed = self.following.get(userId, set()) | {userId}
feed = []
for uid, tid in reversed(self.timeline):
if uid in allowed:
feed.append(tid)
if len(feed) == 10:
break
return feed
def follow(self, followerId: int, followeeId: int) -> None:
self.following.setdefault(followerId, set()).add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
self.following.setdefault(followerId, set()).discard(followeeId)
This is correct and postTweet is O(1), but getNewsFeed walks the global timeline backwards and, when the user follows nobody active, scans every tweet ever posted: O(T) per feed. With 3·10^4 calls, feeds over a long timeline degrade toward ~10^8 tuple checks, which motivates sharding tweets by user.
Approach 2 — Per-user lists + heap k-way merge
The insight: each user’s own tweets are already in time order, so a feed is a merge of k sorted lists, and we only need the first 10 results of that merge. The tool for this is a heap-based k-way merge (the merge step of external sorting): seed a heap with the head of each list, pop the newest, push that list’s next element. It touches k + 10 tweets instead of all of them. A global monotonically increasing counter serves as the timestamp.
flowchart LR
A["User A tweets<br/>newest to oldest"] --> H
B["User B tweets<br/>newest to oldest"] --> H
C["User C tweets<br/>newest to oldest"] --> H
H["Max-heap of current heads<br/>at most F entries"] --> P["Pop newest into feed,<br/>push that user's next-older tweet"]
P -->|repeat up to 10 times| H
P --> F["Feed: 10 newest tweet ids"]
import heapq
from collections import defaultdict
from typing import List
class Twitter:
def __init__(self):
self.time = 0
self.tweets: defaultdict[int, list[tuple[int, int]]] = defaultdict(list)
self.following: defaultdict[int, set[int]] = 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]:
heap: list[tuple[int, int, int, int]] = []
for uid in self.following[userId] | {userId}:
posts = self.tweets[uid]
if posts:
i = len(posts) - 1 # newest first
t, tid = posts[i]
heap.append((-t, tid, uid, i))
heapq.heapify(heap)
feed = []
while heap and len(feed) < 10:
_, tid, uid, i = heapq.heappop(heap)
feed.append(tid)
if i > 0:
t, next_tid = self.tweets[uid][i - 1]
heapq.heappush(heap, (-t, next_tid, uid, i - 1))
return feed
Walkthrough of the question’s example (timestamps assigned 0, 1, …):
postTweet(1, 5) → tweets[1] = [(0, 5)].getNewsFeed(1) → heap seeded with user 1’s newest: (-0, 5, 1, 0). Pop → feed [5]; index 0 has no older tweet, heap empty. Return [5].follow(1, 2); postTweet(2, 6) → tweets[2] = [(1, 6)].getNewsFeed(1) → seed with (-0, 5, 1, 0) and (-1, 6, 2, 0). Root is (-1, ...) (larger timestamp) → pop 6, then pop 5. Return [6, 5].unfollow(1, 2); getNewsFeed(1) → user 2 no longer seeded. Return [5].
Complexity: with F = number of followees (≤ 500), getNewsFeed seeds F heads (O(F) heapify) and does ≤ 10 pop/push rounds → O(F + 10 log F) = O(F log F) worst case, independent of total tweet count. postTweet, follow, unfollow are O(1). Space O(T + E) for T tweets and E follow edges.
Approach 3 — Merge by “collect 10 per followee, then nlargest” (the common shortcut)
The insight: a feed shows at most 10 tweets, so only each followee’s last 10 tweets can possibly appear. Gather ≤ 10F candidates and let heapq.nlargest(10, ...) (a heap under the hood) pick the winners — less bookkeeping than the streaming merge, same output.
import heapq
from collections import defaultdict
from typing import List
class Twitter:
def __init__(self):
self.time = 0
self.tweets: defaultdict[int, list[tuple[int, int]]] = defaultdict(list)
self.following: defaultdict[int, set[int]] = 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]:
candidates = []
for uid in self.following[userId] | {userId}:
candidates.extend(self.tweets[uid][-10:])
top = heapq.nlargest(10, candidates) # sorts by timestamp desc
return [tid for _, tid in top]
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)
On the walkthrough example the candidate pools are [(0, 5)] → [5], then [(0, 5), (1, 6)] → [6, 5], then [(0, 5)] → [5] — identical results. Complexity: O(10F) candidates, nlargest over them is O(10F log 10) → effectively O(F) per feed; slightly more tweets touched than Approach 2 (10 per followee instead of ~1 each), which is why the streaming merge is the “textbook” answer.
Common pitfalls
- Sorting tweets by
tweetId instead of a timestamp — ids carry no time meaning; you must mint your own monotonic counter.
- Letting a user follow themself (or storing the self-edge) and then double-counting their tweets in the feed; simplest is to union
{userId} at read time and discard rather than remove on unfollow.
- In the k-way merge, forgetting to push the next-older tweet of the user you just popped — the feed then contains at most one tweet per followee.
- Heap tie-breaking: tuples compare element-by-element, so after
-t the remaining fields must be comparable ints — putting a dict or None second crashes on timestamp ties (avoided here since timestamps are unique, but keep the tuple all-ints anyway).
Pattern takeaway
“Show the top 10 newest across several already-sorted sources” is a k-way merge: seed a heap with one head per source, pop and advance until you have enough. The heap holds k entries, not all the data, which is the difference between work proportional to the answer size and work proportional to the whole history. Design problems in this pattern reduce to keeping each source sorted by append order and merging lazily at query time.