355. Design Twitter

MediumDesignHash TableLinked ListHeap (Priority Queue)
Leetcode Link

Problem Description

This problem simulates a basic form of Twitter functionality. It involves designing a system that allows users to post tweets, follow other users, unfollow users, and view the 10 most recent tweets in their news feed. Each tweet has a unique ID, and the news feed must display these tweets in order from most to least recent. The following functionalities are to be implemented:

  • Twitter(): a constructor to initialize the Twitter object.
  • postTweet(userId, tweetId): allows a user to post a tweet.
  • getNewsFeed(userId): retrieves the 10 most recent tweets from the user and the users they follow.
  • follow(followerId, followeeId): allows a user to follow another user.
  • unfollow(followerId, followeeId): allows a user to unfollow another user.

Intuition

The solution to this problem requires efficient ways to store and retrieve tweets and follow relationships. Here's the intuition behind each part of the solution:

  • Initialisation: Use dictionaries (defaultdict) to track tweets and follow relationships for each user. The user_tweets dictionary keeps a list of a user's tweets, user_following keeps track of who each user is following, and tweets maintains the timestamp order of each tweet.

  • Posting Tweets: Increment a global time variable each time a tweet is posted to keep track of the order. Save each tweet with the current time into user_tweets to build a user's twitter history and tweets dictionary to preserve the global order.

  • Getting News Feed: Retrieve the 10 most recent tweets from the user and users they follow. This requires merging and sorting tweets from multiple users. The naive approach could be costly due to sorting each time the news feed is requested, so the solution uses a heap (nlargest function) to efficiently get the top 10 tweets.

  • Following: Modify the user_following dictionary to add the followeeId to the followerId's set.

  • Unfollowing: Check if the followerId is following followeeId and remove it from the follow set if present.

By combining these data structures and methods, the system manages user activity in an efficient and streamlined manner, optimizing for the frequent action of getting the news feed which requires sorting and collation of tweets.

Learn more about Linked List and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The solution utilizes a combination of data structures such as dictionaries, sets, and heaps to implement the required functionality efficiently. Here’s how each functionality is implemented:

  • Data Structures Used:

    • defaultdict(list) for user_tweets: This stores tweets for each user. The key is the userId and the value is a list of tweetIds.
    • defaultdict(set) for user_following: This maintains the following relationships. The key is the followerId and the value is a set of followeeIds to facilitate quick add (follow) and delete (unfollow) operations.
    • defaultdict() for tweets: This keeps track of when each tweet was posted. It maps tweetId to a timestamp based on the time variable.

  • Posting Tweets (postTweet method):

    • Increment the time each time a new tweet is posted to create a unique timestamp.
    • Append tweetId to the user_tweets list for the given userId.
    • Associate tweetId with the current time in the tweets dictionary to keep track of when the tweet was posted.

  • Getting News Feed (getNewsFeed method):

    • First, gather all user IDs that the news feed should include – the user itself and all user IDs they follow, which are obtained from user_following.
    • Create a combined list of tweets by retrieving the lists of recent tweets from user_tweets for all these users and flattening them into a single list. Only the most recent 10 tweets per user are considered.
    • Use the nlargest function from the heapq module to efficiently retrieve the 10 most recent tweets from the combined list, utilizing timestamps stored in the tweets dictionary as the key for sorting.
    • The nlargest function takes advantage of the fact that tweets are stored with a monotonically increasing timestamp, thereby efficiently implementing a max heap to find the top tweets without needing to sort the entire list.

  • Following a user (follow method):

    • Add the followeeId to the followerId's set in user_following.

  • Unfollowing a user (unfollow method):

    • Check if the followeeId is in the followerId's set in user_following and remove it if present.

