Facebook Pixel

355. Design Twitter

MediumDesignHash TableLinked ListHeap (Priority Queue)
Leetcode Link

Problem Description

This problem asks you to design a simplified Twitter-like social media system with basic functionality for posting tweets, following/unfollowing users, and viewing a news feed.

The system needs to support the following operations:

  1. Initialize the Twitter system - Create an empty Twitter object to store all user data and tweets.

  2. Post a tweet - A user can post a tweet with a unique tweet ID. The function postTweet(userId, tweetId) allows a user to create a new tweet. Each tweet ID is guaranteed to be unique across all calls.

  3. Get news feed - The function getNewsFeed(userId) should return the 10 most recent tweets that appear in a user's feed. The news feed includes:

    • Tweets posted by the user themselves
    • Tweets posted by users they follow
    • The tweets must be sorted from most recent to least recent
    • If there are fewer than 10 tweets available, return all of them

  4. Follow another user - The function follow(followerId, followeeId) allows one user to follow another user. After following, the follower should see the followee's tweets in their news feed.

  5. Unfollow a user - The function unfollow(followerId, followeeId) allows a user to unfollow someone they previously followed. After unfollowing, the followee's tweets should no longer appear in the follower's news feed.

The key challenge is maintaining the chronological order of tweets across all users and efficiently retrieving the most recent tweets for a user's news feed. The solution uses timestamps to track when each tweet was posted and combines tweets from followed users to generate the news feed.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

To build a Twitter-like system, we need to think about what data we need to track and how to organize it efficiently.

First, let's consider what information we need to store:

  • Who posted what: We need to know which tweets belong to which user
  • When tweets were posted: To show the most recent tweets, we need to track the order of posting
  • Who follows whom: We need to track the follow relationships between users

The natural approach is to use hash maps (dictionaries) for quick lookups:

  • user_tweets: Maps each user to their list of tweet IDs
  • user_following: Maps each user to the set of users they follow
  • tweets: Maps each tweet ID to its timestamp
  • time: A counter that increments with each tweet to maintain chronological order

For posting tweets, we simply add the tweet to the user's list and record its timestamp. Using an incrementing counter for time is simpler than using actual timestamps and guarantees unique ordering.

The most interesting part is generating the news feed. We need to:

  1. Identify all relevant users (the user themselves plus everyone they follow)
  2. Collect tweets from all these users
  3. Sort them by recency and return the top 10

The solution cleverly uses nlargest(10, tweets, key=lambda tweet: self.tweets[tweet]) to efficiently get the 10 most recent tweets without sorting the entire list. This is more efficient than sorting all tweets when we only need the top 10.

For follow/unfollow operations, we use a set to store followees for each user. Sets provide O(1) addition and removal, and automatically handle duplicates (preventing following the same user twice).

The key insight is that by separating the storage of tweets, timestamps, and follow relationships into different data structures, we can efficiently handle each operation without complex reorganization of data.

Solution Approach

The implementation uses several data structures to efficiently manage the Twitter system:

Data Structures

  1. user_tweets: A defaultdict(list) that maps each userId to a list of their tweetIds in chronological order
  2. user_following: A defaultdict(set) that maps each userId to a set of userIds they follow
  3. tweets: A defaultdict() that maps each tweetId to its timestamp
  4. time: An integer counter that increments with each tweet to maintain global chronological ordering

Implementation Details

__init__(): Initializes all data structures as empty collections with time starting at 0.

postTweet(userId, tweetId):

  1. Increment the global time counter
  2. Append the tweetId to the user's tweet list in user_tweets[userId]
  3. Store the timestamp in tweets[tweetId] = self.time

getNewsFeed(userId):

  1. Get the set of users the current user follows: following = self.user_following[userId]
  2. Create a set of all relevant users (followed users plus the user themselves): users.add(userId)
  3. For each relevant user, get their most recent 10 tweets:
    • self.user_tweets[u][::-1][:10] reverses the list and takes the first 10 (most recent)
  4. Combine all collected tweets into a single list using sum(tweets, [])
  5. Use nlargest(10, tweets, key=lambda tweet: self.tweets[tweet]) to get the 10 tweets with the highest timestamps

The nlargest function from the heapq module efficiently finds the k largest elements without fully sorting the list, which has O(n log k) complexity where n is the total number of tweets and k=10.

follow(followerId, followeeId):

  • Simply add followeeId to the follower's following set: self.user_following[followerId].add(followeeId)
  • Using a set automatically handles duplicate follows

