355. Design Twitter

# Medium

Key idea: data structure

use postStack to store tweets in order

use dictionary to store user-follows {user: set(followee)}

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.postStack = []  # [[userID, tweeetID]]
        self.users = {}   # {userID: set(followeeID)}
        

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        if userId not in self.users:
            self.users[userId] = set()
        self.postStack.append([userId, tweetId])
        # print("users", self.users)
        # print("posts", self.postStack)
        

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """
        # edge case, if no user information, then return []
        if userId not in self.users:
            return []
        
        # regular case, if user in self.users
        res = []
        n = 10
        for post in reversed(self.postStack):
            if n >= 1 and (post[0] == userId or post[0] in self.users[userId]):
                res.append(post[1])
                n -= 1
                
        # print("users", self.users)
        # print("posts", self.postStack)
        return res

        

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        # only when followee has existed in this user's followee list, then no operation
        if followerId in self.users:
            self.users[followerId].add(followeeId)
        else:
            self.users[followerId] = {followeeId}

        # print("follow", self.users)
        

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        # if follower doesn't exist in self.users, then no operation
        if followerId in self.users:
            self.users[followerId].discard(followeeId)
        # print("unfollow", self.users)
        


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

postTweet() should add userId into self.users.

no operation about follow() and unfollow() because this followee has been followed or not been followed.

运行速度非常慢

set()

set.add(value) 如果要添加的数已存在则无任何操作，set.remove(value)如果要移除的数不存在则报错，set.discard(value)如果要移除的数不存在则无任何操作