355. Design Twitter - Leetcode Solution

Problem Description

The "Design Twitter" problem asks you to implement a simplified version of Twitter. You are to design a system with the following features:

postTweet(userId, tweetId): Compose a new tweet with ID tweetId by user userId.
getNewsFeed(userId): Retrieve the 10 most recent tweet IDs in the user's news feed. The news feed should show tweets from the user themselves and from users they follow, ordered from most recent to least recent.
follow(followerId, followeeId): Follower with ID followerId starts following user with ID followeeId.
unfollow(followerId, followeeId): Follower with ID followerId stops following user with ID followeeId.

Key constraints:

Each tweet has a unique tweetId and is timestamped according to posting order.
Users can follow and unfollow others at any time, but cannot follow themselves.
The system should support efficient retrieval of the news feed.

Thought Process

At first glance, you might think to store all tweets in a single list, then filter and sort them every time a user wants their news feed. However, this would be very inefficient, especially as the number of tweets grows.

Instead, we want to design data structures that allow:

Efficient posting of tweets.
Efficient lookup of a user's own tweets and the tweets of users they follow.
Efficient retrieval of the most recent tweets for a user's news feed.

The challenge is to balance fast writes (posting tweets) with fast reads (fetching the news feed).

We realize that for each user, we need to keep track of who they follow and also maintain a record of their own tweets. For the news feed, we need a way to efficiently merge the most recent tweets from multiple users.

Solution Approach

Let's break down the solution step by step:

Data Structures:
- Followers Map: For each user, maintain a set of user IDs they follow. This allows O(1) add/remove operations and quick lookups.
- Tweets List: For each user, maintain a list of their tweets. Each tweet is stored as a tuple of (timestamp, tweetId).
- Global Timestamp: Use a counter to assign increasing timestamps to tweets, so we can always determine which tweet is newer.
Posting a Tweet: When postTweet is called, add the tweet to the user's list with the current timestamp.
Following/Unfollowing: Update the follower's set of followees accordingly. Prevent users from following themselves.
Fetching the News Feed:
- Gather the most recent tweets from the user and all users they follow.
- Use a min-heap (priority queue) to efficiently merge these tweets and always retrieve the 10 most recent ones.
- This is similar to merging k sorted lists (where k is the number of users the person follows + themselves).

This approach ensures all operations are efficient and scalable, even as the number of users or tweets grows.

Example Walkthrough

Let's walk through a sample scenario:

User 1 posts tweet 5: postTweet(1, 5)
Tweets list for user 1: [(timestamp1, 5)]
User 1's news feed: getNewsFeed(1)
Only tweet 5 is available, so [5] is returned.
User 2 follows user 1: follow(2, 1)
User 2's followees: {1}
User 2's news feed: getNewsFeed(2)
User 2 sees user 1's tweet, so [5] is returned.
User 2 unfollows user 1: unfollow(2, 1)
User 2's followees: {}
User 2's news feed: getNewsFeed(2)
User 2 has no tweets or followees, so [] is returned.

If multiple users post tweets, the news feed merges the tweets by timestamp and returns the 10 most recent.

Time and Space Complexity

Brute-force Approach:

For each getNewsFeed, scan all tweets in the system and filter those posted by the user or their followees. This takes O(N) time per query, where N is the total number of tweets.
Space is O(N) for all tweets.

Optimized Approach (as described above):

postTweet: O(1) time and space per tweet.
follow / unfollow: O(1) time and space per operation.
getNewsFeed: For each user, we only merge the most recent tweets from themselves and each followee. If there are k users (themselves + followees), and each has up to 10 recent tweets, merging is O(k log k) (using a heap). Since k is typically much smaller than the total user base, this is efficient.
Overall space: O(U + N), where U is the number of users (for follow lists) and N is the number of tweets.

Summary

In summary, the "Design Twitter" problem is a classic system design and data structure challenge. The key insights are:

Use hash maps and sets for fast user and followee lookups.
Store tweets per user for efficient access.
Merge recent tweets using a heap for fast news feed retrieval.

This approach balances efficiency and simplicity, making it suitable for both interview settings and real-world scalable systems.

Code Implementation

import heapq
from collections import defaultdict, deque