unfollow(followerId, followeeId):

  1. Get the follower's following set
  2. Check if the followeeId exists in the set
  3. If it exists, remove it using following.remove(followeeId)

The solution leverages Python's defaultdict to avoid explicit initialization checks and uses sets for O(1) follow/unfollow operations. The global timestamp counter ensures tweets across all users can be properly ordered chronologically.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate how the Twitter system works:

Step 1: Initialize and create first tweets

twitter = Twitter()
twitter.postTweet(1, 101)  # User 1 posts tweet 101 (time=1)
twitter.postTweet(2, 201)  # User 2 posts tweet 201 (time=2)

After these operations:

  • user_tweets = {1: [101], 2: [201]}
  • tweets = {101: 1, 201: 2}
  • time = 2

Step 2: User 1 follows User 2

twitter.follow(1, 2)  # User 1 follows User 2

After this operation:

  • user_following = {1: {2}}

Step 3: User 2 posts another tweet

twitter.postTweet(2, 202)  # User 2 posts tweet 202 (time=3)

After this operation:

  • user_tweets = {1: [101], 2: [201, 202]}
  • tweets = {101: 1, 201: 2, 202: 3}
  • time = 3

Step 4: Get User 1's news feed

feed = twitter.getNewsFeed(1)  # Returns [202, 201, 101]

Here's how the news feed is generated:

  1. Identify relevant users: User 1 and User 2 (whom User 1 follows)
  2. Collect recent tweets:
    • From User 1: [101] (reversed from stored order)
    • From User 2: [202, 201] (reversed, so most recent first)
  3. Combined tweets: [101, 202, 201]
  4. Sort by timestamp using nlargest:
    • Tweet 202 (time=3) → highest
    • Tweet 201 (time=2) → second
    • Tweet 101 (time=1) → third
  5. Return: [202, 201, 101]

Step 5: User 1 unfollows User 2

twitter.unfollow(1, 2)  # User 1 unfollows User 2

After this operation:

  • user_following = {1: {}}

Step 6: Get User 1's news feed again

feed = twitter.getNewsFeed(1)  # Returns [101]

Now the feed only contains User 1's own tweets since they no longer follow User 2:

  1. Relevant users: Only User 1
  2. Collect tweets: [101]
  3. Return: [101]

This example demonstrates how the system tracks tweets with timestamps, maintains follow relationships, and generates personalized news feeds by combining and sorting tweets from relevant users.

Solution Implementation