This approach takes advantage of the properties of sets for quick modifications in follow/unfollow operations and leverages the ordering of a timestamp to avoid full sorts when retrieving the news feed.

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

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's walk through a simple example to illustrate how the solution approach works:

  1. Initialization: Assume we initialize our Twitter system.

    1twitter = Twitter()

    Now, our user_tweets, user_following, and tweets are all initialized, but they are empty.

  2. Post Tweets:

    • User 1 posts a tweet:

      1twitter.postTweet(1, 5)

      The tweet with id 5 from user 1 is stored, and the timestamp is increased. user_tweets now has {1: [5]}, and tweets has {5: timestamp}.

    • User 2 posts two tweets:

      1twitter.postTweet(2, 6)
2twitter.postTweet(2, 7)

      User 2’s tweets are stored with increasing timestamps. Now user_tweets has {1: [5], 2: [6, 7]}, and tweets includes {5: timestamp1, 6: timestamp2, 7: timestamp3}.

  3. Follow:

    • User 1 decides to follow user 2: 
      1twitter.follow(1, 2)
      user_following updates to {1: {2}} indicating that user 1 is now following user 2.

  4. Get News Feed:

    • User 1 wants to view their news feed: 
      1twitter.getNewsFeed(1)
      Since user 1 follows user 2, the feed should include tweets from both users. The system gathers all tweet IDs from user 1 and user 2, which are [5, 6, 7]. The nlargest function is used with the tweets' timestamps to get the top tweets, resulting in a list of tweets [7, 6, 5] showing the most recent tweets first.

  5. Unfollow:

    • User 1 decides to unfollow user 2: 
      1twitter.unfollow(1, 2)
      Now user_following is updated to {1: {}}, which means user 1 is not following anyone anymore.

