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

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

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

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

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

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

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

這幾個(gè) API 中大部分都很好實(shí)現(xiàn)，最核心的功能難點(diǎn)應(yīng)該是 getNewsFeed，因?yàn)榉祷氐慕Y(jié)果必須在時(shí)間上有序，但問題是用戶的關(guān)注是動(dòng)態(tài)變化的，怎么辦？

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

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

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

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

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

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

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

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

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

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

3、幾個(gè) API 方法的實(shí)現(xiàn)

三、算法設(shè)計(jì)

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

如果你對優(yōu)先級隊(duì)列不太了解，可以理解為它可以對插入的元素自動(dòng)排序。亂序的元素插入其中就被放到了正確的位置，可以按照從小到大（或從大到小）有序地取出元素。

PriorityQueue pq
# 亂序插入
for i in {2,4,1,9,6}:
    pq.add(i)
while pq not empty:
    # 每次取出第一個(gè)（最小）元素
    print(pq.pop())

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

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

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

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

四、最后總結(jié)

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

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

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

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