【第二十九天 - 系统分析 题目分析】

• 先简单回顾一下，今天预计分析的题目：
• 题目连结：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)