1from collections import defaultdict
2from heapq import nlargest
3from typing import List
4
5class Twitter:
6    def __init__(self):
7        """
8        Initialize your data structure here.
9        """
10        # Dictionary mapping user_id to list of tweet_ids posted by that user
11        self.user_tweets = defaultdict(list)
12      
13        # Dictionary mapping user_id to set of user_ids they follow
14        self.user_following = defaultdict(set)
15      
16        # Dictionary mapping tweet_id to its timestamp
17        self.tweets = defaultdict()
18      
19        # Global timestamp counter, incremented with each new tweet
20        self.time = 0
21
22    def postTweet(self, userId: int, tweetId: int) -> None:
23        """
24        Compose a new tweet.
25        """
26        # Increment global timestamp
27        self.time += 1
28      
29        # Add tweet to user's tweet list
30        self.user_tweets[userId].append(tweetId)
31      
32        # Store tweet's timestamp for sorting purposes
33        self.tweets[tweetId] = self.time
34
35    def getNewsFeed(self, userId: int) -> List[int]:
36        """
37        Retrieve the 10 most recent tweet ids in the user's news feed. 
38        Each item in the news feed must be posted by users who the user followed 
39        or by the user herself. Tweets must be ordered from most recent to least recent.
40        """
41        # Get the set of users this user follows
42        following = self.user_following[userId]
43      
44        # Create set of all users whose tweets should appear in feed (followers + self)
45        users = set(following)
46        users.add(userId)
47      
48        # Collect the 10 most recent tweets from each user
49        # Reverse each user's tweet list to get most recent first, then take up to 10
50        tweets = [self.user_tweets[user][::-1][:10] for user in users]
51      
52        # Flatten the list of lists into a single list
53        tweets = sum(tweets, [])
54      
55        # Return the 10 most recent tweets based on timestamp
56        return nlargest(10, tweets, key=lambda tweet_id: self.tweets[tweet_id])
57
58    def follow(self, followerId: int, followeeId: int) -> None:
59        """
60        Follower follows a followee. If the operation is invalid, it should be a no-op.
61        """
62        # Add followee to follower's following set
63        self.user_following[followerId].add(followeeId)
64
65    def unfollow(self, followerId: int, followeeId: int) -> None:
66        """
67        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
68        """
69        # Get the follower's following set
70        following = self.user_following[followerId]
71      
72        # Remove followee if they exist in the following set
73        if followeeId in following:
74            following.remove(followeeId)
75
76
77# Your Twitter object will be instantiated and called as such:
78# obj = Twitter()
79# obj.postTweet(userId, tweetId)
80# param_2 = obj.getNewsFeed(userId)
81# obj.follow(followerId, followeeId)
82# obj.unfollow(followerId, followeeId)
83
1class Twitter {
2    // Map to store each user's tweet IDs in chronological order
3    private Map<Integer, List<Integer>> userTweetsMap;
4    // Map to store each user's following relationships (who they follow)
5    private Map<Integer, Set<Integer>> userFollowingMap;
6    // Map to store tweet ID to timestamp mapping for sorting
7    private Map<Integer, Integer> tweetTimestampMap;
8    // Global timestamp counter for ordering tweets
9    private int timestamp;
10
11    /**
12     * Initialize the Twitter data structure
13     */
14    public Twitter() {
15        userTweetsMap = new HashMap<>();
16        userFollowingMap = new HashMap<>();
17        tweetTimestampMap = new HashMap<>();
18        timestamp = 0;
19    }
20
21    /**
22     * Compose a new tweet
23     * @param userId The user who posts the tweet
24     * @param tweetId The unique identifier of the tweet
25     */
26    public void postTweet(int userId, int tweetId) {
27        // Add tweet to user's tweet list, creating new list if user doesn't exist
28        userTweetsMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(tweetId);
29        // Record tweet timestamp for later sorting
30        tweetTimestampMap.put(tweetId, ++timestamp);
31    }
32
33    /**
34     * Retrieve the 10 most recent tweet ids in the user's news feed
35     * Each item in the news feed must be posted by users who the user followed or by the user herself
36     * Tweets must be ordered from most recent to least recent
37     * @param userId The user requesting the news feed
38     * @return List of up to 10 most recent tweet IDs
39     */
40    public List<Integer> getNewsFeed(int userId) {
41        // Get the set of users this user follows
42        Set<Integer> followingSet = userFollowingMap.getOrDefault(userId, new HashSet<>());
43      
44        // Create a set including both followed users and the user themselves
45        Set<Integer> allRelevantUsers = new HashSet<>(followingSet);
46        allRelevantUsers.add(userId);
47      
48        // Priority queue to maintain tweets sorted by timestamp (most recent first)
49        PriorityQueue<Integer> tweetQueue = new PriorityQueue<>(
50            (tweet1, tweet2) -> tweetTimestampMap.get(tweet2) - tweetTimestampMap.get(tweet1)
51        );
52      
53        // Collect recent tweets from all relevant users
54        for (Integer currentUserId : allRelevantUsers) {
55            List<Integer> currentUserTweets = userTweetsMap.get(currentUserId);
56          
57            if (currentUserTweets != null && !currentUserTweets.isEmpty()) {
58                // Add up to 10 most recent tweets from each user
59                int tweetsToAdd = Math.min(10, currentUserTweets.size());
60                for (int i = currentUserTweets.size() - 1; 
61                     i >= currentUserTweets.size() - tweetsToAdd; 
62                     i--) {
63                    tweetQueue.offer(currentUserTweets.get(i));
64                }
65            }
66        }
67      
68        // Extract top 10 tweets from the priority queue
69        List<Integer> newsFeed = new ArrayList<>();
70        while (!tweetQueue.isEmpty() && newsFeed.size() < 10) {
71            newsFeed.add(tweetQueue.poll());
72        }
73      
74        return newsFeed;
75    }
76
77    /**
78     * Follower follows a followee
79     * If the operation is invalid, it should be a no-op
80     * @param followerId The user who wants to follow
81     * @param followeeId The user to be followed
82     */
83    public void follow(int followerId, int followeeId) {
84        // Add followee to follower's following set, creating new set if follower doesn't exist
85        userFollowingMap.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
86    }
87
88    /**
89     * Follower unfollows a followee
90     * If the operation is invalid, it should be a no-op
91     * @param followerId The user who wants to unfollow
92     * @param followeeId The user to be unfollowed
93     */
94    public void unfollow(int followerId, int followeeId) {
95        // Remove followee from follower's following set, creating empty set if needed
96        userFollowingMap.computeIfAbsent(followerId, k -> new HashSet<>()).remove(followeeId);
97    }
98}
99
100/**
101 * Your Twitter object will be instantiated and called as such:
102 * Twitter obj = new Twitter();
103 * obj.postTweet(userId,tweetId);
104 * List<Integer> param_2 = obj.getNewsFeed(userId);
105 * obj.follow(followerId,followeeId);
106 * obj.unfollow(followerId,followeeId);
107 */
108
1class Twitter {
2private:
3    // Map to store each user's tweet IDs in chronological order
4    unordered_map<int, vector<int>> userTweetsMap;
5    // Map to store each user's following relationships (who they follow)
6    unordered_map<int, unordered_set<int>> userFollowingMap;
7    // Map to store tweet ID to timestamp mapping for sorting
8    unordered_map<int, int> tweetTimestampMap;
9    // Global timestamp counter for ordering tweets
10    int timestamp;
11
12public:
13    /**
14     * Initialize the Twitter data structure
15     */
16    Twitter() {
17        timestamp = 0;
18    }
19  
20    /**
21     * Compose a new tweet
22     * @param userId The user who posts the tweet
23     * @param tweetId The unique identifier of the tweet
24     */
25    void postTweet(int userId, int tweetId) {
26        // Add tweet to user's tweet list, creating new list if user doesn't exist
27        userTweetsMap[userId].push_back(tweetId);
28        // Record tweet timestamp for later sorting
29        tweetTimestampMap[tweetId] = ++timestamp;
30    }
31  
32    /**
33     * Retrieve the 10 most recent tweet ids in the user's news feed
34     * Each item in the news feed must be posted by users who the user followed or by the user herself
35     * Tweets must be ordered from most recent to least recent
36     * @param userId The user requesting the news feed
37     * @return List of up to 10 most recent tweet IDs
38     */
39    vector<int> getNewsFeed(int userId) {
40        // Get the set of users this user follows
41        unordered_set<int> followingSet;
42        if (userFollowingMap.find(userId) != userFollowingMap.end()) {
43            followingSet = userFollowingMap[userId];
44        }
45      
46        // Create a set including both followed users and the user themselves
47        unordered_set<int> allRelevantUsers = followingSet;
48        allRelevantUsers.insert(userId);
49      
50        // Priority queue to maintain tweets sorted by timestamp (most recent first)
51        // Using pair<timestamp, tweetId> for sorting
52        priority_queue<pair<int, int>> tweetQueue;
53      
54        // Collect recent tweets from all relevant users
55        for (int currentUserId : allRelevantUsers) {
56            if (userTweetsMap.find(currentUserId) != userTweetsMap.end()) {
57                vector<int>& currentUserTweets = userTweetsMap[currentUserId];
58              
59                if (!currentUserTweets.empty()) {
60                    // Add up to 10 most recent tweets from each user
61                    int tweetsToAdd = min(10, static_cast<int>(currentUserTweets.size()));
62                    for (int i = currentUserTweets.size() - 1; 
63                         i >= static_cast<int>(currentUserTweets.size()) - tweetsToAdd; 
64                         i--) {
65                        int tweetId = currentUserTweets[i];
66                        tweetQueue.push({tweetTimestampMap[tweetId], tweetId});
67                    }
68                }
69            }
70        }
71      
72        // Extract top 10 tweets from the priority queue
73        vector<int> newsFeed;
74        while (!tweetQueue.empty() && newsFeed.size() < 10) {
75            newsFeed.push_back(tweetQueue.top().second);
76            tweetQueue.pop();
77        }
78      
79        return newsFeed;
80    }
81  
82    /**
83     * Follower follows a followee
84     * If the operation is invalid, it should be a no-op
85     * @param followerId The user who wants to follow
86     * @param followeeId The user to be followed
87     */
88    void follow(int followerId, int followeeId) {
89        // Add followee to follower's following set, creating new set if follower doesn't exist
90        userFollowingMap[followerId].insert(followeeId);
91    }
92  
93    /**
94     * Follower unfollows a followee
95     * If the operation is invalid, it should be a no-op
96     * @param followerId The user who wants to unfollow
97     * @param followeeId The user to be unfollowed
98     */
99    void unfollow(int followerId, int followeeId) {
100        // Remove followee from follower's following set if it exists
101        if (userFollowingMap.find(followerId) != userFollowingMap.end()) {
102            userFollowingMap[followerId].erase(followeeId);
103        }
104    }
105};
106
107/**
108 * Your Twitter object will be instantiated and called as such:
109 * Twitter* obj = new Twitter();
110 * obj->postTweet(userId,tweetId);
111 * vector<int> param_2 = obj->getNewsFeed(userId);
112 * obj->follow(followerId,followeeId);
113 * obj->unfollow(followerId,followeeId);
114 */
115
1// Map to store each user's tweet IDs in chronological order
2const userTweetsMap: Map<number, number[]> = new Map();
3// Map to store each user's following relationships (who they follow)
4const userFollowingMap: Map<number, Set<number>> = new Map();
5// Map to store tweet ID to timestamp mapping for sorting
6const tweetTimestampMap: Map<number, number> = new Map();
7// Global timestamp counter for ordering tweets
8let timestamp: number = 0;
9
10/**
11 * Compose a new tweet
12 * @param userId - The user who posts the tweet
13 * @param tweetId - The unique identifier of the tweet
14 */
15function postTweet(userId: number, tweetId: number): void {
16    // Add tweet to user's tweet list, creating new list if user doesn't exist
17    if (!userTweetsMap.has(userId)) {
18        userTweetsMap.set(userId, []);
19    }
20    userTweetsMap.get(userId)!.push(tweetId);
21  
22    // Record tweet timestamp for later sorting
23    timestamp++;
24    tweetTimestampMap.set(tweetId, timestamp);
25}
26
27/**
28 * Retrieve the 10 most recent tweet ids in the user's news feed
29 * Each item in the news feed must be posted by users who the user followed or by the user themselves
30 * Tweets must be ordered from most recent to least recent
31 * @param userId - The user requesting the news feed
32 * @returns List of up to 10 most recent tweet IDs
33 */
34function getNewsFeed(userId: number): number[] {
35    // Get the set of users this user follows
36    const followingSet = userFollowingMap.get(userId) || new Set<number>();
37  
38    // Create a set including both followed users and the user themselves
39    const allRelevantUsers = new Set<number>(followingSet);
40    allRelevantUsers.add(userId);
41  
42    // Collect all tweets from relevant users with their timestamps
43    const tweetsWithTimestamps: Array<[number, number]> = [];
44  
45    // Gather recent tweets from all relevant users
46    for (const currentUserId of allRelevantUsers) {
47        const currentUserTweets = userTweetsMap.get(currentUserId);
48      
49        if (currentUserTweets && currentUserTweets.length > 0) {
50            // Add up to 10 most recent tweets from each user
51            const tweetsToAdd = Math.min(10, currentUserTweets.length);
52            for (let i = currentUserTweets.length - tweetsToAdd; i < currentUserTweets.length; i++) {
53                const tweetId = currentUserTweets[i];
54                const tweetTimestamp = tweetTimestampMap.get(tweetId)!;
55                tweetsWithTimestamps.push([tweetId, tweetTimestamp]);
56            }
57        }
58    }
59  
60    // Sort tweets by timestamp in descending order (most recent first)
61    tweetsWithTimestamps.sort((a, b) => b[1] - a[1]);
62  
63    // Extract top 10 tweet IDs
64    const newsFeed: number[] = [];
65    for (let i = 0; i < Math.min(10, tweetsWithTimestamps.length); i++) {
66        newsFeed.push(tweetsWithTimestamps[i][0]);
67    }
68  
69    return newsFeed;
70}
71
72/**
73 * Follower follows a followee
74 * If the operation is invalid, it should be a no-op
75 * @param followerId - The user who wants to follow
76 * @param followeeId - The user to be followed
77 */
78function follow(followerId: number, followeeId: number): void {
79    // Add followee to follower's following set, creating new set if follower doesn't exist
80    if (!userFollowingMap.has(followerId)) {
81        userFollowingMap.set(followerId, new Set<number>());
82    }
83    userFollowingMap.get(followerId)!.add(followeeId);
84}
85
86/**
87 * Follower unfollows a followee
88 * If the operation is invalid, it should be a no-op
89 * @param followerId - The user who wants to unfollow
90 * @param followeeId - The user to be unfollowed
91 */
92function unfollow(followerId: number, followeeId: number): void {
93    // Remove followee from follower's following set if it exists
94    const followingSet = userFollowingMap.get(followerId);
95    if (followingSet) {
96        followingSet.delete(followeeId);
97    }
98}
99

