Design Twitter

NeetCode: Design Twitter · LeetCode: 355. Design Twitter · Difficulty: Medium

Design a class with these methods:

postTweet(userId, tweetId): the user posts a tweet.
getNewsFeed(userId): returns the ids of the 10 most recent tweets posted by the user or anyone they follow, newest first.
follow(followerId, followeeId) and unfollow(followerId, followeeId).

The class is Twitter, with LeetCode's method names.

Example

Text

postTweet(1, 5)
getNewsFeed(1)  -> [5]
follow(1, 2)
postTweet(2, 6)
getNewsFeed(1)  -> [6, 5]
unfollow(1, 2)
getNewsFeed(1)  -> [5]

Brute force: one global list, filter and sort

Keep every tweet as (time, user_id, tweet_id) in one ArrayList, where time is the position in posting order. For a feed, keep the tweets whose author is the user or someone they follow, sort by time descending, and take 10.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Twitter {
    private final List<int[]> tweets = new ArrayList<>();            // {time, userId, tweetId}
    private final Map<Integer, Set<Integer>> following = new HashMap<>(); // userId -> ids they follow

    public Twitter() {
    }

    public void postTweet(int userId, int tweetId) {
        int time = tweets.size(); // later tweets get larger times
        tweets.add(new int[]{time, userId, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> followed = following.getOrDefault(userId, new HashSet<>());
        List<int[]> feed = new ArrayList<>();
        for (int[] t : tweets) {
            if (t[1] == userId || followed.contains(t[1])) {
                feed.add(t);
            }
        }
        feed.sort((a, b) -> Integer.compare(b[0], a[0])); // newest first
        List<Integer> ids = new ArrayList<>();
        for (int i = 0; i < Math.min(10, feed.size()); i++) {
            ids.add(feed.get(i)[2]);
        }
        return ids;
    }

    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);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Twitter t = new Twitter();
        t.postTweet(1, 5);
        System.out.println(t.getNewsFeed(1));
        t.follow(1, 2);
        t.postTweet(2, 6);
        System.out.println(t.getNewsFeed(1));
        t.unfollow(1, 2);
        System.out.println(t.getNewsFeed(1));
    }
}

Output

[5]
[6, 5]
[5]

Time: O(T log T) per feed for T total tweets; the other methods are O(1). Space: O(T).

Optimal: per-user tweet lists merged with a max-heap

Store each user's tweets in their own ArrayList, oldest first. Each list is already sorted by time, so the feed is the first 10 elements of a k-way merge of the lists of the user and of everyone they follow.

Push the newest tweet of each relevant user into a max-heap ordered by time. Java's PriorityQueue is a min-heap, so the comparator (a, b) -> Integer.compare(b[0], a[0]) reverses the order.
Poll the heap: the top is the newest remaining tweet overall. Append its id to the feed.
Push the next-older tweet of the same author, if any.
Stop after 10 tweets or when the heap is empty.

Text

user 1: [.., 5@t1]      user 2: [.., 9@t4, 6@t2]
heap = {5@t1, 9@t4}  -> poll 9  -> add 6@t2  -> poll 6  -> poll 5  -> feed [9, 6, 5]

The heap never holds more than one tweet per author, so the work depends on the number of followed users, not on the total number of tweets.

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

class Twitter {
    private static final int FEED_SIZE = 10;

    private int clock = 0; // increases with every posted tweet
    private final Map<Integer, List<int[]>> tweets = new HashMap<>();      // userId -> {time, tweetId}, oldest first
    private final Map<Integer, Set<Integer>> following = new HashMap<>();  // userId -> ids they follow

    public Twitter() {
    }

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

    public List<Integer> getNewsFeed(int userId) {
        // The user's own tweets count too. A set keeps each author once, even if the user follows themselves.
        Set<Integer> authors = new HashSet<>();
        authors.add(userId);
        authors.addAll(following.getOrDefault(userId, new HashSet<>()));

        // Heap entry: {time, tweetId, author, position in the author's list}.
        // The comparator orders by time descending, so the newest tweet is on top.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0]));
        for (int author : authors) {
            List<int[]> list = tweets.get(author);
            if (list != null) {
                int last = list.size() - 1; // the author's newest tweet
                heap.add(new int[]{list.get(last)[0], list.get(last)[1], author, last});
            }
        }

        List<Integer> feed = new ArrayList<>();
        while (feed.size() < FEED_SIZE && !heap.isEmpty()) {
            int[] top = heap.poll();
            feed.add(top[1]);
            int pos = top[3];
            if (pos > 0) {
                // Replace the popped tweet by the same author's next-older one.
                int[] older = tweets.get(top[2]).get(pos - 1);
                heap.add(new int[]{older[0], older[1], top[2], pos - 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);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Twitter t = new Twitter();
        t.postTweet(1, 5);
        System.out.println(t.getNewsFeed(1));
        t.follow(1, 2);
        t.postTweet(2, 6);
        System.out.println(t.getNewsFeed(1));
        t.unfollow(1, 2);
        System.out.println(t.getNewsFeed(1));
        for (int id = 100; id < 112; id++) {
            t.postTweet(1, id);
        }
        System.out.println(t.getNewsFeed(1));
    }
}

Output

[5]
[6, 5]
[5]
[111, 110, 109, 108, 107, 106, 105, 104, 103, 102]

Time: postTweet, follow and unfollow are O(1). getNewsFeed is O(f + 10 log f) for f followed users (building the heap, then at most 10 pops and pushes). Space: O(T + F) for T tweets and F follow relations.

Edge cases

A user with no tweets and no followees gets an empty feed.
A user does not need to follow themselves; their own tweets are always included. The author set holds each id once, so follow(1, 1) does not duplicate tweets.
unfollow of someone who is not followed does nothing.
Fewer than 10 tweets available: the heap empties and the feed is shorter.

How to explain it in an interview

Each user's tweets are stored in posting order, so every list is already sorted by time.
The feed is the 10 newest elements across several sorted lists: a k-way merge.
Use a max-heap keyed by time that holds at most one tweet per author; poll the newest, then push that author's next-older tweet.
Only 10 pops are needed, so the cost depends on the number of followed users, not on total tweets.
A global counter gives tweets a total order, so times never tie.
postTweet, follow and unfollow are O(1); getNewsFeed is O(f + 10 log f).