Start learning free

LESSON 404 OF 569 · HEAP

Design Twitter in JavaScript: Per-User Lists and 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 23
    Ctrl + Enter to check

    JAVASCRIPT · HEAP

    Design Twitter in JavaScript, explained

    Problem overview

    The class Twitter supports four operations. postTweet(userId, tweetId) posts a tweet. getNewsFeed(userId) returns the ids of the 10 most recent tweets posted by the user and by everyone the user follows, newest first. follow(followerId, followeeId) and unfollow(followerId, followeeId) change who sees whose tweets. Following is one way, so user 1 following user 2 does not put user 1's tweets in user 2's feed.

    Some cases change nothing: following someone you already follow, following yourself, and unfollowing someone you don't follow. A user's own tweets are always in their feed. A feed with fewer than 10 tweets returns all of them, and an empty feed returns an empty array.

    The first example, run on a new Twitter: user 1 posts tweet 5 and asks for the feed, then follows user 2, who posts tweet 6, then asks again, then unfollows. The three feeds are:

    5
6 5
5

    Tweet ids do not tell which tweet is newer. In the second example, tweet 106 is newer than tweet 201. The design has to track time on its own.

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

    The simple approach keeps one list of every tweet. To build a feed, it scans all the tweets, keeps those written by the user or the followed people, sorts them by time and takes 10. That cost grows with every tweet ever posted, even tweets nobody in the feed wrote.

    The better design stores the data in three pieces:

    • a clock, this.time, that goes up by one for every tweet posted, so a newer tweet always has a bigger time;
    • this.tweets: for each user id, that user's tweets as [time, tweetId] pairs, oldest first. Times only grow, so every list stays sorted without any sorting, and the newest tweet is at the end;
    • this.following: for each user id, a Set of the ids that user follows. A set ignores a second follow and adds or removes in constant time.

    With that, postTweet, follow and unfollow do a constant amount of work. The feed is the interesting part. Each person's list is already sorted, so building a feed is a merge of several sorted lists, as in merging sorted linked lists. A max-heap does it: it holds one entry per person, that person's newest tweet not yet shown, and its top is the newest tweet among all of them. Take the top, add it to the feed, and put that person's next older tweet into the heap in its place. After 10 rounds, stop. Only 10 tweets leave the heap, however many tweets exist.

    A run makes this concrete. User 1 posts 50, 51 and 52, user 2 posts 60 and 61, interleaved as 50, 60, 51, 61, 52, and then user 1 follows user 2. The stored data is:

    {"1":[[1,50],[3,51],[5,52]],"2":[[2,60],[4,61]]}

    The heap starts with two entries, the newest tweet of each person: time 5 (tweet 52) and time 4 (tweet 61). The top is time 5, so 52 goes into the feed and user 1's older tweet, time 3, enters the heap. Now the top is time 4, so 61 follows, then 51, then 60, then 50. getNewsFeed(1) returns:

    52 61 51 60 50

    Step by step

    1. Constructor: set this.time to 0, this.tweets to an empty object and this.following to an empty object. A user gets an entry in each only when they first post or follow.
    2. postTweet: first advance the clock with this.time++, so every tweet gets its own, larger time.
    3. If userId has no array yet, create one. The test is !(userId in this.tweets), and the parentheses matter: ! must apply to the whole in test.
    4. Push [this.time, tweetId] onto that user's array. The newest tweet is always last.
    5. getNewsFeed: start an array users with just userId, because your own tweets are always in your feed.
    6. If the user follows anyone, push them all with users.push(...this.following[userId]), which spreads the set into separate arguments. Nobody appears twice, because follow never stores a user following themselves.
    7. Create newest, a MaxHeap whose compare function is (a, b) => a[0] - b[0]. As in the argument of sort, it orders entries by their first number, so the entry with the biggest time is on top. Each entry is [time, user, index]: the tweet's time, its author, and its position in the author's array.
    8. Loop over users. For each person who has posted, take the index of their newest tweet, length - 1, and insert an entry for it. Only one tweet per person goes in at first, because an older tweet of the same person cannot be in the feed before their newer one.
    9. Create the empty array feed.
    10. Loop while the heap is not empty and feed.length < 10. Inside, extract the top entry and unpack it with let [time, user, index] = ....
    11. Push that tweet's id, this.tweets[user][index][1], onto feed.
    12. If index > 0, the author has an older tweet. Insert its entry, with index - 1, so the heap again has one candidate for that person.
    13. Return feed.
    14. follow: if the two ids are equal (===), return at once. Create the follower's set if it does not exist, then add the followee.
    15. unfollow: if the follower has a set, delete the followee from it. Deleting a value that is not in the set does nothing.

    The solution in JavaScript

    var algorithms = require('algorithms')
class Twitter {
    constructor() {
        this.time = 0;
        this.tweets = {};
        this.following = {};
    }

    postTweet(userId, tweetId) {
        this.time++;
        if (!(userId in this.tweets)) {
            this.tweets[userId] = [];
        }
        this.tweets[userId].push([this.time, tweetId]);
    }

    getNewsFeed(userId) {
        let users = [userId];
        if (userId in this.following) {
            users.push(...this.following[userId]);
        }
        let newest = new algorithms.DataStructures.Heap.MaxHeap((a, b) => a[0] - b[0]);
        for (let user of users) {
            if (user in this.tweets) {
                let index = this.tweets[user].length - 1;
                newest.insert([this.tweets[user][index][0], user, index]);
            }
        }
        let feed = [];
        while (!newest.isEmpty() && feed.length < 10) {
            let [time, user, index] = newest.extract();
            feed.push(this.tweets[user][index][1]);
            if (index > 0) {
                newest.insert([this.tweets[user][index - 1][0], user, index - 1]);
            }
        }
        return feed;
    }

    follow(followerId, followeeId) {
        if (followerId === followeeId) {
            return;
        }
        if (!(followerId in this.following)) {
            this.following[followerId] = new Set();
        }
        this.following[followerId].add(followeeId);
    }

    unfollow(followerId, followeeId) {
        if (followerId in this.following) {
            this.following[followerId].delete(followeeId);
        }
    }
}

    JavaScript details worth knowing:

    • Objects as maps. userId in this.tweets checks whether the key exists. Object keys are strings, so key 1 and key "1" are the same slot. Reading a missing key would give undefined, which is why the code tests with in before using the array.
    • The spread operator. push(...set) works because a Set is iterable. The values come out in the order they were added.
    • Destructuring. let [time, user, index] = newest.extract() unpacks the three items of the array into three variables, in order. The variable time is only there to match the entry's shape; the feed does not use it.
    • The compare function is the same kind as the one passed to Array.prototype.sort. Here it makes the heap a max-heap by time.

    Complexity

    postTweet, follow, unfollow: O(1). An array push, a set add and a set delete each take constant time.

    getNewsFeed: O(F log F), where F is the number of people in the feed (the user plus the people they follow). Spreading the set into users and inserting one entry per person costs O(F log F) in total. After that, at most 10 rounds each do one extract and at most one insert on a heap of at most F entries, which is O(10 log F), a constant times log F. The cost does not depend on how many tweets exist. A user following hundreds of people costs more than one following three, but never more because of old tweets.

    Space: the store holds every tweet once, so it is O(T + S) for T tweets and S follow relations. A feed request uses O(F) extra for the heap.

    Edge cases and common mistakes

    • Comparing tweet ids instead of times. Ids are arbitrary: tweet 106 was posted after tweet 201 in the second example. The clock decides the order.
    • An empty feed. A user who has not posted and follows nobody gets []. Because the loop skips people who never posted, no code reads from a missing array.
    • Following yourself. After follow(3, 3) the user must still show tweet 7 once, not twice. Returning early in follow prevents the duplicate. In a run, user 1 following 2, then following 2 again and following 1, ends with a set of size 1.
    • Following before the other user posts. In the third example, user 3 follows user 4 before user 4's first tweet. The feed does not store tweets, only the follow relation, so tweet 8 shows up as soon as it exists: the feed became 8 7.
    • Unfollowing. It only removes the id from the set. The followee's tweets stay stored, and they leave the feed because the user is no longer collected.
    • Fewer than 10 tweets. The loop ends when the heap is empty, so the feed holds whatever exists. With 100 tweets by one user (ids 1001 to 1100), the feed is the 10 newest, 1100 1099 ... 1091.

    Testing

    Outputs of the solution above, one line per getNewsFeed call:

    • Example 1 (post 5; feed; follow 1to2; post 6; feed; unfollow; feed) prints 5, 6 5, 5.
    • Users 1 and 2 following and alternating six tweets each (101 to 106 and 201 to 206, user 1 following user 2): the feed of user 1 is 206 106 205 105 204 104 203 103 202 102 and the feed of user 2 is 206 205 204 203 202 201.
    • A new Twitter: getNewsFeed(3) returns [].
    • The trace above, getNewsFeed(1), returns 52 61 51 60 50.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free