Design Twitter

The link to question is lettcode/design-twitter.

The question is asking us to design a simple twitter like class. It has four functions: - To create a post. - To follow another user. - To unfollow any user. - To get newsfeed which comprises of ten recent post from the people user is following and himself.

This question is somewhat advanced level to solve it one should already be adept in other datastructures like array and have some idea about sorting. Before doing this you can solve this question first.

Now that the basic gist of question is clear, let’s solve it. let’s break it down.

Twitter Design

To follow users

Let’s start thinking, this function takes the followerId and followeeId and we need to connect two id together. Now one user can have many followers and user can also follow many other users.

To resolve this problme one can use hashmap where every followerId is key and which will sotre a set with every followeeId. This way every time new followeeId is added to specific followerId it will solve all the problem.

To unfollow users

In previous section we made the hashmao so to unfollow just remove the followeeId from the set of followekId.

To create new post

Now we can store the tweets in hasmap but with key as userId and tweets can be stored into a queue. This way when we retrive the posts accordingly to the order they are created.

To create newsfeed

To create news feed we will just merge the arrays gotten from the different users from his followers List according to the hashmap. Just like merging k sorted list.

Now let’s see the code.

class Twitter:
    def __init__(self):
        self.count = 0
        self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]
        self.followMap = defaultdict(set)  # userId -> set of followeeId

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append([self.count, tweetId])
        self.count -= 1

    def getNewsFeed(self, userId: int) -> List[int]:
        res = []
        minHeap = []

        self.followMap[userId].add(userId)
        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap:
                index = len(self.tweetMap[followeeId]) - 1
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        while minHeap and len(res) < 10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            res.append(tweetId)
            if index >= 0:
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])
        return res

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)

Hope this helps you. If you got any message for me just ping me using my socials.