-
Notifications
You must be signed in to change notification settings - Fork 0
099 — Design Twitter
LeetCode 355 · Medium. Design a simplified Twitter. Implement postTweet(_ userId: Int, _ tweetId: Int), getNewsFeed(_ userId: Int) -> [Int] (the 10 most recent tweet IDs from the user and everyone they follow, most recent first), follow(_ followerId: Int, _ followeeId: Int), and unfollow(_ followerId: Int, _ followeeId: Int).
Picture flipping through several separate photo albums — one per person you follow — where each album is already arranged newest-photo-first. To build a combined "most recent 10" feed, you don't need to dump every photo from every album onto one big table and sort the whole pile. You just need to look at the front photo of each album, take whichever one is newest, and — this is the trick — only then peek at the next photo behind it in that same album, since that's the only album whose "front" just changed. This is exactly Merge k Sorted Lists's technique, aimed at a social feed instead of linked lists.
"Combine the most recent items from several already-time-ordered sources into one combined top-N list" — "news feed," "merge sorted streams," "most recent across many followed accounts" — is the K-way merge signature. Each source is already sorted, so a heap seeded with one candidate per source (and refilled from that same source after each pop) produces the combined order without ever fully re-sorting anything.
Log every tweet ever posted, globally, with a timestamp. getNewsFeed filters that entire history down to the user's own tweets plus their followees' tweets, sorts what's left by time, and takes the top 10 — mirroring how chapter 73's LRU Cache brute force used a plain array and paid for a full scan on every operation.
class TwitterBruteForce {
private var tweets: [(time: Int, userId: Int, tweetId: Int)] = []
private var following: [Int: Set<Int>] = [:]
private var clock = 0
func postTweet(_ userId: Int, _ tweetId: Int) {
tweets.append((clock, userId, tweetId))
clock += 1
}
func getNewsFeed(_ userId: Int) -> [Int] {
let followees = following[userId] ?? []
let relevant = tweets.filter { $0.userId == userId || followees.contains($0.userId) }
let sorted = relevant.sorted { $0.time > $1.time }
return sorted.prefix(10).map { $0.tweetId }
}
func follow(_ followerId: Int, _ followeeId: Int) {
following[followerId, default: []].insert(followeeId)
}
func unfollow(_ followerId: Int, _ followeeId: Int) {
following[followerId]?.remove(followeeId)
}
}
// smoke test — mirrors LeetCode's canonical walkthrough
let bfTwitter = TwitterBruteForce()
bfTwitter.postTweet(1, 5)
print(bfTwitter.getNewsFeed(1)) // [5]
bfTwitter.follow(1, 2)
bfTwitter.postTweet(2, 6)
print(bfTwitter.getNewsFeed(1)) // [6, 5]
bfTwitter.unfollow(1, 2)
print(bfTwitter.getNewsFeed(1)) // [5]Big-O: postTweet is O(1). getNewsFeed is O(T log T), where T is the total number of tweets ever posted by anyone — the filter is O(T) and the sort is O(T log T), no matter how few people the user actually follows. follow/unfollow are O(1) average.
Store each user's own tweets chronologically (append-only, so each user's list is already sorted). For getNewsFeed, seed a max-heap with the single most recent tweet from each relevant author (self plus followees). Repeatedly pop the overall most recent tweet, and — only for the author whose tweet just got popped — push that author's next-most-recent tweet in to replace it. Stop after 10 pops or an empty heap.
struct Heap<T> {
private var elements: [T] = []
private let areInIncreasingOrder: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.areInIncreasingOrder = sort
}
var isEmpty: Bool { elements.isEmpty }
var count: Int { elements.count }
var peek: T? { elements.first }
mutating func insert(_ value: T) {
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func extract() -> T? {
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let top = elements.removeLast()
siftDown(from: 0)
return top
}
private mutating func siftUp(from index: Int) {
var child = index
var parent = (child - 1) / 2
while child > 0 && areInIncreasingOrder(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = (child - 1) / 2
}
}
private mutating func siftDown(from index: Int) {
var parent = index
while true {
let left = 2 * parent + 1
let right = 2 * parent + 2
var candidate = parent
if left < elements.count && areInIncreasingOrder(elements[left], elements[candidate]) {
candidate = left
}
if right < elements.count && areInIncreasingOrder(elements[right], elements[candidate]) {
candidate = right
}
if candidate == parent { return }
elements.swapAt(parent, candidate)
parent = candidate
}
}
}
final class Twitter {
private struct Tweet {
let time: Int
let tweetId: Int
}
private var tweetsByUser: [Int: [Tweet]] = [:] // chronological (oldest first) per user
private var following: [Int: Set<Int>] = [:]
private var clock = 0
func postTweet(_ userId: Int, _ tweetId: Int) {
tweetsByUser[userId, default: []].append(Tweet(time: clock, tweetId: tweetId))
clock += 1
}
func getNewsFeed(_ userId: Int) -> [Int] {
var authors = following[userId] ?? []
authors.insert(userId) // you always see your own tweets
// max-heap keyed by time; each entry also carries the index of the
// *next* (older) tweet to pull from that same author, for the merge.
var heap = Heap<(time: Int, tweetId: Int, author: Int, index: Int)>(sort: { $0.time > $1.time })
for author in authors {
if let userTweets = tweetsByUser[author], !userTweets.isEmpty {
let lastIndex = userTweets.count - 1
let t = userTweets[lastIndex]
heap.insert((t.time, t.tweetId, author, lastIndex))
}
}
var result: [Int] = []
while result.count < 10, let top = heap.extract() {
result.append(top.tweetId)
if top.index > 0 {
let nextIndex = top.index - 1
let t = tweetsByUser[top.author]![nextIndex]
heap.insert((t.time, t.tweetId, top.author, nextIndex))
}
}
return result
}
func follow(_ followerId: Int, _ followeeId: Int) {
guard followerId != followeeId else { return }
following[followerId, default: []].insert(followeeId)
}
func unfollow(_ followerId: Int, _ followeeId: Int) {
following[followerId]?.remove(followeeId)
}
}
// smoke test — same walkthrough as the brute force
let twitter = Twitter()
twitter.postTweet(1, 5)
print(twitter.getNewsFeed(1)) // [5]
twitter.follow(1, 2)
twitter.postTweet(2, 6)
print(twitter.getNewsFeed(1)) // [6, 5]
twitter.unfollow(1, 2)
print(twitter.getNewsFeed(1)) // [5]
// multi-tweet merge check — one followee with several tweets must come back
// in correct newest-first order via the "advance the pointer" step
let twitter2 = Twitter()
twitter2.follow(1, 2)
twitter2.postTweet(2, 10)
twitter2.postTweet(2, 11)
twitter2.postTweet(2, 12)
print(twitter2.getNewsFeed(1)) // [12, 11, 10]Big-O: getNewsFeed is O((F + 1) log(F + 1)) — the heap only ever holds one entry per relevant author (F followees plus the user), and at most 10 pop/push rounds happen, each O(log(F + 1)). postTweet is O(1) amortized. follow/unfollow are O(1) average. Crucially, cost tracks the number of people the user follows, never the total tweet history across the whole platform.
The brute force's waste is re-discovering, from scratch, an ordering that already partially exists: each individual author's tweets are already time-sorted the moment they're posted (nothing ever needs re-sorting within one author's list) — the only genuinely unsolved question is how to interleave several already-sorted lists together. That's precisely what a K-way merge does: seed a heap with one "current candidate" per source, and every time a candidate is consumed, reveal that same source's next candidate — nothing else in the heap needs to be touched. The heap's size tracks the number of sources (followees), not the size of everyone's combined history, which is what keeps getNewsFeed fast even as the platform's total tweet count grows unboundedly.
- Heaps and Priority Queues — the max-heap keyed by timestamp that drives the merge.
- Top K and Heap Pattern — bounding the result to the top 10 most-recent items is the pattern's "top K" shape, applied to a merge instead of a plain scan.
- Merge k Sorted Lists — the exact same "seed a heap with one candidate per source, replace only the consumed one" technique, there applied to linked lists instead of per-user tweet arrays.
-
Hash Maps and Hash Sets — both
tweetsByUserandfollowingare hash maps keyed by user ID, givingO(1)access to "this user's tweets" and "this user's followees" without scanning.
Design Twitter's news feed is a stack of newest-first photo albums, one per followee — a max-heap always knows whose front photo is newest, and only that one album ever needs its next photo revealed.
- Why does
getNewsFeedonly ever push a new candidate from the author whose tweet was just popped, rather than pushing all of that author's remaining tweets up front? -
postTweetin the optimal solution never touches the heap at all. Why is that safe — what guarantees that a tweet posted "in the past" (before the currentgetNewsFeedcall) is still findable when needed? - Why does the optimal solution always insert
userIditself intoauthors, even when the user isn't in their ownfollowingset? - Compare the two Big-O costs for
getNewsFeed: the brute force'sO(T log T)versus the optimal'sO((F + 1) log(F + 1)). In a platform with millions of tweets but a user who follows only a handful of accounts, which term dominates the brute force's cost —Tor the sort'slog?
⬅️ Previous: Task Scheduler · Next: Find Median from Data Stream ➡️