Design Twitter Problem ( C++, Java, Python )

In Today’s world of technology, social media plays an important role in everybody’s life. Twitter is one of them and its design, and how it works still fascinate many users, In this article, we will discuss this Design Twitter problem from leetcode, see how Twitter functions behind the scenes with the help of data structures and algorithms, along with its implementation.

What is the Design Twitter Problem?

In the Design Twitter problem, we have to design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in the user’s news feed, we have to implement all this in a “Twitter class”.

Below are the functions to be implemented in this problem:

Twitter() Initializes your Twitter object
void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user’s news feed. Each item in the news feed must be posted by users whom the user followed or by the users themself. Tweets must be ordered from most recent to least recent.
void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Let us understand it better with an example:

Input = [“Twitter”, “postTweet”, “getNewsFeed”, “follow”, “postTweet”, “getNewsFeed”, “unfollow”, “getNewsFeed”]
[[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]]

This array shows the parameters passed in the functions given above.

Output = [null, null, [5], null, null, [6, 5], null, [5]]

The first input initializes the Twitter object, and the second input posts a tweet with id = 5. The input at index 2 will get the recent tweet that was just posted with id = 5.

Design Twitter Problem Solution

In this, we will discuss how we will build essential functionality of Twitter using data structures and algorithms.

The following are the steps involved in this approach:

In Twitter class, we will declare sour data structures a set to store tweets ordered by timestamp in descending order. A map to store the relationship between users and those they follow.
We will also declare “countOfPost” an integer to store the unique timestamp of each post.
Firstly we will build post-tweet functionality in this we will create a pair of integers and a pair, in integers we will store the timestamp, and the inner pair holds the user ID and tweet ID.
- We will use the set that we have declared in starting which maintains the timestamp in descending order.
- Now we will increment “countOfPost” to maintain a unique timestamp for each tweet.
Now we will complete the “getNewsFeed” function, we will initialize a vector to store the newsfeed as a result
- Now we will retrieve the set of users that the current user (userId) follows and store it in st.
- Iterates through the sorted sets that we have used to store user id and tweet id to get the 10 most recent tweets.
- Now we will Check if the tweet is from a user that the current user follows or if it’s their tweet. If true, add the tweet ID to the result and return our result.
In the “follow” function, we just have to map follower-Id with followee-Id using a map data structure.
In the “unfollow” function we will remove followee-Id from the set users that follower-Id follows.

C++ Code

Below is the C++ program to solve the Design Twitter problem:

#include <bits/stdc++.h>

class Twitter {
public:
    std::set<std::pair<int, std::pair<int, int>>, std::greater<std::pair<int, std::pair<int, int>>>> s;
    std::map<int, std::unordered_set<int>> mp;
    int countOfPost;

    Twitter() {
        countOfPost = 0;
    }

    // Function to post a new tweet
    void postTweet(int userId, int tweetId) {
        // Create a pair with timestamp and a pair of userId and tweetId
        std::pair<int, std::pair<int, int>> p = {countOfPost, {userId, tweetId}};
        // Insert the tweet into the set, ordered by timestamp
        s.insert(p);
        // Increment the timestamp for the next tweet
        countOfPost++;
    }

    // Function to get the news feed for a user
    std::vector<int> getNewsFeed(int userId) {
        std::vector<int> res;
        // Retrieve the set of users that the current user follows
        std::unordered_set<int> st = mp[userId];

        // Iterator for the sorted set
        auto it = s.begin();

        // Iterate through the sorted set to get the 10 most recent tweets
        while (res.size() != 10 && it != s.end()) {
            std::pair<int, std::pair<int, int>> p = *it;
            // Check if the tweet is from a user that the current user follows or if it's their own tweet
            if (st.count(p.second.first) == 1 || p.second.first == userId)
                res.push_back(p.second.second);
            it++;
        }

        return res;
    }

    // Function to make a user follow another user
    void follow(int followerId, int followeeId) {
        mp[followerId].insert(followeeId);
    }

    // Function to make a user unfollow another user
    void unfollow(int followerId, int followeeId) {
        mp[followerId].erase(followeeId);
    }
};

