Design Twitter

January 10, 2025

Designing a Simplified Twitter Application

In this article, we explore how to design a simplified version of Twitter, implementing core functionalities such as posting tweets, following and unfollowing users, and retrieving personalized news feeds.

This design focuses on efficiency and simplicity, adhering to the constraints and requirements outlined below.

Problem Description

The goal is to build a lightweight Twitter model that provides the following functionalities:

Post Tweets: Users can post unique tweets identified by a tweet ID.
Follow and Unfollow Users: Users can choose to follow or unfollow other users.
Fetch News Feed: Users can retrieve a news feed consisting of the 10 most recent tweets from themselves and the users they follow.

Methods to Implement

Twitter()
Initializes the Twitter object. This will set up the necessary data structures to manage users, tweets, and their relationships.
postTweet(int userId, int tweetId)
Publishes a new tweet with a unique ID, associating it with the specified user.
getNewsFeed(int userId)
Retrieves up to 10 of the most recent tweets in the user’s personalized news feed. The feed includes tweets from:
- The user themselves.
- All users they are currently following.
  Tweets are sorted in reverse chronological order (most recent first).
follow(int followerId, int followeeId)
Allows a user to follow another user.
unfollow(int followerId, int followeeId)
Allows a user to stop following another user.

Example 1

Input: points = [[0,2],[2,2]], k = 1

Output: [[0,2]]

Example 1:

Input:
["Twitter", "postTweet", [1, 10], "postTweet", [2, 20], "getNewsFeed", [1], "getNewsFeed", [2], "follow", [1, 2], "getNewsFeed", [1], "getNewsFeed", [2], "unfollow", [1, 2], "getNewsFeed", [1]]

Output:
[null, null, null, [10], [20], null, [20, 10], [20], null, [10]]

Explanation:
Twitter twitter = new Twitter();
twitter.postTweet(1, 10); // User 1 posts a new tweet with id = 10.
twitter.postTweet(2, 20); // User 2 posts a new tweet with id = 20.
twitter.getNewsFeed(1);   // User 1's news feed should only contain their own tweets -> [10].
twitter.getNewsFeed(2);   // User 2's news feed should only contain their own tweets -> [20].
twitter.follow(1, 2);     // User 1 follows user 2.
twitter.getNewsFeed(1);   // User 1's news feed should contain both tweets from user 1 and user 2 -> [20, 10].
twitter.getNewsFeed(2);   // User 2's news feed should still only contain their own tweets -> [20].
twitter.unfollow(1, 2);   // User 1 follows user 2.
twitter.getNewsFeed(1);   // User 1's news feed should only contain their own tweets -> [10].

Example 2

Input: points = [[0,2],[2,0],[2,2]], k = 2

Output: [[0,2],[2,0]]

Explanation: The output [2,0],[0,2] would also be accepted.

Constraints:

1 <= k <= points.length <= 1000
-100 <= points[i][0], points[i][1] <= 100

Approach

Key Idea: Max-Heap Simulation

To efficiently retrieve the two heaviest stones, we use a max-heap. However, Python’s heapq library provides a min-heap implementation by default, so we simulate a max-heap by storing negative values.

Algorithm

Steps

Initialize the Heap: Convert all stone weights to negative and push them into a heap.
Simulation Loop:
- Pop the two largest elements (smallest in the min-heap due to negative values).
- If the stones are not equal, compute the new weight and push it back into the heap.
Result:
- If the heap is empty, return 0.
- Otherwise, return the absolute value of the remaining stone.

Hint 1

Can you think of a data structure to store all the information, such as userIds and corresponding followeeIds, or userIds and their tweets? Maybe you should think of a hash data structure in terms of key-value pairs. Also, can you think of a way to determine that a tweet was posted before another tweet?

Hint 2

We use a hash map followMap to store userIds and their unique followeeIds as a hash set. Another hash map, tweetMap, stores userIds and their tweets as a list of (count, tweetId) pairs. A counter count, incremented with each tweet, tracks the order of tweets. The variable count is helpful in distinguishing the time of tweets from two users. This way of storing data makes the functions follow(), unfollow(), and postTweet() run in O(1). Can you think of a way to implement getNewsFeed()? Maybe consider a brute force approach and try to optimize it.

Hint 3

A naive solution would involve taking the tweets of the userId and its followeeIds into a list, sorting them in descending order based on their count values, and returning the top 10 tweets as the most recent ones. Can you think of a more efficient approach that avoids collecting all tweets and sorting? Perhaps consider a data structure and leverage the fact that each user's individual tweets list is already sorted.

There are mainly Two approach to solve this problem –

Sorting
Heap

1. Sorting

Time complexity: for each call and for remaining methods.
Space complexity:

Python

C++

Java

JavaScript

Python

class Twitter:

    def __init__(self):
        self.time = 0
        self.followMap = defaultdict(set)
        self.tweetMap = defaultdict(list)

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

    def getNewsFeed(self, userId: int) -> List[int]:
        feed = self.tweetMap[userId][:]
        for followeeId in self.followMap[userId]:
            feed.extend(self.tweetMap[followeeId])

        feed.sort(key=lambda x: -x[0])  
        return [tweetId for _, tweetId in feed[:10]]

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

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