Time and Space Complexity

Time Complexity:

  • __init__(): O(1) - Simply initializes empty data structures.

  • postTweet(): O(1) - Increments time counter, appends to a list, and adds to a dictionary, all constant time operations.

  • getNewsFeed(): O(U * T + N log N) where:

    • U is the number of users (the user + their followees)
    • T is the number of tweets per user (capped at 10 due to slicing [:10])
    • N is the total number of collected tweets (at most U * 10)
    • Getting the following set and creating users set: O(U)
    • Retrieving last 10 tweets for each user: O(U * T) where T ≤ 10
    • Reversing and slicing each user's tweets: O(T) per user
    • Flattening the tweets list: O(U * T)
    • Finding the 10 largest tweets using nlargest: O(N log 10) = O(N) where N ≤ U * 10
    • Overall: O(U * T) which simplifies to O(U) since T is bounded by 10

  • follow(): O(1) - Adding to a set is constant time on average.

  • unfollow(): O(1) - Checking membership and removing from a set are both constant time operations on average.

Space Complexity:

  • Overall space: O(N + M) where:

    • N is the total number of tweets posted across all users
    • M is the total number of follow relationships

  • user_tweets: O(N) - Stores all tweet IDs for all users

  • user_following: O(M) - Stores all follow relationships

  • tweets: O(N) - Stores timestamp for each tweet

  • getNewsFeed() auxiliary space: O(U) for the temporary lists created during execution

