Design Twitter — Social Media Feed with Top K Posts

Problem

Design a simplified Twitter:

postTweet(userId, tweetId) — compose a tweet
getNewsFeed(userId) — return 10 most recent tweet IDs from followed users (including self)
follow(followerId, followeeId) / unfollow(...) — manage follows

Constraints: Users can follow/unfollow dynamically; feeds must reflect current state.

Key Insight — Heap Merge of Sorted Lists

Each user maintains a list of tweets in reverse-chronological order. getNewsFeed merges up to N such lists (N = followee count) and takes the top 10 — classic k-way merge with a max-heap.

Use a global timestamp to compare tweets across users.

Solutions

Python

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)
        self.following = defaultdict(set)

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

    def getNewsFeed(self, userId: int):
        heap = []
        users = self.following[userId] | {userId}
        for uid in users:
            if self.tweets[uid]:
                idx = len(self.tweets[uid]) - 1
                t, tid = self.tweets[uid][idx]
                heapq.heappush(heap, (t, tid, uid, idx))
        res = []
        while heap and len(res) < 10:
            t, tid, uid, idx = heapq.heappop(heap)
            res.append(tid)
            if idx > 0:
                nt, ntid = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (nt, ntid, uid, idx - 1))
        return res

    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)

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

JavaScript

class Twitter {
    constructor() {
        this.time = 0;
        this.tweets = new Map();
        this.following = new Map();
    }
    postTweet(userId, tweetId) {
        if (!this.tweets.has(userId)) this.tweets.set(userId, []);
        this.tweets.get(userId).push([this.time++, tweetId]);
    }
    getNewsFeed(userId) {
        const users = new Set(this.following.get(userId) || []);
        users.add(userId);
        let all = [];
        for (const uid of users) {
            const tw = this.tweets.get(uid) || [];
            all = all.concat(tw);
        }
        all.sort((a, b) => b[0] - a[0]);
        return all.slice(0, 10).map(x => x[1]);
    }
    follow(followerId, followeeId) {
        if (!this.following.has(followerId)) this.following.set(followerId, new Set());
        this.following.get(followerId).add(followeeId);
    }
    unfollow(followerId, followeeId) {
        if (this.following.has(followerId)) this.following.get(followerId).delete(followeeId);
    }
}

Java

import java.util.*;
class Twitter {
    int time = 0;
    Map<Integer, List<int[]>> tweets = new HashMap<>();
    Map<Integer, Set<Integer>> following = new HashMap<>();
    public void postTweet(int userId, int tweetId) {
        tweets.computeIfAbsent(userId, k -> new ArrayList<>()).add(new int[]{time++, tweetId});
    }
    public List<Integer> getNewsFeed(int userId) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0]-a[0]);
        Set<Integer> users = following.getOrDefault(userId, new HashSet<>());
        users = new HashSet<>(users); users.add(userId);
        for (int uid : users) {
            List<int[]> tw = tweets.getOrDefault(uid, new ArrayList<>());
            if (!tw.isEmpty()) pq.offer(new int[]{tw.get(tw.size()-1)[0], tw.get(tw.size()-1)[1], uid, tw.size()-1});
        }
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty() && res.size() < 10) {
            int[] top = pq.poll(); res.add(top[1]);
            int idx = top[3];
            if (idx > 0) {
                List<int[]> tw = tweets.get(top[2]);
                pq.offer(new int[]{tw.get(idx-1)[0], tw.get(idx-1)[1], top[2], idx-1});
            }
        }
        return res;
    }
    public void follow(int a, int b) { following.computeIfAbsent(a, k->new HashSet<>()).add(b); }
    public void unfollow(int a, int b) { following.getOrDefault(a, new HashSet<>()).remove(b); }
}

C++

#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
using namespace std;
class Twitter {
    int time = 0;
    unordered_map<int, vector<pair<int,int>>> tweets;
    unordered_map<int, unordered_set<int>> following;
public:
    void postTweet(int userId, int tweetId) { tweets[userId].push_back({time++, tweetId}); }
    vector<int> getNewsFeed(int userId) {
        priority_queue<tuple<int,int,int,int>> pq;
        auto users = following[userId]; users.insert(userId);
        for (int uid : users) {
            auto& tw = tweets[uid];
            if (!tw.empty()) {
                int i = tw.size()-1;
                pq.push({tw[i].first, tw[i].second, uid, i});
            }
        }
        vector<int> res;
        while (!pq.empty() && (int)res.size() < 10) {
            auto [t, tid, uid, idx] = pq.top(); pq.pop();
            res.push_back(tid);
            if (idx > 0) pq.push({tweets[uid][idx-1].first, tweets[uid][idx-1].second, uid, idx-1});
        }
        return res;
    }
    void follow(int a, int b) { following[a].insert(b); }
    void unfollow(int a, int b) { following[a].erase(b); }
};

C

/* C: arrays of tweet records per user, sorted merge via index tracking */
/* Same O(N log N) heap approach with struct-based priority queue */

Complexity

Operation	Time	Space
postTweet	O(1)	O(U·T)
getNewsFeed	O(N log N)	O(N)
follow/unfollow	O(1)	O(U²)

N = number of followees, U = users, T = tweets per user.