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)
There’s no meaningful “brute force algorithm” here — it’s a design problem — so the ladder starts at the simplest design that works: store every tweet ever posted 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)
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 — the interviewer’s cue to shard 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 classic tool is a heap-based k-way merge (the merge step of external sorting): seed a heap with the head of each list, pop the best, 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.
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 k-way merge territory: seed a heap with one head per source, pop-then-advance until you have enough. The heap holds k entries, not all the data — that’s the difference between work proportional to the answer size and work proportional to the whole history. Design problems in this pattern reduce to: keep each source sorted for free (append order), merge lazily at query time.