Design Twitter

Problem

Design a simplified Twitter. Implement void postTweet(int userId, int tweetId); List<Integer> getNewsFeed(int userId) — the 10 most recent tweet ids posted by the user or anyone they follow, newest first; void follow(int followerId, int followeeId); void unfollow(int followerId, int followeeId). A user implicitly follows themselves.

Constraints

• 1 ≤ userId, tweetId ≤ 10⁴
• feed returns at most 10 ids
• at most 3·10⁴ calls

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

import heapq
from collections import defaultdict
class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)     # user -> [(time, tweetId)]
        self.following = defaultdict(set)   # user -> set(followees)

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

    def getNewsFeed(self, userId):
        users = self.following[userId] | {userId}
        candidates = [t for u in users for t in self.tweets[u]]
        top = heapq.nlargest(10, candidates)
        return [tid for _, tid in top]

    def follow(self, followerId, followeeId):
        if followerId != followeeId:
            self.following[followerId].add(followeeId)

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

Java

import java.util.*;

class Twitter {
    private int clock = 0;
    // userId -> list of [time, tweetId]
    private Map<Integer, List<int[]>> tweets = new HashMap<>();
    // userId -> set of followees
    private Map<Integer, Set<Integer>> following = new HashMap<>();

    public Twitter() { }

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

    public List<Integer> getNewsFeed(int userId) {
        // Max-heap on timestamp.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);

        Set<Integer> sources = new HashSet<>();
        sources.add(userId);                          // follows self
        sources.addAll(following.getOrDefault(userId, Collections.emptySet()));

        for (int u : sources) {
            for (int[] t : tweets.getOrDefault(u, Collections.emptyList())) {
                heap.offer(t);
            }
        }

        List<Integer> feed = new ArrayList<>();
        while (!heap.isEmpty() && feed.size() < 10) {
            feed.add(heap.poll()[1]);
        }
        return feed;
    }

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

    public void unfollow(int followerId, int followeeId) {
        Set<Integer> set = following.get(followerId);
        if (set != null) set.remove(followeeId);
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.