Design Twitter
Designing Twitter on LeetCode: A Comprehensive Guide
Designing complex systems or applications is a common problem faced in the real world. LeetCode's "Design Twitter" problem provides an interesting platform to apply critical thinking and foundational data structure concepts. This article will guide you through problem understanding, solution approaches, and efficient implementations using heaps. Let’s dive in!
Problem Overview
In the "Design Twitter" problem on LeetCode, you are tasked with designing a simplified version of Twitter where users can post tweets, follow other users, and retrieve the most recent tweets. The required operations include:
- Post a tweet: A user can post a new tweet.
- Retrieve the 10 most recent tweets: For a given user id, retrieve up to 10 most recent tweet ids in the user's news feed, which includes the user’s own tweets and the tweets of the users they follow.
- Follow another user: Follow operation that enables a user to follow another user.
- Unfollow a user: Unfollow operation that enables a user to stop following another user.
Understanding the Problem
The problem involves maintaining a dynamic, real-time system where frequent updates occur as new tweets are posted, users follow or unfollow others, and news feeds need to be fetched quickly. The constraints may include handling operations in an efficient manner since users can have a large number of followers and followees.
Key DSA Concepts and Theory
Heaps: Heaps are crucial in solving this problem efficiently. A min-heap can be used to maintain the top K elements, which in our case, are the most recent tweets in the news feed.
HashMaps: These are used to map user relationships and store user tweets. Specifically, we use:
- HashMap for user_follow relationships (to keep track of followers and followees).
- HashMap for storing user tweets with timestamps.
Prioritization: Since we need to endlessly fetch the most recent tweets, understanding how to maintain the tweet's order efficiently while performing operations is essential.
Solution Approach
We'll make use of data structures such as hash maps and heaps to efficiently implement the above functionalities. Let’s break down the solution step by step:
Implementation in C++
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
class Twitter {
private:
int timestamp;
unordered_map<int, unordered_set<int>> following;
unordered_map<int, vector<pair<int, int>>> tweets;
public:
Twitter() : timestamp(0) {}
void postTweet(int userId, int tweetId) {
tweets[userId].emplace_back(timestamp++, tweetId);
}
vector<int> getNewsFeed(int userId) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
if (tweets.count(userId)) {
for (auto &p : tweets[userId]) {
minHeap.push(p);
if (minHeap.size() > 10) minHeap.pop();
}
}
if (following.count(userId)) {
for (int fid : following[userId]) {
if (tweets.count(fid)) {
for (auto &p : tweets[fid]) {
minHeap.push(p);
if (minHeap.size() > 10) minHeap.pop();
}
}
}
}
vector<int> result;
while (!minHeap.empty()) {
result.push_back(minHeap.top().second);
minHeap.pop();
}
reverse(result.begin(), result.end());
return result;
}
void follow(int followerId, int followeeId) {
if (followerId != followeeId) {
following[followerId].insert(followeeId);
}
}
void unfollow(int followerId, int followeeId) {
if (following[followerId].find(followeeId) != following[followerId].end()) {
following[followerId].erase(followeeId);
}
}
};
Implementation in Java
import java.util.*;
public class Twitter {
private static int timestamp = 0;
private Map<Integer, Set<Integer>> following;
private Map<Integer, List<Tweet>> tweets;
private class Tweet {
int time;
int tweetId;
Tweet(int time, int tweetId) {
this.time = time;
this.tweetId = tweetId;
}
}
public Twitter() {
following = new HashMap<>();
tweets = new HashMap<>();
}
public void postTweet(int userId, int tweetId) {
tweets.putIfAbsent(userId, new ArrayList<>());
tweets.get(userId).add(new Tweet(timestamp++, tweetId));
}
public List<Integer> getNewsFeed(int userId) {
PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> a.time - b.time);
if (tweets.containsKey(userId)) {
for (Tweet t : tweets.get(userId)) {
pq.add(t);
if (pq.size() > 10) pq.poll();
}
}
Set<Integer> fids = following.get(userId);
if (fids != null) {
for (int fid : fids) {
if (tweets.containsKey(fid)) {
for (Tweet t : tweets.get(fid)) {
pq.add(t);
if (pq.size() > 10) pq.poll();
}
}
}
}
List<Integer> res = new LinkedList<>();
while (!pq.isEmpty()) {
res.add(0, pq.poll().tweetId);
}
return res;
}
public void follow(int followerId, int followeeId) {
if (followerId != followeeId) {
following.putIfAbsent(followerId, new HashSet<>());
following.get(followerId).add(followeeId);
}
}
public void unfollow(int followerId, int followeeId) {
if (following.containsKey(followerId)) {
following.get(followerId).remove(followeeId);
}
}
}
Time and Space Complexity Analysis
- Post Tweet: O(1). Each tweet is posted with a timestamp which takes constant time.
- Get News Feed: O(N log N), where N is the total tweets from the user and the users they follow, due to the heap's operation to maintain the top 10 recent tweets.
- Follow: O(1). It just involves adding a followee to the set.
- Unfollow: O(1). It involves removing a followee from the set.
Space complexity mainly comes from storing tweets and maintaining the following relationships.
Common Mistakes to Avoid
- Not handling self-follows properly: Ensure the user cannot follow themselves as per the problem constraints.
- Incorrect heap usage: While constructing the newsfeed, ensure the top tweets are correctly maintained in a min-heap to retrieve the 10 most recent tweets efficiently.
- Managing inexistent user operations: It is crucial to handle cases when a user tries to perform operations on users who do not exist yet.
Similar Problems on LeetCode
- LeetCode 355 - Design Twitter: This is the exact problem we discussed.
- LeetCode 346 - Moving Average from Data Stream
Additional Resources and References
- Understanding Heaps: Explore more about heap data structure basics and operations.
- Java PriorityQueue class: Java Documentation
- C++ STL Priority Queue: C++ Reference
This guide should provide comprehensive insights into tackling the "Design Twitter" problem on LeetCode. By effectively harnessing heaps and hash maps, you can design a solution that scales efficiently to handle various users and tweet interactions.