Start learning free

LESSON 408 OF 573 · HEAP

Design Twitter in Scala: Per-User Lists Merged with a Heap

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

    SCALA · HEAP

    Design Twitter in Scala, explained

    Problem overview

    The task is a small social feed. Users post tweets and follow each other, and each user's news feed is the 10 most recent tweets posted by that user and by the people they follow, newest first. The class Twitter has four methods:

    • postTweet(userId: Int, tweetId: Int): Unit posts a tweet. Every call posts later than all the calls before it.
    • getNewsFeed(userId: Int): List[Int] returns the ids of the 10 newest tweets in the feed, newest first. A feed with fewer than 10 tweets returns all of them, and an empty feed returns an empty list.
    • follow(followerId: Int, followeeId: Int): Unit and unfollow(followerId: Int, followeeId: Int): Unit change who sees whose tweets. Following is one way. Following someone twice, following yourself and unfollowing someone you don't follow change nothing, and your own tweets are always in your feed.

    Example: user 1 posts tweet 5, so user 1's feed is 5. User 1 follows user 2, who posts tweet 6, and the feed becomes 6 5. After unfollow(1, 2) the feed is 5 again.

    Approach

    The simple way and its cost

    Store all tweets in one list. To build a feed, filter the list for tweets from the user and the people they follow, sort by time, and take 10. Every call to getNewsFeed then looks at every tweet ever posted, so it slows down as the service grows. The lesson asks for O(1) in postTweet, follow and unfollow, and O(F log F) in getNewsFeed, where F is the number of people the user follows.

    A clock, one list per user, one set per user

    Tweet ids say nothing about age: tweet 106 can be newer than tweet 201. So the class keeps a clock, a counter that goes up by one for every tweet posted. A tweet is stored as the pair (time, tweetId).

    Each user has a list of their own tweets. Times only grow, so appending keeps every list sorted from oldest to newest, and a user's newest tweet is always at the end. Each user also has a set of the people they follow, which adds and removes in O(1) and ignores repeats.

    Merging the lists with a heap

    A feed is the 10 newest tweets out of several lists, each sorted by time. This is the same shape as merging sorted lists: the heap holds the next candidate of every list, and the largest time comes out first.

    1. Put each person's newest tweet in a max-heap, as an entry (time, user, index).
    2. Take the top entry. It is the newest tweet not yet shown, over everyone in the feed. Add its id to the result.
    3. If that user has an older tweet, at index - 1, put it in the heap. It is now their newest tweet not yet shown.
    4. Stop after 10 tweets, or when the heap is empty.

    The heap holds at most one entry per person, so every push and pop costs O(log F), and no more than 10 tweets ever leave it.

    Step by step

    1. Add the clock: a var time = 0.
    2. Add tweets, a mutable.Map[Int, mutable.ArrayBuffer[(Int, Int)]]: a user's id to their (time, tweetId) pairs, oldest first. A user gets a list the first time they post.
    3. Add following, a mutable.Map[Int, mutable.Set[Int]]: a user's id to the ids they follow.
    4. In postTweet, move the clock on with time += 1.
    5. Create the user's list on the first post: if tweets does not contain userId, store an empty buffer there.
    6. Append (time, tweetId) to tweets(userId) with +=.
    7. In getNewsFeed, start users with the user's own id.
    8. Add the followees with ++= when the user follows anyone. follow never stores a user following themselves, so nobody appears twice.
    9. Declare the heap: newest, a PriorityQueue[(Int, Int, Int)]. Tuples compare by their first value first, so the largest time is on top.
    10. Loop over users. For each person who has posted, find the index of their last tweet, tweets(user).length - 1.
    11. Enqueue the entry (time, user, index), reading the time with ._1. Only the newest tweet of each person goes in now.
    12. Declare feed, an empty buffer of ids.
    13. Loop while the heap is non-empty and the feed has fewer than 10 ids.
    14. Take the top entry and unpack it with val (_, user, index) = newest.dequeue(). The underscore skips the time, which has done its job.
    15. Append the id, tweets(user)(index)._2, to feed.
    16. Refill from the same user: if index > 0, enqueue their previous tweet.
    17. Return feed.toList.
    18. In follow, return at once when the two ids are equal. Create the follower's set if needed, then add the followee with +=.
    19. In unfollow, if the follower has a set, remove the followee with -=. Removing a value that is not there does nothing.

    The solution in Scala

    class Twitter {
    var time = 0
    val tweets = mutable.Map[Int, mutable.ArrayBuffer[(Int, Int)]]()
    val following = mutable.Map[Int, mutable.Set[Int]]()

    def postTweet(userId: Int, tweetId: Int): Unit = {
        time += 1
        if (!tweets.contains(userId)) {
            tweets(userId) = mutable.ArrayBuffer[(Int, Int)]()
        }
        tweets(userId) += ((time, tweetId))
    }

    def getNewsFeed(userId: Int): List[Int] = {
        val users = mutable.ArrayBuffer(userId)
        if (following.contains(userId)) {
            users ++= following(userId)
        }
        val newest = PriorityQueue[(Int, Int, Int)]()
        for (user <- users) {
            if (tweets.contains(user)) {
                val index = tweets(user).length - 1
                newest.enqueue((tweets(user)(index)._1, user, index))
            }
        }
        val feed = mutable.ArrayBuffer[Int]()
        while (newest.nonEmpty && feed.length < 10) {
            val (_, user, index) = newest.dequeue()
            feed += tweets(user)(index)._2
            if (index > 0) {
                newest.enqueue((tweets(user)(index - 1)._1, user, index - 1))
            }
        }
        return feed.toList
    }

    def follow(followerId: Int, followeeId: Int): Unit = {
        if (followerId == followeeId) {
            return
        }
        if (!following.contains(followerId)) {
            following(followerId) = mutable.Set[Int]()
        }
        following(followerId) += followeeId
    }

    def unfollow(followerId: Int, followeeId: Int): Unit = {
        if (following.contains(followerId)) {
            following(followerId) -= followeeId
        }
    }
}

    Using the class looks like this:

    val t = new Twitter
