Problem statement

Design a tiny version of Twitter: users post tweets, follow and unfollow each other, and read a news feed of the most recent tweets. Write the class Twitter:

• Twitter() creates the service with no users, tweets or follows.
• void postTweet(int userId, int tweetId) records a new tweet with id tweetId by user userId. Every call uses a new tweetId, and later calls are more recent.
• int[] getNewsFeed(int userId) returns the ids of the 10 most recent tweets posted either by userId or by someone userId currently follows, most recent first (fewer if there are fewer such tweets).
• void follow(int followerId, int followeeId) makes followerId follow followeeId (no effect if already following).
• void unfollow(int followerId, int followeeId) makes followerId stop following followeeId (no effect if not following).

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]
Output: [null,null,[5],null,null,[6,5],null,[5]]
Explanation: User 1's feed starts as their own tweet 5. After following user 2, tweet 6 is newer and comes first. After unfollowing, only tweet 5 is left.

Example 2

Input: ["Twitter","postTweet","postTweet","postTweet","follow","getNewsFeed","getNewsFeed"]
[[],[3,41],[4,17],[3,8],[4,3],[4],[9]]
Output: [null,null,null,null,null,[8,17,41],[]]
Explanation: User 4 follows user 3, so their feed holds 3's tweets 8 and 41 and their own 17, newest first. User 9 has posted nothing and follows nobody: an empty feed.

Constraints

• 1 <= userId, followerId, followeeId <= 500
• followerId != followeeId
• 0 <= tweetId <= 10^4
• All the tweets have unique ids
• At most 3 * 10^4 calls are made to postTweet, getNewsFeed, follow and unfollow

Hints for Design Twitter

1. Hint 1

   Give every tweet a timestamp from a global counter, so "most recent" is a comparison of numbers.

2. Hint 2

   Store each user's own tweets in posting order, and each user's followees in a set — follow and unfollow become set operations.

3. Hint 3

   A feed only needs the last 10 tweets of each relevant user: merge those lists by timestamp (a max-heap over the users' newest tweets, or gather the candidates and sort) and keep the first 10.

How to solve Design Twitter

Keep per user a list of (time, tweetId) in posting order and a set of followees. A feed is a merge, newest first, of the tweet lists of the user and their followees — and since only 10 tweets are wanted, only the last 10 of each list can ever matter.

Approach

1. postTweet(u, id): append (time++, id) to u's list.
2. follow(a, b) / unfollow(a, b): add b to / remove b from a's followee set.
3. getNewsFeed(u): for u and every followee, take the last (up to) 10 entries of their list as candidates.
4. Order the candidates by time, newest first, and return the ids of the first 10. (A max-heap seeded with each user's newest tweet does the same merge in O(10 log F).)

Why it works

Every tweet in the feed belongs to u or a followee, so it is in one of the lists considered. Any tweet that is not among its own author's 10 newest has 10 newer tweets from that one author ahead of it, so it can never make a 10-tweet feed — dropping it is safe. Sorting the rest by the global timestamp gives exactly the most recent first.

Complexity

• Time — O(1) for postTweet, follow and unfollow; O(10F log(10F)) for getNewsFeed with F followees
• Space — O(T + E) for T tweets and E follow relations

Pitfalls

• A user's own tweets are in their feed even though they do not follow themselves.
• Tweet ids are not timestamps — order by posting time, not by id.
• Unfollowing someone you do not follow must be a harmless no-op.

Reference solution

Python

from typing import List

class Twitter:

    def __init__(self):
        self.time = 0
        self.tweets = {}    # user -> [(time, tweetId)] in posting order
        self.following = {}  # user -> set of followees

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

    def getNewsFeed(self, userId: int) -> List[int]:
        candidates = []
        for u in {userId} | self.following.get(userId, set()):
            candidates.extend(self.tweets.get(u, [])[-10:])  # older ones can never make the top 10
        candidates.sort(reverse=True)
        return [tweetId for _, tweetId in candidates[:10]]

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

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

Java

class Twitter {
    private int time = 0;
    private Map<Integer, List<int[]>> tweets = new HashMap<>();     // user -> {time, tweetId}
    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[]{time++, tweetId});
    }

    public List<Integer> feedOf(int userId) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        Set<Integer> users = new HashSet<>(following.getOrDefault(userId, Collections.emptySet()));
        users.add(userId);
        for (int u : users) {
            List<int[]> list = tweets.getOrDefault(u, Collections.emptyList());
            for (int j = Math.max(0, list.size() - 10); j < list.size(); j++) heap.add(list.get(j));
        }
        List<Integer> out = new ArrayList<>();
        while (!heap.isEmpty() && out.size() < 10) out.add(heap.poll()[1]);
        return out;
    }

    public int[] getNewsFeed(int userId) {
        return feedOf(userId).stream().mapToInt(Integer::intValue).toArray();
    }

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

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

C++

class Twitter {
    int time = 0;
    unordered_map<int, vector<pair<int, int>>> tweets; // user -> {time, tweetId}
    unordered_map<int, unordered_set<int>> following;
public:
    Twitter() {}

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

    vector<int> getNewsFeed(int userId) {
        vector<int> users(following[userId].begin(), following[userId].end());
        users.push_back(userId);
        vector<pair<int, int>> cand;
        for (int u : users) {
            auto& list = tweets[u];
            for (size_t j = list.size() > 10 ? list.size() - 10 : 0; j < list.size(); j++) cand.push_back(list[j]);
        }
        sort(cand.rbegin(), cand.rend()); // newest first
        vector<int> out;
        for (size_t t = 0; t < cand.size() && t < 10; t++) out.push_back(cand[t].second);
        return out;
    }

    void follow(int followerId, int followeeId) {
        following[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        following[followerId].erase(followeeId);
    }
};

JavaScript

var Twitter = function() {
    this.time = 0;
    this.tweets = {};    // user -> [[time, tweetId]] in posting order
    this.following = {}; // user -> { followee: true }
};

Twitter.prototype.postTweet = function(userId, tweetId) {
    (this.tweets[userId] = this.tweets[userId] || []).push([this.time++, tweetId]);
};

Twitter.prototype.getNewsFeed = function(userId) {
    var users = [userId], f = this.following[userId] || {};
    for (var k in f) users.push(Number(k));
    var cand = [];
    for (var i = 0; i < users.length; i++) {
        var list = this.tweets[users[i]] || [];
        for (var j = Math.max(0, list.length - 10); j < list.length; j++) cand.push(list[j]);
    }
    cand.sort(function(a, b) { return b[0] - a[0]; });
    var out = [];
    for (var t = 0; t < cand.length && t < 10; t++) out.push(cand[t][1]);
    return out;
};

Twitter.prototype.follow = function(followerId, followeeId) {
    (this.following[followerId] = this.following[followerId] || {})[followeeId] = true;
};

Twitter.prototype.unfollow = function(followerId, followeeId) {
    if (this.following[followerId]) delete this.following[followerId][followeeId];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium