Start learning free

LESSON 407 OF 572 · HEAP

Design Twitter in C#: A Max-Heap Merge of Each User's Tweets

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 24
    Ctrl + Enter to check

    C# · HEAP

    Design Twitter in C#, explained

    Problem overview

    You write the class Twitter with four methods. PostTweet(userId, tweetId) posts a tweet. Follow(followerId, followeeId) and Unfollow(followerId, followeeId) change who sees whose tweets. GetNewsFeed(userId) returns the ids of the 10 most recent tweets posted by the user and by the people the user follows, newest first, as a List<int>.

    The rules around the edges: following is one way; following someone twice, following yourself, and unfollowing someone you do not follow change nothing; your own tweets are always in your feed; a feed with fewer than 10 tweets returns all of them, and a feed with none returns an empty list.

    Here is the first example in use. User 1 posts tweet 5, follows user 2, who posts tweet 6, and then unfollows. The feed of user 1 after each stage:

    5
6 5
5

    Tweet ids do not tell which tweet is newer: in the second example, tweet 106 is newer than tweet 201. Newness comes from the order of the PostTweet calls.

    Approach: merge, don't sort everything

    The simple solution is to collect every tweet of every person in the feed, sort them by time, and take 10. That costs time that grows with every tweet ever posted, and a user who follows a prolific account pays for its whole history on every call, even though only 10 tweets are shown.

    The better idea uses one fact: each user's tweets are already in order, because they are appended as they are posted. Finding the 10 newest tweets across several sorted lists is a merge, the same shape as merging k sorted lists. A heap holds the next candidate from each list:

    • Put the newest tweet of each person in the feed into a max-heap ordered by time.
    • The top is the newest tweet of all. Take it out and add its id to the feed.
    • That person's next older tweet is now their newest tweet not shown yet, so push it in.
    • Stop after 10 tweets or when the heap is empty.

    The heap never holds more than one entry per person, and at most 10 tweets are taken out. With F people in the feed, GetNewsFeed costs O(F log F) at most to build the heap and a further O(10 log F) for the merge, regardless of how many tweets exist. PostTweet, Follow and Unfollow are O(1).

    To compare tweets you need a clock. The class keeps one counter that goes up with every tweet, and stores each tweet as the pair (time, id).

    Step by step

    1. Declare time, the global clock, starting at 0. Every tweet gets the next value, so a later tweet always has a bigger time.
    2. Declare tweets, a Dictionary<int, List<int[]>>: for each user, the list of their tweets, oldest first, each an int[] holding the time and the id. A user gets a list only when they first post.
    3. Declare following, a Dictionary<int, HashSet<int>>: for each user, the set of people they follow. A set ignores a repeated follow and adds and removes in O(1).
    4. PostTweet moves the clock on, creates the user's list if it is their first tweet, and adds new int[]{time, tweetId} to the end of it.
    5. GetNewsFeed first builds users: the user themself, then everyone they follow, added with AddRange. The user is added separately because Follow never stores a user following themself.
    6. It creates the heap newest, a PriorityQueue<int[], int>. Its comparer Comparer<int>.Create((a, b) => b - a) reverses the order of the priorities, so the biggest time comes out first. Each element is {user, index}, where index is the position of a tweet in that user's list, and its priority is the tweet's time.
    7. For each person who has posted, the newest tweet (the last in the list) goes in.
    8. The loop runs while the heap is not empty and the feed has fewer than 10 ids. It takes the top, adds that tweet's id to the feed, and if the person has an older tweet (index > 0) it pushes that one in with its own time.
    9. Follow returns at once if both ids are equal, creates the set if needed, and adds the followee. Unfollow removes the followee if the follower has a set.

    The solution in C#

    class Twitter {
    int time = 0;
    Dictionary<int, List<int[]>> tweets = new Dictionary<int, List<int[]>>();
    Dictionary<int, HashSet<int>> following = new Dictionary<int, HashSet<int>>();

    public void PostTweet(int userId, int tweetId) {
        time++;
        if (!tweets.ContainsKey(userId)) {
            tweets[userId] = new List<int[]>();
        }
        tweets[userId].Add(new int[]{time, tweetId});
    }

    public List<int> GetNewsFeed(int userId) {
        List<int> users = new List<int>();
        users.Add(userId);
        if (following.ContainsKey(userId)) {
            users.AddRange(following[userId]);
        }
        PriorityQueue<int[], int> newest = new PriorityQueue<int[], int>(Comparer<int>.Create((a, b) => b - a));
        foreach (int user in users) {
            if (tweets.ContainsKey(user)) {
                int index = tweets[user].Count - 1;
                newest.Enqueue(new int[]{user, index}, tweets[user][index][0]);
            }
        }
        List<int> feed = new List<int>();
        while (newest.Count > 0 && feed.Count < 10) {
            int[] top = newest.Dequeue();
            int user = top[0], index = top[1];
            feed.Add(tweets[user][index][1]);
            if (index > 0) {
                newest.Enqueue(new int[]{user, index - 1}, tweets[user][index - 1][0]);
            }
        }
        return feed;
    }

    public void Follow(int followerId, int followeeId) {
        if (followerId == followeeId) {
            return;
        }
        if (!following.ContainsKey(followerId)) {
            following[followerId] = new HashSet<int>();
        }
        following[followerId].Add(followeeId);
    }

    public void Unfollow(int followerId, int followeeId) {
        if (following.ContainsKey(followerId)) {
            following[followerId].Remove(followeeId);
        }
    }
}

    C# details worth knowing: the heap stores the index of a tweet rather than the tweet itself, which is what makes "the same user's previous tweet" easy to find, at index - 1. The comparer subtracts priorities; that is safe here because times are small positive counters (at most 100,000 calls), so b - a cannot overflow. PriorityQueue orders only by priority, so the times, which are all different, decide everything. HashSet<int>.Remove returns false and does nothing when the value is absent, which is why unfollowing a stranger needs no check.

    Complexity

    • PostTweet, Follow, Unfollow: O(1) each, apart from the occasional growth of a list or dictionary.
    • GetNewsFeed: O(F log F) for F people in the feed. The heap is built by F pushes, and at most 10 pops and 10 pushes follow.
    • Space: O(T + L) for T tweets and L follow links. A feed call uses O(F) extra for the heap.

    Testing

    The second example has users 1 and 2 taking turns posting 6 tweets each (101 to 106, and 201 to 206), with user 1 following user 2. The two feeds:

    206 106 205 105 204 104 203 103 202 102
206 205 204 203 202 201

    User 1 has 12 tweets in their feed and sees the newest 10, so 101 and 201 are left out. User 2 follows nobody, so only their own tweets appear.

    A third check with three users. User 1 posts 10 and 11, user 2 posts 20 and 21, user 3 posts 30, interleaved as 10, 20, 11, 30, 21. User 1 follows users 2 and 3. The feeds of user 1 and user 2:

    21 30 11 20 10
21 20

    The edge cases from the third example behave as described: a brand-new user with no tweets gets an empty list, Follow(3, 3) leaves tweet 7 appearing once, Unfollow(3, 4) on a stranger changes nothing, and following user 4 before they post still works, so after user 4 posts tweet 8 the feed of user 3 is 8 7.

    Edge cases and common mistakes

    • Ordering by tweet id. Ids are arbitrary; use the clock.
    • Following yourself. If it were stored, your own tweets would be collected twice and show up twice in the feed.
    • Pushing all of a person's tweets. Only the newest goes in first; the older ones wait their turn. Pushing everything turns the method back into a full sort.
    • Reading the last tweet of a user who never posted. People who never posted have no entry in tweets, so check ContainsKey before reading their last tweet.
    • A reversed comparer. A default PriorityQueue is a min-heap; without the comparer the feed would come out oldest first.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free