設計一個簡化版 Twitter。使用者可以發推文、追蹤/取消追蹤其他使用者，並看到自己動態牆中最近的 10 則推文（來自自己和追蹤的人），按時間由新到舊排序。
Example:
Input: [“Twitter”, “postTweet”, “getNewsFeed”, “follow”, “getNewsFeed”, “unfollow”, “getNewsFeed”] [[], [1, 5], [1], [1, 2], [1], [1, 2], [1]] Output: [null, null, [5], null, [5, 6], null, [5]]
Intuition
TIP
核心思路：合併 K 個有序列表問題——每個使用者的推文按時間排序，用 Min Heap 合併取前 10 則。
- 每個使用者有自己的推文列表（時間排序）
getNewsFeed需要合併自己和所有追蹤者的推文，取最新 10 則- 這就是 Merge K Sorted Lists 的經典應用，用 Heap 可以高效完成
Approaches
1. Merge Sort — O(N log N) / O(N)
- Idea: 收集所有相關推文放入列表，按時間排序，取前 10 個
- Time:
O(N log N)- N 為所有相關推文數 - Space:
O(N)
class Twitter() {
private var timestamp = 0
private val tweets = HashMap<Int, MutableList<Pair<Int, Int>>>() // userId -> [(time, tweetId)]
private val following = HashMap<Int, HashSet<Int>>() // userId -> followeeIds
fun postTweet(userId: Int, tweetId: Int) {
tweets.getOrPut(userId) { mutableListOf() }.add(timestamp++ to tweetId)
}
fun getNewsFeed(userId: Int): List<Int> {
val allTweets = mutableListOf<Pair<Int, Int>>()
val users = following.getOrPut(userId) { hashSetOf() } + userId
for (u in users) {
tweets[u]?.let { allTweets.addAll(it) }
}
allTweets.sortByDescending { it.first }
return allTweets.take(10).map { it.second }
}
fun follow(followerId: Int, followeeId: Int) {
following.getOrPut(followerId) { hashSetOf() }.add(followeeId)
}
fun unfollow(followerId: Int, followeeId: Int) {
following[followerId]?.remove(followeeId)
}
}⭐ 2. Max Heap (Merge K Sorted Lists) — O(k log k) / O(k)
- Idea: 將每個使用者最新的推文放入 Max Heap，每次取出最新的，再放入該使用者的下一則推文，直到取滿 10 則
- Time:
O(k log k)getNewsFeed - k 為追蹤人數（最多取 10 則） - Space:
O(k)為 heap 大小
class Twitter() {
private var timestamp = 0
private val tweets = HashMap<Int, MutableList<IntArray>>() // userId -> [[time, tweetId], ...]
private val following = HashMap<Int, HashSet<Int>>()
fun postTweet(userId: Int, tweetId: Int) {
tweets.getOrPut(userId) { mutableListOf() }.add(intArrayOf(timestamp++, tweetId))
}
fun getNewsFeed(userId: Int): List<Int> {
val result = mutableListOf<Int>()
// Max Heap: (time, tweetId, userId, index in that user's tweet list)
val maxHeap = PriorityQueue<IntArray>(compareByDescending { it[0] })
val users = (following[userId] ?: emptySet()) + userId
for (u in users) {
val userTweets = tweets[u]
if (!userTweets.isNullOrEmpty()) {
val lastIdx = userTweets.lastIndex
val tweet = userTweets[lastIdx]
maxHeap.offer(intArrayOf(tweet[0], tweet[1], u, lastIdx))
}
}
while (maxHeap.isNotEmpty() && result.size < 10) {
val (_, tweetId, userId2, idx) = maxHeap.poll()
result.add(tweetId)
if (idx > 0) {
val prevTweet = tweets[userId2]!![idx - 1]
maxHeap.offer(intArrayOf(prevTweet[0], prevTweet[1], userId2, idx - 1))
}
}
return result
}
fun follow(followerId: Int, followeeId: Int) {
following.getOrPut(followerId) { hashSetOf() }.add(followeeId)
}
fun unfollow(followerId: Int, followeeId: Int) {
following[followerId]?.remove(followeeId)
}
}🔑 Takeaways
- Pattern: 合併 K 個有序列表 → Heap 是標準做法
- Key trick: 系統設計題的核心在資料結構選擇；每個使用者推文按時間排序存儲，合併時只需把各列表的指標放入 Heap