• 先簡單回顧一下，今天預計分析的題目：
• 題目連結：https://leetcode.com/problems/design-twitter/
• 題目敘述
  • 設計一個簡化版的 twitter，主要實現如下功能：
    • User 可以發布推文
    • User 可以追蹤 / 取消追蹤其他 User
    • 可以看到一個 User 的 news feed 中，最近 10 篇的推文
  • Twitter class 要包含如下 methods:
    • Constructor
    • void postTweet(int userId, int tweetId) ：
      • 用來發布推文的 function。
      • 由 ID 為 userId 的 User 發布了 ID 為 tweetId 的推文。
      • 每次 call 這個 function 的 tweetId 必須 unique 。
    • List<Integer> getNewsFeed(int userId) ：
      • 取得 ID 為 userId 的 User 的 news feed 中最近的 10 篇推文。
      • 每一個推文必須是由該 User 所發布，或是由該 User 追蹤的 User 所發布。
      • 必須由最新到最舊排序。
    • void follow(int followerId, int followeeId) ：
      • 用於讓 ID 為 followerId 的 User 追蹤 ID 為 followeeId 的 User。
    • void unfollow(int followerId, int followeeId) ：
      • 用於讓 ID 為 followerId 的 User 取消追蹤 ID 為 followeeId 的 User。

• 測資的 Input/Output

  • 根據每個函數實作並回傳相關資料
  • 不需真的讀取 ["Twitter", "postTweet", ....] 或回傳 [null, null, ....]
    

• 首先我們實作 follow 功能。由於 followee 理論上不重複，我們對每個 user 建立一個 set 用於儲存 followee：

  def __init__(self):
      self.followees = defaultdict(set)
  
  def follow(self, followerId: int, followeeId: int) -> None:
      self.followees[followerId].add(followeeId)
  
  def unfollow(self, followerId: int, followeeId: int) -> None:
      self.followees[followerId].discard(followeeId)
  

  • 由於 User ID 沒有限制會照順序來，如果用 list 紀錄很可能會造成 sparse array，浪費效能，因此這邊使用 dict 來儲存對應關係。
  • 由於 dict 需要預先判斷該 key 是否存在，若不存在要初始化 set ，若存在則要新增到既有的 set ，較為麻煩，因此此處直接使用 defaultdict 幫助我們自動在該 key 第一次存取時進行初始化，因此我們可以當作 set 已經存在，只要 add / discard 即可。

• 接著我們來實現 post 功能。考慮到 getNewsFeed 會需要抓取最近的推文，但推文沒有保證 ID 越大的則越新，因此我們需要自己實作 timestamp 機制。

  def __init__(self):
      self.posts = defaultdict(list)
      self.timestamp = 0
  
  def postTweet(self, userId: int, tweetId: int) -> None:
      self.posts[userId].append((self.timestamp, tweetId))
      self.timestamp += 1
  

  • 為了方便抓取最新貼文，此處使用 list 紀錄每個 user 的推文，越往後則越新。
  • 推文時，除了紀錄 tweetId，還要一併紀錄當前的 timestamp ，此處直接建立 tuple ， append 到 list 中。
  • 推文後， timestamp +1 ，確保每個推文 unique ，且越新者 timestamp 越大

• 最後實作 getNewsFeed ，要從 User 的貼文與所有 followee 的貼文選出最新的十篇，此處我們可以先將所有人個別發布的最新十篇推文取出，再統一排序，取得真正最新的十篇

   def getNewsFeed(self, userId: int) -> List[int]:
        allTweets = set(self.posts[userId][-10:])
        for i in self.followees[userId]:
            allTweets.update(self.posts[i][-10:])
        return list(map(lambda x: x[1], sorted(allTweets, reverse=True)[:10]))
  

  • 由於題目沒有規定 user 不能 follow 自己，此處為了避免合併所有人的推文後有重複，使用了 set 來消除重複貼文
  • 搭配 sorted 可以幫助我們輕鬆排序，不過 sorted 預設順序為由小到大，因此加上 reverse 參數，改為由大到小，再取前 10 篇推文。
  • 最後，由於當初是儲存 (timestamp, tweetId) 的 tuple，此處用 map 取出 tweetId，即是答案。

• 完整 python 實作

class Twitter:

    def __init__(self):
        self.followees = defaultdict(set)
        self.posts = defaultdict(list)
        self.timestamp = 0
        
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.posts[userId].append((self.timestamp, tweetId))
        self.timestamp += 1
        
    def getNewsFeed(self, userId: int) -> List[int]:
        allTweets = set(self.posts[userId][-10:])
        for i in self.followees[userId]:
            allTweets.update(self.posts[i][-10:])
        return list(map(lambda x: x[1], sorted(allTweets, reverse=True)[:10]))

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followees[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.followees[followerId].discard(followeeId)