Start learning free

LESSON 403 OF 568 · HEAP

Design Twitter in C++: O(F log F) News Feed with a Max-Heap Merge

Practice O(F log F) Read the full explanation

Design a small version of Twitter. Users post tweets and follow each other, and each user has a news feed: the 10 most recent tweets posted by the user and by the people the user follows, newest first.

Implement the class Twitter:

  • Twitter() creates an empty Twitter: no users, no tweets.
  • postTweet(userId, tweetId) posts a new tweet with the id tweetId by the user userId. Each call posts later than all the calls before it.
  • getNewsFeed(userId) returns the ids of the 10 most recent tweets in the user's news feed, newest first. A feed with fewer than 10 tweets returns all of them, and an empty feed returns no ids at all.
  • follow(followerId, followeeId): the user followerId starts following the user followeeId.
  • unfollow(followerId, followeeId): the user followerId stops following the user followeeId.

Following is one way: when user 1 follows user 2, user 1 sees user 2's tweets, old and new, but not the other way round. Following someone you already follow, following yourself and unfollowing someone you don't follow change nothing; your own tweets are always in your feed.

The input is a list of operations, applied in order to one new Twitter. The output has one line for each getNewsFeed call: the tweet ids it returns, separated by spaces, or an empty line for an empty feed. The starter code spells these names the way your language does.

 

Example 1:

Input:
    postTweet(1, 5)
    getNewsFeed(1)
    follow(1, 2)
    postTweet(2, 6)
    getNewsFeed(1)
    unfollow(1, 2)
    getNewsFeed(1)
Output:
5
6 5
5
Explanation:
User 1's first feed holds their own tweet 5.
User 1 then follows user 2, who posts tweet 6: it is newer than 5, so it comes first.
After the unfollow, user 2's tweets leave user 1's feed again.

Example 2:

Input:
    follow(1, 2)
    postTweet(1, 101)
    postTweet(2, 201)
    postTweet(1, 102)
    postTweet(2, 202)
    ...
    postTweet(1, 106)
    postTweet(2, 206)
    getNewsFeed(1)
    getNewsFeed(2)
Output:
206 106 205 105 204 104 203 103 202 102
206 205 204 203 202 201
Explanation:
Users 1 and 2 take turns posting 6 tweets each (101 to 106 and 201 to 206).
User 1's feed has all 12, but shows only the 10 newest: 101 and 201 are left out.
User 2 doesn't follow user 1, so user 2's feed holds only user 2's own tweets.

Example 3:

Input:
    getNewsFeed(3)
    follow(3, 3)
    postTweet(3, 7)
    getNewsFeed(3)
    unfollow(3, 4)
    follow(3, 4)
    getNewsFeed(3)
    postTweet(4, 8)
    getNewsFeed(3)
Output:

7
7
8 7
Explanation:
The first line of the output is empty: nobody has posted yet, so user 3's feed is empty.
follow(3, 3) changes nothing: tweet 7 appears once. unfollow(3, 4) changes nothing either: user 3 didn't follow user 4.
User 3 follows user 4 before user 4 posts anything; once tweet 8 arrives, it is in user 3's feed.

 

Constraints:

  • 1 <= userId, followerId, followeeId <= 500
  • 0 <= tweetId <= 109
  • All the tweets have different ids.
  • At most 105 calls in total are made to postTweet, getNewsFeed, follow and unfollow.

Note:

postTweet, follow and unfollow should run in O(1) time, and getNewsFeed in O(F log F) time, where F is the number of people the user follows. Collecting and sorting all the tweets of those people at every getNewsFeed would take time that grows with every tweet ever posted.