t.postTweet(1, 5)
println(t.getNewsFeed(1))
t.follow(1, 2)
t.postTweet(2, 6)
println(t.getNewsFeed(1))
t.unfollow(1, 2)
println(t.getNewsFeed(1))

    List(5)
List(6, 5)
List(5)

    Scala details worth knowing:

    • Adding a tuple with += needs double parentheses. buffer += ((time, tweetId)) adds one pair. With single parentheses, buffer += (time, tweetId) reads as two arguments, and the compiler reports a type mismatch: it found an Int where it required (Int, Int). The inner pair of parentheses is the tuple.
    • tweets(userId) = ... and tweets(userId) += .... On a mutable map, the first form calls update and stores a value. The second reads the buffer with apply and then calls += on that buffer, so it changes the buffer in place.
    • Tuples in a PriorityQueue. Scala has a default ordering for tuples of Ints, which compares the first elements and then the next ones. Times are all different, so only the first element ever decides.
    • val (_, user, index) = ... unpacks a three-value tuple in one line, and _ skips a value.
    • return in a Unit method. A bare return in follow leaves the method early. It is not needed at the end of a method, because the last expression is the result.
    • feed.toList copies the mutable buffer into the immutable List[Int] that the method returns.
    • The lesson's code uses mutable and PriorityQueue without a prefix. In a file of your own, add import scala.collection.mutable and import scala.collection.mutable.PriorityQueue.

    Complexity

    Time. postTweet, follow and unfollow are O(1) on average: a clock update, a map lookup and an append, or a set insertion or removal. getNewsFeed is O(F log F): it copies the F followees, pushes at most F + 1 entries one by one, and then does at most 10 pops and 10 pushes, each O(log F). The cost does not depend on how many tweets exist.

    Space. O(T + E), where T is the number of tweets and E the number of follow relationships stored. A feed call uses O(F) extra memory for the heap and the user list.

    Edge cases and common mistakes

    • Sorting by tweet id. Ids are not times. After postTweet(1, 900), postTweet(2, 5) and postTweet(1, 300), with user 1 following user 2, the feed of user 1 is 300 5 900: the order of posting, not of ids.
    • More than 10 tweets. If users 1 and 2 take turns posting tweets 101 to 106 and 201 to 206, with user 1 following user 2, the feed of user 1 is 206 106 205 105 204 104 203 103 202 102. Tweets 101 and 201 are left out. User 2 does not follow user 1, so user 2's feed holds only user 2's tweets: 206 205 204 203 202 201.
    • An empty feed returns List(), for a user who never posted and follows nobody who posted.
    • Following yourself. The early return in follow keeps your id out of your own set. Without it, users would hold your id twice: after follow(3, 3) and postTweet(3, 7), the feed would be List(7, 7).
    • Unfollowing a stranger. Without the check on following.contains(followerId), following(followerId) throws NoSuchElementException for a user who never followed anyone. With the check, the call changes nothing.
    • Following before the followee posts. It works, since users is read from following at feed time, and a followee with no list is skipped by tweets.contains(user).
    • Pushing every tweet of everyone into the heap. It gives the right answer, but it costs time proportional to all the tweets. Pushing one entry per person and refilling after each pop is what keeps the feed cheap.

    Testing

    • A new Twitter, then getNewsFeed(3): List().
    • After follow(3, 3) and postTweet(3, 7), getNewsFeed(3) gives List(7).
    • After unfollow(3, 4) and follow(3, 4) the feed is still List(7), and once postTweet(4, 8) is called it is List(8, 7).
    • User 1 follows users 2, 3 and 4. User 2 posts tweets 21 to 24, then user 3 posts 31 to 34, then user 4 posts 41 to 44. User 1's feed is List(44, 43, 42, 41, 34, 33, 32, 31, 24, 23).
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free