355. Design Twitter

Question: Design Twitter

Solution

想法：

1. follower & followee (follow/unfollow)

   一個 user 對應到他的 followee → userId: set of followeeId

   follow: set.add(followeeId)

   unfollow: set.remove(followeeId)

2. user & posts (postTweet)

   一個 user 對應到他的 posts，文章有新舊，順序的問題，所以用有序的 list 儲存，append 新的文章，越新的在越尾巴 → userId: list of posts

3. getNewsFeed

   找到最近的 10 篇文章 → 文章用 time 排序，找最小的前 10 → min Heap

1. 把所有 followeeId 找出來，包含自己的 id，用此 id 對照 user_posts ，把最後一篇文章找出來(list 的最後一個 index)，放入 min Heap 中，儲存的值包含[時間, tweetId, 該 followeeId, post index - 1(讓我們可以往前一篇文章追尋)]，min Heap 的排序就用”時間”。
2. 放完一輪以後，pop min Heap 的最小值，放到 result 中，並把他前一篇文章 heappush 到 min Heap 中，儲存的值一樣要包含[時間, tweetId, 該 followeeId, post index - 1]。
3. 一直 pop 到 result 滿 10 個為止，或是 min Heap 裡沒有東西了！

import heapq

from collections import defaultdict

class Twitter:

def __init__(self):

self.time = 0

self.user_posts = defaultdict(list) # userId -> posts: list() [time, tweetId]

self.user_followee = defaultdict(set) # userId -> followees: set() {userId}

def postTweet(self, userId: int, tweetId: int) -> None:

self.user_posts[userId].append([self.time, tweetId])

self.time -= 1

def getNewsFeed(self, userId: int) -> list[int]:

res = list()

posts = list()

self.user_followee[userId].add(userId)

followees = self.user_followee[userId]

for followee_id in followees:

if followee_id in self.user_posts:

latest_post_index = len(self.user_posts[followee_id]) - 1

time, tweet_id = self.user_posts[followee_id][latest_post_index]

posts.append([time, tweet_id, followee_id, latest_post_index - 1])

heapq.heapify(posts)

while posts and len(res) < 10:

time, tweet_id, followee_id, latest_post_index = heapq.heappop(posts)

res.append(tweet_id)

time, tweet_id = self.user_posts[followee_id][latest_post_index]

if latest_post_index >= 0:

heapq.heappush(posts, [time, tweet_id, followee_id, latest_post_index - 1])

return res

def follow(self, followerId: int, followeeId: int) -> None:

self.user_followee[followerId].add(followeeId)

def unfollow(self, followerId: int, followeeId: int) -> None:

if followeeId in self.user_followee[followerId]:

self.user_followee[followerId].remove(followeeId

Video Solution