// Example Usage
int main() {
    Twitter twitter;

    twitter.postTweet(1, 101);
    twitter.postTweet(1, 102);
    twitter.postTweet(2, 103);
    twitter.postTweet(2, 104);
    twitter.follow(1, 2);

    std::vector<int> newsFeed = twitter.getNewsFeed(1);
    std::cout << "News Feed for User 1: ";
    for (int tweetId : newsFeed) {
        std::cout << tweetId << " ";
    }
    std::cout << std::endl;

    twitter.unfollow(1, 2);

    newsFeed = twitter.getNewsFeed(1);
    std::cout << "News Feed for User 1 after Unfollow: ";
    for (int tweetId : newsFeed) {
        std::cout << tweetId << " ";
    }

    return 0;
}

Python Code

You can implement it in Python as well with PriorityQueue:

from queue import PriorityQueue
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.s = PriorityQueue()
        self.mp = defaultdict(set)
        self.countOfPost = 0

    def postTweet(self, userId, tweetId):
        p = (self.countOfPost, (userId, tweetId))
        self.s.put(p)
        self.countOfPost += 1

    def getNewsFeed(self, userId):
        res = []
        st = self.mp[userId]

        while not self.s.empty() and len(res) < 10:
            p = self.s.get()
            if st.__contains__(p[1][0]) or p[1][0] == userId:
                res.append(p[1][1])

        return res

    def follow(self, followerId, followeeId):
        self.mp[followerId].add(followeeId)

    def unfollow(self, followerId, followeeId):
        self.mp[followerId].discard(followeeId)

# Example Usage
if __name__ == "__main__":
    twitter = Twitter()

    twitter.postTweet(1, 101)
    twitter.postTweet(1, 102)
    twitter.postTweet(2, 103)
    twitter.postTweet(2, 104)
    twitter.follow(1, 2)

    newsFeed = twitter.getNewsFeed(1)
    print("News Feed for User 1:", newsFeed)

    twitter.unfollow(1, 2)

    newsFeed = twitter.getNewsFeed(1)
    print("News Feed for User 1 after Unfollow:", newsFeed)

Java Code

Here is the implementation in Java:

import java.util.*;

class Twitter {
    PriorityQueue<Pair<Integer, Pair<Integer, Integer>>> s;
    Map<Integer, Set<Integer>> mp;
    int countOfPost;

    public Twitter() {
        s = new PriorityQueue<>((p1, p2) -> Integer.compare(p2.getKey(), p1.getKey()));
        mp = new HashMap<>();
        countOfPost = 0;
    }

    public void postTweet(int userId, int tweetId) {
        Pair<Integer, Pair<Integer, Integer>> p = new Pair<>(countOfPost, new Pair<>(userId, tweetId));
        s.add(p);
        countOfPost++;
    }

    public List<Integer> getNewsFeed(int userId) {
        List<Integer> res = new ArrayList<>();
        Set<Integer> st = mp.getOrDefault(userId, new HashSet<>());

        PriorityQueue<Pair<Integer, Pair<Integer, Integer>>> temp = new PriorityQueue<>(s);

        while (!temp.isEmpty() && res.size() < 10) {
            Pair<Integer, Pair<Integer, Integer>> p = temp.poll();
            if (st.contains(p.getValue().getKey()) || p.getValue().getKey() == userId) {
                res.add(p.getValue().getValue());
            }
        }

        return res;
    }

    public void follow(int followerId, int followeeId) {
        mp.computeIfAbsent(followerId, k -> new HashSet<>()).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        mp.getOrDefault(followerId, Collections.emptySet()).remove(followeeId);
    }

    public static void main(String[] args) {
        Twitter twitter = new Twitter();
        twitter.postTweet(1, 101);
        twitter.postTweet(1, 102);
        twitter.postTweet(2, 103);
        twitter.postTweet(2, 104);
        twitter.follow(1, 2);

        List<Integer> newsFeed = twitter.getNewsFeed(1);
        System.out.println("News Feed for User 1: " + newsFeed);

        twitter.unfollow(1, 2);

        newsFeed = twitter.getNewsFeed(1);
        System.out.println("News Feed for User 1 after Unfollow: " + newsFeed);
    }

    // Simple Pair class
    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

Output:

News Feed for User 1: 104 103 102 101 
News Feed for User 1 after Unfollow: 102 101

The overall time complexity for this approach is

postTweet(): O(log n)
getNewsFeed(): O(m + n log n)
follow(): O(1)
unfollow(): O(1)

The overall space complexity is

Set (s): O(n)
Map (mp): O(m), where m is the number of users.

Conclusion

In this article, we have learned how to create functionality of Twitter using data structures and algorithms to solve this interesting leetcode problem. And also implemented that in C++, Java, and Python. And discussed time and space complexities.