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

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

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

一、題目及應(yīng)用場景簡介

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

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

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

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

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

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

二、面向?qū)ο笤O(shè)計

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

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

1、Tweet 類的實現(xiàn)

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

2、User 類的實現(xiàn)

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

除此之外，根據(jù)面向?qū)ο蟮脑O(shè)計原則，「關(guān)注」「取關(guān)」和「發(fā)文」應(yīng)該是 User 的行為，況且關(guān)注列表和推文列表也存儲在 User 類中，所以我們也應(yīng)該給 User 添加 follow，unfollow 和 post 這幾個方法：

3、幾個 API 方法的實現(xiàn)

三、算法設(shè)計

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

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

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

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

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

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

四、最后總結(jié)

本文運用簡單的面向?qū)ο蠹记珊秃喜?k 個有序鏈表的算法設(shè)計了一套簡化的時間線功能，這個功能其實廣泛地運用在許多社交應(yīng)用中。

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

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

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