C++

class Twitter {
    int time;
    unordered_map> followMap;
    unordered_map>> tweetMap;
public:
    Twitter() : time(0) {}

    void postTweet(int userId, int tweetId) {
        tweetMap[userId].push_back({time++, tweetId});
    }

    vector getNewsFeed(int userId) {
        vector> feed = tweetMap[userId];
        for (int followeeId : followMap[userId]) {
            feed.insert(feed.end(), tweetMap[followeeId].begin(), 
                                    tweetMap[followeeId].end());
        }
        sort(feed.begin(), feed.end(), [](auto &a, auto &b) {
            return a.first > b.first;
        });
        vector res;
        for (int i = 0; i < min(10, (int)feed.size()); ++i) {
            res.push_back(feed[i].second);
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            followMap[followerId].insert(followeeId);
        }
    }

    void unfollow(int followerId, int followeeId) {
        followMap[followerId].erase(followeeId);
    }
};

Java

public class Twitter {
    private int time;
    private Map> followMap;
    private Map> tweetMap;

    public Twitter() {
        time = 0;
        followMap = new HashMap<>();
        tweetMap = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        tweetMap.putIfAbsent(userId, new ArrayList<>());
        tweetMap.get(userId).add(new int[]{time++, tweetId});
    }

    public List getNewsFeed(int userId) {
        List feed = new ArrayList<>(tweetMap.getOrDefault(userId, new ArrayList<>()));
        for (int followeeId : followMap.getOrDefault(userId, new HashSet<>())) {
            feed.addAll(tweetMap.getOrDefault(followeeId, new ArrayList<>()));
        }
        feed.sort((a, b) -> b[0] - a[0]);
        List res = new ArrayList<>();
        for (int i = 0; i < Math.min(10, feed.size()); i++) {
            res.add(feed.get(i)[1]);
        }
        return res;
    }

    public void follow(int followerId, int followeeId) {
        if (followerId != followeeId) {
            followMap.putIfAbsent(followerId, new HashSet<>());
            followMap.get(followerId).add(followeeId);
        }
    }

    public void unfollow(int followerId, int followeeId) {
        followMap.getOrDefault(followerId, new HashSet<>()).remove(followeeId);
    }
}

JavaScript

class Twitter {
    constructor() {
        this.time = 0;
        this.followMap = new Map();
        this.tweetMap = new Map();
    }

    /**
     * @param {number} userId
     * @param {number} tweetId
     * @return {void}
     */
    postTweet(userId, tweetId) {
        if (!this.tweetMap.has(userId)) this.tweetMap.set(userId, []);
        this.tweetMap.get(userId).push([this.time++, tweetId]);
    }

    /**
     * @param {number} userId
     * @return {number[]}
     */
    getNewsFeed(userId) {
        let feed = [...(this.tweetMap.get(userId) || [])];
        (this.followMap.get(userId) || new Set()).forEach(followeeId => {
            feed.push(...(this.tweetMap.get(followeeId) || []));
        });
        feed.sort((a, b) => b[0] - a[0]);
        return feed.slice(0, 10).map(x => x[1]);
    }

    /**
     * @param {number} followerId
     * @param {number} followeeId
     * @return {void}
     */
    follow(followerId, followeeId) {
        if (followerId !== followeeId) {
            if (!this.followMap.has(followerId)) this.followMap.set(followerId, new Set());
            this.followMap.get(followerId).add(followeeId);
        }
    }

    /**
     * @param {number} followerId
     * @param {number} followeeId
     * @return {void}
     */
    unfollow(followerId, followeeId) {
        if (this.followMap.has(followerId)) {
            this.followMap.get(followerId).delete(followeeId);
        }
    }
}

2. Heap

Time complexity: for each call and for remaining methods.
Space complexity:

Python

Java

C++

JavaScript

Python

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)

Java

public class Twitter {
    
    private int count;
    private Map> tweetMap;
    private Map> followMap;

    public Twitter() {
        count = 0;
        tweetMap = new HashMap<>();
        followMap = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        tweetMap.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{count--, tweetId});
    }

    public List getNewsFeed(int userId) {
        List res = new ArrayList<>();
        PriorityQueue minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        followMap.computeIfAbsent(userId, k -> new HashSet<>()).add(userId);
        for (int followeeId : followMap.get(userId)) {
            if (tweetMap.containsKey(followeeId)) {
                List tweets = tweetMap.get(followeeId);
                int index = tweets.size() - 1;
                int[] tweet = tweets.get(index);
                minHeap.offer(new int[]{tweet[0], tweet[1], followeeId, index});
            }
        }

        while (!minHeap.isEmpty() && res.size() < 10) {
            int[] curr = minHeap.poll();
            res.add(curr[1]);
            int index = curr[3];
            if (index > 0) {
                int[] tweet = tweetMap.get(curr[2]).get(index - 1);
                minHeap.offer(new int[]{tweet[0], tweet[1], curr[2], index - 1});
            }
        }
        return res;
    }

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

    public void unfollow(int followerId, int followeeId) {
        followMap.computeIfPresent(followerId, (k, v) -> {
            v.remove(followeeId);
            return v;
        });
    }
}

