355. Design Twitter

Medium

Description

設計一個簡化版 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#

核心思路：合併 K 個有序列表問題——每個使用者的推文按時間排序，用 Min Heap 合併取前 10 則。

每個使用者有自己的推文列表（時間排序）
getNewsFeed 需要合併自己和所有追蹤者的推文，取最新 10 則
這就是 Merge K Sorted Lists 的經典應用，用 Heap 可以高效完成

Approaches#

1: 合併排序#

概念: 收集所有相關推文放入列表，按時間排序，取前 10 個
時間複雜度: O(N log N) - N 為所有相關推文數
空間複雜度: 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)#

概念: 將每個使用者最新的推文放入 Max Heap，每次取出最新的，再放入該使用者的下一則推文，直到取滿 10 則
時間複雜度: O(k log k) getNewsFeed - k 為追蹤人數（最多取 10 則）
空間複雜度: 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 是標準做法
關鍵技巧: 系統設計題的核心在資料結構選擇；每個使用者推文按時間排序存儲，合併時只需把各列表的指標放入 Heap