226. Design Twitter

Stamp every tweet with a global increasing time. A news feed is the 10 most recent tweets among the user and everyone they follow — gather those tweets and pick the newest ten.

Global clock orders tweets

Keep a global counter time incremented on each post; store each user's tweets as (time, tweetId). Track follow relationships in a set per user.

For getNewsFeed(userId), collect the tweets of the user plus everyone they follow, then take the 10 with the largest timestamps (most recent first). A heap or a simple sort of the gathered tweets both work.

postTweet(u, t): tweets[u].append((time, t)); time += 1
getNewsFeed(u): merge tweets of {u} ∪ following[u]; return top 10 by time
follow(a, b):   following[a].add(b)   (a != b)
unfollow(a, b): following[a].discard(b)

Worked example

postTweet(1,5); getNewsFeed(1)=[5]; follow(1,2); postTweet(2,6); getNewsFeed(1)=[6,5]; unfollow(1,2); getNewsFeed(1)=[5].

Complexity

• Time: getNewsFeed O(T log T) over gathered tweets.
• Space: O(users + tweets).

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 int time = 0;
    private Map<Integer, List<int[]>> tweets = new HashMap<>();   // userId -> [(time, tweetId)]
    private Map<Integer, Set<Integer>> following = new HashMap<>();

    public Twitter() {
    }

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

    public List<Integer> getNewsFeed(int userId) {
        List<int[]> candidates = new ArrayList<>();
        Set<Integer> users = new HashSet<>(following.getOrDefault(userId, new HashSet<>()));
        users.add(userId);
        for (int u : users) {
            candidates.addAll(tweets.getOrDefault(u, new ArrayList<>()));
        }
        candidates.sort((a, b) -> b[0] - a[0]);  // most recent first
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < Math.min(10, candidates.size()); i++) {
            res.add(candidates.get(i)[1]);
        }
        return res;
    }

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

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