STEP 1 OF 22
    Ctrl + Enter to check

    C++ · HEAP

    Design Twitter in C++, explained

    Problem overview

    The class Twitter is a small version of the service. Users post tweets and follow each other, and each user has a news feed: the 10 most recent tweets posted by the user and by the people the user follows, newest first. The methods are:

    • postTweet(userId, tweetId): post a tweet. Each call is later than all the calls before it.
    • getNewsFeed(userId): return the ids of the 10 newest tweets in the user's feed, newest first. A feed with fewer than 10 tweets returns all of them, and an empty feed returns an empty vector.
    • follow(followerId, followeeId) and unfollow(followerId, followeeId): start or stop following. Following is one way. Following someone twice, following yourself and unfollowing someone you do not follow change nothing, and your own tweets are always in your feed.

    In the first example, user 1 posts tweet 5, so the feed is 5. User 1 follows user 2, who posts tweet 6; the feed is 6 5. After the unfollow it is 5 again.

    The statement asks for O(1) time for postTweet, follow and unfollow, and O(F log F) for getNewsFeed, where F is the number of people the user follows.

    Approach: a clock, per-user lists and a heap that merges them

    The simple solution collects every tweet of everyone in the feed, sorts them by time and takes 10. That work grows with every tweet ever posted, even though the feed shows only 10.

    The class stores three things:

    • a clock, time, that counts every tweet. Tweet ids do not tell which tweet is newer (tweet 106 can be newer than 201), but the clock does;
    • tweets: for each user, a vector of {time, tweetId} pairs, oldest first. Times only grow, so a new tweet always goes at the end, and the newest tweet of a user is the last one;
    • following: for each user, a set of the ids that user follows. A set ignores a second follow and removes in O(1).

    With that, postTweet, follow and unfollow are each a map lookup and one cheap operation.

    For getNewsFeed, each person's tweets are already a sorted list, newest at the end. Building the feed means merging those sorted lists and stopping after 10 tweets. A max-heap does that: it holds the newest tweet not yet shown of each person. Take the top of the heap, which is the newest tweet among everyone, add it to the feed, then put that person's previous tweet into the heap, because it is now their newest tweet not shown. The heap never holds more than one entry per person, so each push and pop costs O(log F), and at most 10 tweets are taken out.

    Take a small case: user 1 follows user 2, and the posts in order are 101 (user 1), 201 (user 2), 102 (user 1), 202 (user 2), 103 (user 1). The clock gives them the times 1 to 5. The heap starts with the newest tweet of each person, and the feed is built like this:

    start: heap size 2