Common Pitfalls

1. Self-Following Edge Case

One major pitfall is not handling the case where a user might follow themselves. The current implementation allows follow(userId, userId), which could lead to duplicate tweets in the news feed since we explicitly add the user to their own feed set.

Problem Example:

twitter.postTweet(1, 100)
twitter.follow(1, 1)  # User 1 follows themselves
twitter.getNewsFeed(1)  # Could return duplicates or cause issues

Solution: Add a check to prevent self-following:

def follow(self, followerId: int, followeeId: int) -> None:
    if followerId != followeeId:  # Prevent self-following
        self.user_following[followerId].add(followeeId)

2. Memory Inefficiency with Large Tweet History

The current implementation stores all tweets forever in user_tweets, even though we only need the 10 most recent tweets for the news feed. For users with millions of tweets, this becomes a memory issue.

Solution: Limit the stored tweets per user:

def postTweet(self, userId: int, tweetId: int) -> None:
    self.time += 1
    self.user_tweets[userId].append(tweetId)
    # Keep only the most recent 10 tweets per user
    if len(self.user_tweets[userId]) > 10:
        old_tweet = self.user_tweets[userId].pop(0)
        del self.tweets[old_tweet]  # Clean up timestamp mapping
    self.tweets[tweetId] = self.time

3. Integer Overflow for Timestamp

