Design Twitter

Design Twitter requires implementing post, follow, unfollow, and news feed retrieval using linked-list pointer manipulation and hash maps efficiently.

hash table linked list design heap priority queue

Problem Statement

Design a simplified Twitter where users can post tweets, follow and unfollow other users, and retrieve the 10 most recent tweets in their news feed. Each tweet is identified by a unique ID, and the system must efficiently manage both user relationships and tweet ordering.

Implement the Twitter class with methods: postTweet(userId, tweetId) to add a tweet, getNewsFeed(userId) to return up to 10 recent tweets from the user and followed users, follow(followerId, followeeId) to follow another user, and unfollow(followerId, followeeId) to stop following. Tweets should be ordered from most recent to oldest, requiring careful linked-list pointer manipulation.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] Output [null, null, [5], null, null, [6, 5], null, [5]]

Explanation Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5). twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5]. return [5] twitter.follow(1, 2); // User 1 follows user 2. twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6). twitter.getNewsFeed(1); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5. twitter.unfollow(1, 2); // User 1 unfollows user 2. twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2.

Constraints

1 <= userId, followerId, followeeId <= 500
0 <= tweetId <= 104
All the tweets have unique IDs.
At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.
A user cannot follow himself.

Solution Approach

Use a Hash Map for User Relationships

Maintain a hash map mapping each user to a set of followees. This allows O(1) insertion and deletion when following or unfollowing users, and helps identify which tweets to include in the news feed efficiently.

Linked List for Tweets

Each user maintains a linked list of their own tweets, with new tweets inserted at the head. This pointer-based structure enables fast addition and allows merging of multiple user feeds efficiently while preserving order.

Heap to Aggregate News Feed

Use a max heap (priority queue) to merge tweets from the user and their followees by timestamp. Always extract the most recent tweet next to construct the news feed, ensuring the 10 most recent tweets are returned with correct ordering.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity varies by operation: posting is O(1), follow/unfollow is O(1), and getting the news feed is O(N log k) where N is total followed tweets and k is number of tweets to retrieve. Space complexity depends on the number of users and tweets stored, roughly O(U + T).

What Interviewers Usually Probe

Focus on correctly merging multiple user feeds while preserving tweet order.
Ensure follow/unfollow updates maintain user relationships in the hash map.
Handle edge cases like unfollowing a non-followed user or self-follow attempts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update pointers when inserting new tweets can break feed order.
Not limiting news feed to 10 most recent tweets leads to performance issues.
Incorrectly handling self-follow or unfollow scenarios can cause unexpected results.

Follow-up variants

Retrieve news feed with N most recent tweets instead of fixed 10.
Support deleting a tweet and updating feeds dynamically.
Implement trending tweets aggregation based on user likes or retweets.

FAQ

What data structures are essential for Design Twitter?

A hash map to track follow relationships, linked lists to store user tweets, and a max heap to efficiently retrieve the most recent tweets.

How does linked-list pointer manipulation improve performance?

Inserting new tweets at the head and merging feeds via pointers avoids costly array shifts, allowing O(1) insertion and efficient feed aggregation.

Can a user follow themselves in Design Twitter?

No, the system must prevent self-follow to avoid circular references in the news feed logic.

How do I retrieve the 10 most recent tweets efficiently?

Use a max heap to merge the head of each user's tweet list, always extracting the most recent tweet next until you collect up to 10 tweets.

What are common mistakes when implementing Design Twitter?

Common mistakes include not updating linked list pointers correctly, exceeding the 10-tweet feed limit, and mishandling unfollow or self-follow edge cases.

terminal

Solution

Solution 1

#### Python3

class Twitter:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.user_tweets = defaultdict(list)
        self.user_following = defaultdict(set)
        self.tweets = defaultdict()
        self.time = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        self.time += 1
        self.user_tweets[userId].append(tweetId)
        self.tweets[tweetId] = self.time

    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.
        """
        following = self.user_following[userId]
        users = set(following)
        users.add(userId)
        tweets = [self.user_tweets[u][::-1][:10] for u in users]
        tweets = sum(tweets, [])
        return nlargest(10, tweets, key=lambda tweet: self.tweets[tweet])

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        self.user_following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        following = self.user_following[followerId]
        if followeeId in following:
            following.remove(followeeId)


# 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)

Continue Practicing

#432 all oone data structure #460 lfu cache #146 lru cache