C++

class Twitter {
    int count;
    unordered_map>> tweetMap;
    unordered_map> followMap;

public:
    Twitter() {
        count = 0;
    }

    void postTweet(int userId, int tweetId) {
        tweetMap[userId].push_back({count++, tweetId});
    }

    vector getNewsFeed(int userId) {
        vector res;
        auto compare = [](const vector& a, const vector& b) {
            return a[0] < b[0];
        };
        priority_queue, vector>, decltype(compare)> minHeap(compare);

        followMap[userId].insert(userId);
        for (int followeeId : followMap[userId]) {
            if (tweetMap.count(followeeId)) {
                const vector>& tweets = tweetMap[followeeId];
                int index = tweets.size() - 1;
                minHeap.push({tweets[index][0], tweets[index][1], followeeId, index});
            }
        }

        while (!minHeap.empty() && res.size() < 10) {
            vector curr = minHeap.top();
            minHeap.pop();
            res.push_back(curr[1]);
            int index = curr[3];
            if (index > 0) {
                const vector& tweet = tweetMap[curr[2]][index - 1];
                minHeap.push({tweet[0], tweet[1], curr[2], index - 1});
            }
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        followMap[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        followMap[followerId].erase(followeeId);
    }
};

JavaScript

/**
 * const { MaxPriorityQueue } = require('@datastructures-js/priority-queue');
 */

class Twitter {
    constructor() {
        this.users = new Map();
        this.timestamp = 0;
    }

    /**
     * @param {number} userId
     * @param {number} tweetId
     * @return {void}
     */
    postTweet(userId, tweetId) {
        if (!this.users.has(userId)) {
            this.users.set(userId, { tweets: [], following: new Set() });
        }
        this.users
            .get(userId)
            .tweets.push({ timestamp: this.timestamp, tweetId });
        this.timestamp += 1;
    }

    /**
     * @param {number} userId
     * @return {number[]}
     */
    getNewsFeed(userId) {
        if (!this.users.has(userId)) {
            return [];
        }

        const maxPQ = new MaxPriorityQueue(tweet => tweet.timestamp);
        const seenTweets = new Set();

        const user = this.users.get(userId);
        user.tweets.forEach(tweet => {
            if (!seenTweets.has(tweet.tweetId)) {
                maxPQ.enqueue(tweet);
                seenTweets.add(tweet.tweetId);
            }
        });

        user.following.forEach(followeeId => {
            if (this.users.has(followeeId)) {
                this.users.get(followeeId).tweets.forEach(tweet => {
                    if (!seenTweets.has(tweet.tweetId)) {
                        maxPQ.enqueue(tweet);
                        seenTweets.add(tweet.tweetId);
                    }
                });
            }
        });

        const newsFeed = [];
        for (let i = 0; i < 10 && !maxPQ.isEmpty(); i++) {
            newsFeed.push(maxPQ.dequeue().tweetId);
        }

        return newsFeed;
    }

    /**
     * @param {number} followerId
     * @param {number} followeeId
     * @return {void}
     */
    follow(followerId, followeeId) {
        if (!this.users.has(followerId)) {
            this.users.set(followerId, { tweets: [], following: new Set() });
        }
        this.users.get(followerId).following.add(followeeId);
    }

    /**
     * @param {number} followerId
     * @param {number} followeeId
     * @return {void}
     */
    unfollow(followerId, followeeId) {
        if (this.users.has(followerId)) {
            this.users.get(followerId).following.delete(followeeId);
        }
    }
}

Hint 4

We can use a Max-Heap to efficiently retrieve the top 10 most recent tweets. For each followee and the userId, we insert their most recent tweet from the tweetMap into the heap, along with the tweet's count and its index in the tweet list. This index is necessary because after processing a tweet, we can insert the next most recent tweet from the same user's list. By always pushing and popping tweets from the heap, we ensure that the 10 most recent tweets are retrieved without sorting all tweets.

Unlock this article for Free,
by logging in

Design Twitter

Designing a Simplified Twitter Application

Problem Description

Methods to Implement

Example 1:

Constraints:

Approach

Key Idea: Max-Heap Simulation

Algorithm

Steps

There are mainly Two approach to solve this problem –

1. Sorting

2. Heap

More Articles

30+ Companies are Hiring

Unlock this article for Free, by logging in

Design Twitter

Designing a Simplified Twitter Application

Problem Description

Methods to Implement

Example 1:

Constraints:

Approach

Key Idea: Max-Heap Simulation

Algorithm

Steps

There are mainly Two approach to solve this problem –

1. Sorting

2. Heap

More Articles

30+ Companies are Hiring

Unlock this article for Free,
by logging in