The global time counter increments indefinitely. In systems with high tweet volume, this could eventually cause integer overflow issues.

Solution: Use a more robust timestamp approach or periodically reset with proper handling:

def __init__(self):
    self.time = 0
    self.MAX_TIME = 10**9  # Set a reasonable maximum
  
def postTweet(self, userId: int, tweetId: int) -> None:
    self.time = (self.time + 1) % self.MAX_TIME  # Circular counter
    # Or use actual timestamps: self.time = time.time()

4. Inefficient News Feed Generation

The current approach collects tweets from all followed users before filtering, which is inefficient when following many users with lots of tweets.

Solution: Use a heap-based merge approach for better efficiency:

import heapq

def getNewsFeed(self, userId: int) -> List[int]:
    heap = []
    users = self.user_following[userId] | {userId}
  
    for user in users:
        tweets = self.user_tweets[user]
        if tweets:
            # Add most recent tweet from each user to heap
            # Use negative timestamp for max heap behavior
            latest_idx = len(tweets) - 1
            heapq.heappush(heap, 
                (-self.tweets[tweets[latest_idx]], latest_idx, user, tweets))
  
    result = []
    while heap and len(result) < 10:
        _, idx, user, tweets = heapq.heappop(heap)
        result.append(tweets[idx])
      
        # Add next tweet from same user if exists
        if idx > 0:
            heapq.heappush(heap, 
                (-self.tweets[tweets[idx-1]], idx-1, user, tweets))
  
    return result

This approach only processes as many tweets as needed rather than collecting all tweets first.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Heap Fundamentals

https assets algo monster cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue is a data structure

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More