By following these simple steps, the system is capable of supporting different operations efficiently, catering to the functionalities similar to that of Twitter. The use of appropriate data structures such as defaultdict(list), defaultdict(set), and heaps allows for optimal performance for each operation, whether it be posting, following/unfollowing, or retrieving the news feed.

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 structures here.
9        """
10        self.user_tweets = defaultdict(list)  # Maps user ids to their tweets (respecting the chronological order)
11        self.user_following = defaultdict(set) # Maps user ids to the set of user ids they follow
12        self.tweets = {}  # Maps tweet ids to timestamps
13        self.timer = 0  # A timestamp to order tweets
14
15    def post_tweet(self, user_id: int, tweet_id: int) -> None:
16        """
17        Compose and post a new tweet.
18        """
19        self.timer += 1  # Increment the timer to record the time of the tweet
20        self.user_tweets[user_id].append(tweet_id)  # Append the new tweet to the user's tweets
21        self.tweets[tweet_id] = self.timer  # Record the timestamp for the new tweet
22
23    def get_news_feed(self, user_id: int) -> List[int]:
24        """
25        Retrieve the 10 most recent tweet ids in the user's news feed.
26        Each item in the news feed must be posted by users whom the user follows or by the user themselves.
27        Tweets must be ordered from most recent to least recent.
28        """
29        following = self.user_following[user_id]  # Get the set of user ids the current user follows
30        users = following.union({user_id})  # Combine with the current user to get all potential sources of tweets
31        # Collect up to the 10 most recent tweets from each user
32        tweets = [self.user_tweets[u][-10:][::-1] for u in users]  # Retrieve, reverse, and limit to 10 tweets
33        all_tweets = sum(tweets, [])  # Flatten the list of tweets
34        # Get the 10 most recent tweets among all the tweets collected, based on timestamps
35        return nlargest(10, all_tweets, key=lambda tweet: self.tweets[tweet])
36
37    def follow(self, follower_id: int, followee_id: int) -> None:
38        """
39        Follower follows a followee. If the operation is invalid, it should be a no-op.
40        """
41        self.user_following[follower_id].add(followee_id)  # Add the followee to the follower's following set
42
43    def unfollow(self, follower_id: int, followee_id: int) -> None:
44        """
45        Follower unfollows a followee. If the operation is invalid (e.g., not following), it should be a no-op.
46        """
47        if followee_id in self.user_following[follower_id]:  # If the follower is actually following the followee
48            self.user_following[follower_id].remove(followee_id)  # Remove the followee from the set
49
50
51# The Twitter object can be instantiated and used as follows:
52# obj = Twitter()
53# obj.post_tweet(user_id, tweet_id)
54# feed = obj.get_news_feed(user_id)
55# obj.follow(follower_id, followee_id)
56# obj.unfollow(follower_id, followee_id)
57
1import java.util.*;
2
3public class Twitter {
4    private Map<Integer, List<Integer>> userTweetListMap;
5    private Map<Integer, Set<Integer>> userFollowsMap;
6    private Map<Integer, Integer> tweetIdToTimestampMap;
7    private int timestamp;
8
9    /** Initialize your data structure for the Twitter class. */
10    public Twitter() {
11        userTweetListMap = new HashMap<>();
12        userFollowsMap = new HashMap<>();
13        tweetIdToTimestampMap = new HashMap<>();
14        timestamp = 0;
15    }
16
17    /**
18     * Compose a new tweet.
19     * @param userId The ID of the user posting the tweet.
20     * @param tweetId The ID of the tweet.
21     */
22    public void postTweet(int userId, int tweetId) {
23        // Add tweet to the user's list of tweets
24        userTweetListMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(tweetId);
25        // Map the tweetId to the current timestamp
26        tweetIdToTimestampMap.put(tweetId, ++timestamp);
27    }
28
29    /**
30     * Retrieve the 10 most recent tweet IDs in the user's news feed. Each item
31     * in the news feed must be posted by users who the user followed or by the
32     * user themself. Tweets must be ordered from most recent to least recent.
33     * @param userId The ID of the user whose news feed is retrieved.
34     * @return A list of tweet IDs in the news feed.
35     */
36    public List<Integer> getNewsFeed(int userId) {
37        // Get the set of all users the given user is following
38        Set<Integer> following = userFollowsMap.getOrDefault(userId, new HashSet<>());
39        // Include the user's own ID to include their tweets as well
40        following.add(userId);
41
42        // Priority Queue to store tweets by recency
43        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
44                (tweetId1, tweetId2) -> tweetIdToTimestampMap.get(tweetId2) - tweetIdToTimestampMap.get(tweetId1)
45        );
46
47        // Collect the tweets from each user's tweet list, but restrict to the 10 most recent tweets per user
48        for (Integer user : following) {
49            List<Integer> tweets = userTweetListMap.get(user);
50            if (tweets != null) {
51                int tweetCount = tweets.size();
52                for (int i = tweetCount - 1, tweetLimit = 10; i >= 0 && tweetLimit > 0; --i, --tweetLimit) {
53                    minHeap.offer(tweets.get(i));
54                }
55            }
56        }
57
58        // Retrieve the 10 most recent tweets for the news feed
59        List<Integer> feed = new ArrayList<>();
60        int feedSize = 10;
61        while (!minHeap.isEmpty() && feed.size() < feedSize) {
62            feed.add(minHeap.poll());
63        }
64
65        return feed;
66    }
67
68    /**
69     * Follower follows a followee. If the operation is invalid (i.e., already following), it should be a no-op.
70     * @param followerId The ID of the follower.
71     * @param followeeId The ID of the followee.
72     */
73    public void follow(int followerId, int followeeId) {
74        userFollowsMap.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
75    }
76
77    /**
78     * Follower unfollows a followee. If the operation is invalid (i.e., not following), it should be a no-op.
79     * @param followerId The ID of the follower.
80     * @param followeeId The ID of the followee.
81     */
82    public void unfollow(int followerId, int followeeId) {
83        if (userFollowsMap.containsKey(followerId)) {
84            userFollowsMap.get(followerId).remove(followeeId);
85        }
86    }
87}
88
89/**
90 * Your Twitter object will be instantiated and called as such:
91 * Twitter obj = new Twitter();
92 * obj.postTweet(userId, tweetId);
93 * List<Integer> param_2 = obj.getNewsFeed(userId);
94 * obj.follow(followerId, followeeId);
95 * obj.unfollow(followerId, followeeId);
96 */
97
1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
4#include <queue>
5#include <functional>
6#include <utility>
7using namespace std;
8
9class Twitter {
10private:
11    unordered_map<int, vector<int>> userTweetIdsMap; // Maps user ID to a list of tweet IDs
12    unordered_map<int, unordered_set<int>> userFollowsMap; // Maps user ID to a set of user IDs they follow
13    unordered_map<int, int> tweetIdToTimestampMap; // Maps tweet ID to the timestamp it was posted
14    int timestamp; // A global timestamp representing the order in which tweets are posted
15
16public:
17    /** Initialize your data structure for the Twitter class. */
18    Twitter() : timestamp(0) { }
19
20    /**
21     * Compose a new tweet.
22     * @param userId The ID of the user posting the tweet.
23     * @param tweetId The ID of the tweet.
24     */
25    void postTweet(int userId, int tweetId) {
26        // Increment the global timestamp and post the tweet
27        tweetIdToTimestampMap[tweetId] = ++timestamp;
28        // Add the tweet to the user's list of tweets
29        userTweetIdsMap[userId].push_back(tweetId);
30    }
31
32    /**
33     * Retrieve the 10 most recent tweet IDs in the user's news feed. Each item
34     * in the news feed must be posted by users who the user followed or by the user themselves.
35     * Tweets must be ordered from most recent to least recent.
36     *
37     * @param userId The ID of the user whose news feed is retrieved.
38     * @return A list of tweet IDs in the news feed.
39     */
40    vector<int> getNewsFeed(int userId) {
41        // Include the user themselves into the following list to see their own tweets in the news feed
42        unordered_set<int> following = userFollowsMap[userId];
43        following.insert(userId);
44
45        auto cmp = [&](const int a, const int b) {
46            return tweetIdToTimestampMap[a] < tweetIdToTimestampMap[b];
47        };
48      
49        // Use a min heap to keep the 10 most recent tweets
50        priority_queue<int, vector<int>, decltype(cmp)> minHeap(cmp);
51
52        for (int user : following) {
53            // Iterate over the tweets posted by the user
54            const vector<int>& tweets = userTweetIdsMap[user];
55            for (int tweetId : tweets) {
56                minHeap.push(tweetId);
57                // If we have more than 10 tweets, pop the least recent
58                if (minHeap.size() > 10) {
59                    minHeap.pop();
60                }
61            }
62        }
63
64        // Now we have up to 10 tweets in the min heap, sorted by recency
65        vector<int> feed;
66        while (!minHeap.empty()) {
67            feed.push_back(minHeap.top());
68            minHeap.pop();
69        }
70        // The most recent tweet is at the end, so we reverse the vector
71        reverse(feed.begin(), feed.end());
72        return feed;
73    }
74
75    /**
76     * Follower follows a followee. If the operation is invalid (i.e., already following), it should be a no-op.
77     * @param followerId The ID of the follower.
78     * @param followeeId The ID of the followee.
79     */
80    void follow(int followerId, int followeeId) {
81        // Add the followee to the follower's set of follows
82        userFollowsMap[followerId].insert(followeeId);
83    }
84
85    /**
86     * Follower unfollows a followee. If the operation is invalid (i.e., not following), it should be a no-op.
87     * @param followerId The ID of the follower.
88     * @param followeeId The ID of the followee.
89     */
90    void unfollow(int followerId, int followeeId) {
91        // Remove the followee from the follower's set of follows, if it exists
92        userFollowsMap[followerId].erase(followeeId);
93    }
94};
95
1// Declare the type for the maps to be used globally
2type UserTweetListMapType = Map<number, number[]>;
3type UserFollowsMapType = Map<number, Set<number>>;
4type TweetIdToTimestampMapType = Map<number, number>;
5
6// Declare the global variables equivalent to the class properties in Java
7let userTweetListMap: UserTweetListMapType = new Map();
8let userFollowsMap: UserFollowsMapType = new Map();
9let tweetIdToTimestampMap: TweetIdToTimestampMapType = new Map();
10let timestamp: number = 0;
11
12// Function to post a tweet associated with a user
13function postTweet(userId: number, tweetId: number): void {
14  // If the user is not found in the map, initialize their tweet list
15  const tweetList = userTweetListMap.get(userId) ?? [];
16
17  // Add the new tweet's ID to the user's tweet list
18  tweetList.push(tweetId);
19  userTweetListMap.set(userId, tweetList);
20
21  // Increment the timestamp and associate it with the tweet
22  tweetIdToTimestampMap.set(tweetId, ++timestamp);
23}
24
25// Function to get the 10 most recent tweets in the user's news feed
26function getNewsFeed(userId: number): number[] {
27  // Get the user's own tweets and the ones from the users they follow
28  const following = userFollowsMap.get(userId) ?? new Set();
29  following.add(userId);
30
31  // Use a min-heap to keep track of the tweets' timestamps
32  const minHeap: number[] = [];
33
34  // Helper function to sort the heap by timestamp
35  const byTimestamp = (a: number, b: number) => tweetIdToTimestampMap.get(b)! - tweetIdToTimestampMap.get(a)!;
36
37  following.forEach(user => {
38    const tweets = userTweetListMap.get(user) || [];
39    // Take at most the 10 most recent tweets from each user
40    tweets.slice(-10).forEach(tweetId => {
41      minHeap.push(tweetId);
42    });
43  });
44
45  // Sort the collected tweets by their timestamp using the min-heap
46  minHeap.sort(byTimestamp);
47
48  // Slice to get only the 10 most recent tweets
49  return minHeap.slice(0, 10);
50}
51
52// Function for a user to follow another user
53function follow(followerId: number, followeeId: number): void {
54  const followsSet = userFollowsMap.get(followerId) ?? new Set();
55  followsSet.add(followeeId);
56  userFollowsMap.set(followerId, followsSet);
57}
58
59// Function for a user to unfollow another user
60function unfollow(followerId: number, followeeId: number): void {
61  userFollowsMap.get(followerId)?.delete(followeeId);
62}
63
Not Sure What to Study? Take the 2-min Quiz：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Time and Space Complexity

Time Complexity

  • __init__: O(1) - Constant time for initialization since no calculations are being done.
  • postTweet: O(1) - Adding a tweet involves a constant number of operations, incrementing time, appending a tweet to a user's list and storing the timestamp, all of which are O(1).
  • getNewsFeed: O(users * tweets + KlogK) - Where users is the number of followed users, and tweets is the number of tweets in their feed and K is the total number of tweets fetched to sort. Specifically, O(users * 10) for collecting the tweets since we are obtaining at most 10 recent tweets from each user, and O(KlogK) for sorting these tweets, where K is min(users*10, 10) since we only return the 10 most recent tweets. In the worst case, this can be O(NlogN) for the sorting step if N is the number of tweets considered.
  • follow: O(1) - The act of following simply adds to a set which is an O(1) operation.
  • unfollow: O(1) - Unfollowing checks if a followeeId is in the set and removes it which are both O(1) operations.

Space Complexity

  • __init__: O(1) - Initialization of dictionaries and variables uses constant space.
  • postTweet: O(T) - Where T is the number of tweets. Each tweet increases the space needed to store the tweet and its timestamp.
  • getNewsFeed: O(users * tweets) - Additional space needed to collect up to 10 latest tweets from each user followed. Thus space required grows with the number of users being followed and their tweets, although this space is temporary just for the duration of the method call.
  • follow and unfollow: O(U + F) - Where U is the number of users and F is the total number of follow relations since each user may have a set of followers and followees. Each follow/unfollow action potentially adds/removes an element in a user's following set, so it doesn't increase the space complexity beyond what is needed to store all follow relationships.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

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 algomonster s3 us east 2 amazonaws com 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

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