take time 5 (user 1, id 103), push user 1's older tweet; heap size 2
take time 4 (user 2, id 202), push user 2's older tweet; heap size 2
take time 3 (user 1, id 102), push user 1's older tweet; heap size 2
take time 2 (user 2, id 201); heap size 1
take time 1 (user 1, id 101); heap size 0
feed: 103 202 102 201 101

    Step by step

    1. Declare the clock time, an int set to 0.
    2. Declare tweets as an unordered_map<int, vector<pair<int, int>>>: per user, the {time, tweetId} pairs, oldest first.
    3. Declare following as an unordered_map<int, unordered_set<int>>: per user, the ids that user follows.
    4. In postTweet, advance the clock with time++, so every tweet gets a later time than all before.
    5. Push {time, tweetId} onto tweets[userId]. The end of the vector is the newest position.
    6. In getNewsFeed, make the vector users holding userId: the people whose tweets are in the feed. You cannot follow yourself, so the user is added by hand.
    7. Insert following[userId] at the end of users.
    8. Declare newest, a priority_queue<array<int, 3>> of entries {time, user, index}. A priority_queue is a max-heap, and arrays compare their first element first, so the newest tweet is on top.
    9. Loop over users.
    10. Skip people who never posted, with if (tweets.count(user)). count only looks; tweets[user] would create an empty vector.
    11. Compute index, the position of the user's newest tweet: tweets[user].size() - 1.
    12. Push the entry with the tweet's time, the user and the index.
    13. Declare feed, an empty vector<int>.
    14. Loop while newest is not empty and feed has fewer than 10 ids.
    15. Copy the top entry into top, then pop(). pop() returns nothing, so the entry is read first.
    16. Read user and index from top[1] and top[2]. The time has done its job.
    17. Add the tweet's id, tweets[user][index].second, to feed.
    18. If the user has an older tweet (index > 0), push it: its time, user and index - 1. This is the merge step.
    19. Return feed.
    20. In follow, return at once if the two ids are equal. Storing a self-follow would put the user in users twice.
    21. Insert followeeId into following[followerId]. A set ignores a repeated follow.
    22. In unfollow, erase followeeId from following[followerId]. Erasing a value that is not in the set does nothing. The followee's tweets stay where they are.

    The solution in C++

    class Twitter {
public:
    int time = 0;
    unordered_map<int, vector<pair<int, int>>> tweets;
    unordered_map<int, unordered_set<int>> following;

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

    vector<int> getNewsFeed(int userId) {
        vector<int> users = {userId};
        users.insert(users.end(), following[userId].begin(), following[userId].end());
        priority_queue<array<int, 3>> newest;
        for (int user : users) {
            if (tweets.count(user)) {
                int index = tweets[user].size() - 1;
                newest.push({tweets[user][index].first, user, index});
            }
        }
        vector<int> feed;
        while (!newest.empty() && feed.size() < 10) {
            array<int, 3> top = newest.top();
            newest.pop();
            int user = top[1], index = top[2];
            feed.push_back(tweets[user][index].second);
            if (index > 0) {
                newest.push({tweets[user][index - 1].first, user, index - 1});
            }
        }
        return feed;
    }

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

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

    The C++ details worth a closer look:

    • Arrays in a heap. array<int, 3> is a fixed-size array that compares element by element, like a tuple. The heap therefore orders entries by time first. The times are all different, so the user and the index never decide the order; they only say where the tweet is.
    • Why the index, not the tweet. Keeping index in the entry makes the previous tweet of the same user easy to find: it is at index - 1.
    • count against []. tweets.count(user) reads without inserting. After count(9) on an empty map, the map has 0 entries, and after tweets[9] it has 1. In getNewsFeed the lookup following[userId] does create an empty set for a user who follows nobody; that is harmless.
    • size() is unsigned. tweets[user].size() - 1 is safe because the count check means the vector has at least one tweet. The result is stored in an int.
    • Brace initialisation. {time, tweetId} makes a pair and {a, b, c} makes an array<int, 3> for the push call.
    • Several variables in one line. int user = top[1], index = top[2]; declares two ints. This user is a new variable inside the loop and is unrelated to the loop variable of the earlier for.

    Running the second example, where users 1 and 2 take turns posting 101 to 106 and 201 to 206 and user 1 follows user 2, user 1's feed is 206 106 205 105 204 104 203 103 202 102. Tweets 101 and 201 are left out. User 2, who does not follow user 1, gets 206 205 204 203 202 201.

    Complexity

    Time. postTweet is amortized O(1): a hash lookup and a push_back. follow and unfollow are O(1) on average, being hash-set operations. getNewsFeed is O(F log F): building the list of users takes O(F), putting up to F + 1 entries into the heap takes O(F log F), and the loop takes at most 10 entries out and puts at most 10 in, each O(log F). The work does not depend on how many tweets were ever posted.

    Space: O(T + S) for T tweets and S follow relations, plus O(F) for the heap and the users list during one getNewsFeed call.

    Edge cases and common mistakes

    • Ordering by tweet id. Ids are arbitrary. User 1 posts 900, user 2 posts 50, user 1 posts 10: user 3, who follows both, sees 10 50 900, ordered by posting time, not by id.
    • Your own tweets. A user who follows nobody still sees their own tweets. An empty feed, for a user who has not posted and follows nobody who has, is an empty vector.
    • Following yourself. Without the early return, the user would appear twice in users, and every tweet would show up twice in the feed. After follow(3, 3) and postTweet(3, 7), the feed is just 7.
    • Unfollowing someone you do not follow. Nothing happens, and the feed does not change.
    • Tweets that predate the follow. Following gives access to the person's old tweets too. After postTweet(2, 1), follow(1, 2) shows 1 in user 1's feed. After an unfollow it is gone, and after following again it is back.
    • Following before the first tweet. User 3 follows user 4 who has not posted yet. Once tweet 8 arrives, user 3's feed is 8 7.
    • More than 10 tweets. A user with 20 tweets, numbered 1 to 20, gets 20 19 18 17 16 15 14 13 12 11.
    • Pushing every tweet into the heap. It works, but costs time in the number of tweets. Pushing only the newest of each person and refilling from the same person keeps the heap at F entries.

    Testing

    • postTweet(1, 5), getNewsFeed(1), follow(1, 2), postTweet(2, 6), getNewsFeed(1), unfollow(1, 2), getNewsFeed(1) gives the three feeds 5, 6 5, 5.
    • getNewsFeed(3) on a new Twitter gives an empty feed.
    • follow(3, 3), postTweet(3, 7), getNewsFeed(3) gives 7. Then unfollow(3, 4), follow(3, 4), postTweet(4, 8) and getNewsFeed(3) give 8 7.
    • Twenty tweets by user 1, ids 1 to 20, then getNewsFeed(1) gives 20 19 18 17 16 15 14 13 12 11.
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free