iT邦幫忙

2021 iThome 鐵人賽

DAY 29
0
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 29

【第二十九天 - 系統分析 題目分析】

  • 先簡單回顧一下,今天預計分析的題目:
  • 題目連結: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。

https://ithelp.ithome.com.tw/upload/images/20210929/20140592crhfmeWFU8.png

  • 測資的 Input/Output

    • 根據每個函數實作並回傳相關資料
    • 不需真的讀取 ["Twitter", "postTweet", ....] 或回傳 [null, null, ....]
      https://ithelp.ithome.com.tw/upload/images/20210929/20140592Z7fWAULsFx.png
  • 首先我們實作 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)

上一篇
【第二十八天 - 系統設計 介紹】
下一篇
【第三十天 - 結論】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言