「design Twitter」是 LeetCode 上第 335 道題目，讓我們設計 Twitter 的一些功能。不僅題目很有意思，而且把合并多個有序鏈表的算法和面向對象設計（OO design）結合起來了，很有實際意義，本文就帶大家來看看這道題。

至于 Twitter 的什么功能跟算法有關系，等我們描述一下題目要求就知道了。

PS：文末「閱讀原文」按鈕附大型系統(tǒng)設計學習資源的 Github 鏈接。

一、題目及應用場景簡介

Twitter 和微博功能差不多，我們主要要實現這樣幾個 API：

舉個具體的例子，方便大家理解 API 的具體用法：

這個場景在我們的現實生活中非常常見。拿朋友圈舉例，比如我剛加到女神的微信，然后我去刷新一下我的朋友圈動態(tài)，那么女神的動態(tài)就會出現在我的動態(tài)列表，而且會和其他動態(tài)按時間排好序。只不過 Twitter 是單向關注，微信好友相當于雙向關注。除非，被屏蔽...

這幾個 API 中大部分都很好實現，最核心的功能難點應該是 getNewsFeed，因為返回的結果必須在時間上有序，但問題是用戶的關注是動態(tài)變化的，怎么辦？

這里就涉及到算法了：如果我們把每個用戶各自的推文存儲在鏈表里，每個鏈表節(jié)點存儲文章 id 和一個時間戳 time（記錄發(fā)帖時間以便比較），而且這個鏈表是按 time 有序的，那么如果某個用戶關注了 k 個用戶，我們就可以用合并 k 個有序鏈表的算法合并出有序的推文列表，正確地 getNewsFeed 了！

具體的算法等會講解。不過，就算我們掌握了算法，應該如何編程表示用戶 user 和推文動態(tài) tweet 才能把算法流暢地用出來呢？這就涉及簡單的面向對象設計了，下面我們來由淺入深，一步一步進行設計。

二、面向對象設計

根據剛才的分析，我們需要一個 User 類，儲存 user 信息，還需要一個 Tweet 類，儲存推文信息，并且要作為鏈表的節(jié)點。所以我們先搭建一下整體的框架：

之所以要把 Tweet 和 User 類放到 Twitter 類里面，是因為 Tweet 類必須要用到一個全局時間戳 timestamp，而 User 類又需要用到 Tweet 類記錄用戶發(fā)送的推文，所以它們都作為內部類。不過為了清晰和簡潔，下文會把每個內部類和 API 方法單獨拿出來實現。

1、Tweet 類的實現

根據前面的分析，Tweet 類很容易實現：每個 Tweet 實例需要記錄自己的 tweetId 和發(fā)表時間 time，而且作為鏈表節(jié)點，要有一個指向下一個節(jié)點的 next 指針。

2、User 類的實現

我們根據實際場景想一想，一個用戶需要存儲的信息有 userId，關注列表，以及該用戶發(fā)過的推文列表。其中關注列表應該用集合（Hash Set）這種數據結構來存，因為不能重復，而且需要快速查找；推文列表應該由鏈表這種數據結構儲存，以便于進行有序合并的操作。畫個圖理解一下：

除此之外，根據面向對象的設計原則，「關注」「取關」和「發(fā)文」應該是 User 的行為，況且關注列表和推文列表也存儲在 User 類中，所以我們也應該給 User 添加 follow，unfollow 和 post 這幾個方法：

3、幾個 API 方法的實現

三、算法設計

實現合并 k 個有序鏈表的算法需要用到優(yōu)先級隊列（Priority Queue），這種數據結構是「二叉堆」最重要的應用。

如果你對優(yōu)先級隊列不太了解，可以理解為它可以對插入的元素自動排序。亂序的元素插入其中就被放到了正確的位置，可以按照從小到大（或從大到?。┯行虻厝〕鲈亍?/p>

PriorityQueue pq
# 亂序插入
for i in {2,4,1,9,6}:
    pq.add(i)
while pq not empty:
    # 每次取出第一個（最?。┰?/span>
    print(pq.pop())

# 輸出有序：1,2,4,6,9

借助這種牛逼的數據結構支持，我們就很容易實現這個核心功能了。注意我們把優(yōu)先級隊列設為按 time 屬性從大到小降序排列，因為 time 越大意味著時間越近，應該排在前面：

這個過程是這樣的，下面是我制作的一個 GIF 圖描述合并鏈表的過程。假設有三個 Tweet 鏈表按 time 屬性降序排列，我們把他們降序合并添加到 res 中。注意圖中鏈表節(jié)點中的數字是 time 屬性，不是 id 屬性：

至此，一個簡化的 Twitter 時間線功能就設計完畢了。

四、最后總結

本文運用簡單的面向對象技巧和合并 k 個有序鏈表的算法設計了一套簡化的時間線功能，這個功能其實廣泛地運用在許多社交應用中。

我們先合理地設計出 User 和 Tweet 兩個類，然后基于這個設計之上運用算法解決了最重要的一個功能?？梢妼嶋H應用中的算法并不是孤立存在的，需要和其他知識混合運用，才能發(fā)揮實際價值。

當然，實際應用中的社交 App 數據量是巨大的，考慮到數據庫的讀寫性能，我們的設計可能承受不住流量壓力，還是有些太簡化了。而且實際的應用都是一個極其龐大的工程，比如下圖，是 Twitter 這樣的社交網站大致的系統(tǒng)結構：

我們解決的問題應該只能算 Timeline Service 模塊的一小部分，功能越多，系統(tǒng)的復雜性可能是指數級增長的。所以說合理的頂層設計十分重要，其作用是遠超某一個算法的。