class Twitter:
    def __init__(self):
        self.timestamp = 0
        self.tweets = defaultdict(deque)  # userId: deque of (timestamp, tweetId)
        self.follows = defaultdict(set)   # userId: set of followees

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].appendleft((self.timestamp, tweetId))
        self.timestamp += 1

    def getNewsFeed(self, userId: int) -> list:
        heap = []
        users = set(self.follows[userId])
        users.add(userId)
        for uid in users:
            for i in range(min(10, len(self.tweets[uid]))):
                ts, tid = self.tweets[uid][i]
                heapq.heappush(heap, (-ts, tid))
        res = []
        while heap and len(res) < 10:
            res.append(heapq.heappop(heap)[1])
        return res

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

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.follows[followerId].discard(followeeId)

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;

class Twitter {
    int timestamp;
    unordered_map<int, unordered_set<int>> follows;
    unordered_map<int, vector<pair<int, int>>> tweets;
public:
    Twitter() : timestamp(0) {}

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

    vector<int> getNewsFeed(int userId) {
        struct Tweet {
            int time, tid;
            Tweet(int t, int id) : time(t), tid(id) {}
            bool operator<(const Tweet& other) const { return time < other.time; }
        };
        priority_queue<Tweet> pq;
        unordered_set<int> users = follows[userId];
        users.insert(userId);
        for (int uid : users) {
            int n = tweets[uid].size();
            for (int i = max(0, n-10); i < n; ++i) {
                pq.push(Tweet(tweets[uid][i].first, tweets[uid][i].second));
            }
        }
        vector<int> res;
        while (!pq.empty() && res.size() < 10) {
            res.push_back(pq.top().tid);
            pq.pop();
        }
        return res;
    }

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

    void unfollow(int followerId, int followeeId) {
        if (followerId != followeeId) follows[followerId].erase(followeeId);
    }
};

import java.util.*;

class Twitter {
    private static int timestamp = 0;
    private Map<Integer, Set<Integer>> follows;
    private Map<Integer, LinkedList<Tweet>> tweets;

    private static class Tweet {
        int time, tid;
        Tweet(int t, int id) { time = t; tid = id; }
    }

    public Twitter() {
        follows = new HashMap<>();
        tweets = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        tweets.putIfAbsent(userId, new LinkedList<>());
        tweets.get(userId).addFirst(new Tweet(timestamp++, tweetId));
    }

    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<Tweet> pq = new PriorityQueue<>((a, b) -> b.time - a.time);
        Set<Integer> users = new HashSet<>(follows.getOrDefault(userId, new HashSet<>()));
        users.add(userId);
        for (int uid : users) {
            LinkedList<Tweet> list = tweets.getOrDefault(uid, new LinkedList<>());
            int cnt = 0;
            for (Tweet tweet : list) {
                pq.offer(tweet);
                if (++cnt == 10) break;
            }
        }
        List<Integer> res = new ArrayList<>();
        int cnt = 0;
        while (!pq.isEmpty() && cnt++ < 10) {
            res.add(pq.poll().tid);
        }
        return res;
    }

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

    public void unfollow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        if (follows.containsKey(followerId))
            follows.get(followerId).remove(followeeId);
    }
}

class Twitter {
    constructor() {
        this.timestamp = 0;
        this.tweets = new Map(); // userId: array of [timestamp, tweetId]
        this.follows = new Map(); // userId: set of followees
    }

    postTweet(userId, tweetId) {
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId).unshift([this.timestamp++, tweetId]);
    }

    getNewsFeed(userId) {
        let users = new Set(this.follows.get(userId) || []);
        users.add(userId);
        let heap = [];
        for (let uid of users) {
            let list = this.tweets.get(uid) || [];
            for (let i = 0; i < Math.min(10, list.length); ++i) {
                heap.push(list[i]);
            }
        }
        heap.sort((a, b) => b[0] - a[0]);
        return heap.slice(0, 10).map(x => x[1]);
    }

    follow(followerId, followeeId) {
        if (followerId === followeeId) return;
        if (!this.follows.has(followerId)) this.follows.set(followerId, new Set());
        this.follows.get(followerId).add(followeeId);
    }

    unfollow(followerId, followeeId) {
        if (followerId === followeeId) return;
        if (this.follows.has(followerId)) this.follows.get(followerId).delete(followeeId);
    }
}

AlgoMap.io

Want Help Cracking FAANG?