Design Twitter

The problem

Build a small Twitter. operations lists the calls to carry out, in order, and values holds the arguments of each call at the same position. "postTweet" [userId, tweetId] posts a tweet. "follow" and "unfollow" [followerId, followeeId] make the first user start or stop following the second. "getNewsFeed" [userId] asks for the ids of the 10 most recently posted tweets, newest first, among that user's own tweets and the tweets of the users they follow. The feed is shorter, or empty, when fewer such tweets exist. Return a list with one result per call: the feed for "getNewsFeed" and null for every other call, including the opening "Twitter".

What to write

function solve(operations: string[], values: number[][]): (number[] | null)[]

Input
operations = ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
values = [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

Output
[null,null,[5],null,null,[6,5],null,[5]]

Input
operations = ["Twitter","getNewsFeed","follow","unfollow","postTweet","getNewsFeed"]
values = [[],[1],[1,1],[1,1],[1,8],[1]]

Output
[null,[],null,null,null,[8]]

Constraints

Tweet IDs are unique.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A feed never holds more than 10 tweets, however many exist, so gathering every tweet and sorting them does far more work than the answer needs. Tweet ids are unique but say nothing about time: the newest tweet is the one posted by the latest call.

2. Hint 2: Ask a smaller question

   Three tweets are posted in this order: 5 by user 1, 6 by user 2, 7 by user 1. User 1 follows nobody. Work out user 1's feed by hand. Which tweet did you look at first, and how did you decide about each one?

3. Hint 3: Name the pattern

   No ready-made structure answers a feed, so build one from two simple parts: one list of all tweets in the order they were posted, and for each user a set of the users they follow. Designing storage around the calls you must answer is the purpose-built data structure pattern. Read the lesson on purpose-built data structure.

4. Hint 4: State the invariant

   The tweet list is always in posting order, oldest first, because a post only ever adds to the end. So walking the list from the end meets the tweets from newest to oldest, and the first 10 that belong in the feed are the feed.

5. Hint 5: Sketch the pseudocode

   postTweet: append (author, tweet id) to the list. follow: add the followee to the follower's set, making the set if needed. unfollow: remove the followee from that set, if there is one. getNewsFeed: walk the list from the end, keep an id when its author is the user or in the user's set, and stop at 10 ids.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep a global chronological tweet log and, for each user, the set of users they follow. Scan backward until ten eligible tweets are found. This simple reference trades feed speed for straightforward writes.

The slow way

For every feed, collect all the tweets of the user and of everyone they follow, sort them by posting time, newest first, and take the first 10. It is correct, but it needs a time stored with every tweet, and it sorts every tweet those users ever posted to return 10 of them.

The insight

The calls arrive in time order, so a list that only grows at its end is already sorted by time: no clock and no sorting are needed. Read from the end, the list gives the tweets newest first, and a feed can stop as soon as it has 10. A set per user answers "does this user follow that author?" in about one step.

Step by step

1. Keep every tweet in one list, oldest first, with its author. Posts arrive in time order, so adding each one to the end keeps the list sorted by time for free. The author is stored with the id because a feed chooses tweets by who wrote them.
2. Keep, for each user, the set of users they follow. A feed asks again and again whether the user follows a tweet's author. A set answers that in about one step, and following the same user twice changes nothing.
3. Carry out the operations in order and collect one result for each. The calls come as two lists, the names and their arguments. Each call changes the stored data or reads it, and the answer needs one entry per call, null when the call returns nothing.
4. A post adds the author and the tweet id to the end of the list. The end of the list is the newest position. Appending there keeps the oldest-first order without moving or comparing any earlier tweet.
5. A follow or an unfollow changes the follower's set. Only the follower's own set changes, because a feed looks up who the reader follows, never who follows the author. The set is made at the first follow, and an unfollow without a set has nothing to remove.
6. A feed walks the list from the newest tweet until it has kept 10. Walking backward meets the tweets newest first, which is the order the feed wants. Once 10 are kept, every tweet still unread is older, so the walk can stop.
7. Keep a tweet whose author is the user or someone the user follows. A user always sees their own tweets, so the author is compared with the user first. Any other author is looked up in the user's set, and a user without a set follows nobody.

The same numbered steps are the comments in each solution.

function solve(operations, values) {
  // 1. Keep every tweet in one list, oldest first, with its author
  const tweets = [];
  // 2. Keep, for each user, the set of users they follow
  const follows = new Map();
  // 3. Carry out the operations in order and collect one result for each
  return operations.map((op, i) => {
    // "Twitter" only creates the two stores, so it has no result.
    if (op === "Twitter") return null;
    // 4. A post adds the author and the tweet id to the end of the list
    if (op === "postTweet") {
      const [userId, tweetId] = values[i];
      tweets.push([userId, tweetId]);
      return null;
    }
    // 5. A follow or an unfollow changes the follower's set
    if (op === "follow") {
      const [followerId, followeeId] = values[i];
      if (!follows.has(followerId)) follows.set(followerId, new Set());
      follows.get(followerId).add(followeeId);
      return null;
    }
    if (op === "unfollow") {
      const [followerId, followeeId] = values[i];
      follows.get(followerId)?.delete(followeeId);
      return null;
    }
    // 6. A feed walks the list from the newest tweet until it has kept 10
    const [userId] = values[i];
    const feed = [];
    for (let j = tweets.length - 1; j >= 0 && feed.length < 10; j--) {
      const [authorId, tweetId] = tweets[j];
      // 7. Keep a tweet whose author is the user or someone the user follows
      if (authorId === userId || follows.get(userId)?.has(authorId))
        feed.push(tweetId);
    }
    return feed;
  });
}

function solve(operations: string[], values: number[][]): (number[] | null)[] {
  // 1. Keep every tweet in one list, oldest first, with its author
  const tweets: [number, number][] = [];
  // 2. Keep, for each user, the set of users they follow
  const follows = new Map<number, Set<number>>();
  // 3. Carry out the operations in order and collect one result for each
  return operations.map((op, i) => {
    // "Twitter" only creates the two stores, so it has no result.
    if (op === "Twitter") return null;
    // 4. A post adds the author and the tweet id to the end of the list
    if (op === "postTweet") {
      const [userId, tweetId] = values[i];
      tweets.push([userId, tweetId]);
      return null;
    }
    // 5. A follow or an unfollow changes the follower's set
    if (op === "follow") {
      const [followerId, followeeId] = values[i];
      if (!follows.has(followerId)) follows.set(followerId, new Set());
      follows.get(followerId)!.add(followeeId);
      return null;
    }
    if (op === "unfollow") {
      const [followerId, followeeId] = values[i];
      follows.get(followerId)?.delete(followeeId);
      return null;
    }
    // 6. A feed walks the list from the newest tweet until it has kept 10
    const [userId] = values[i];
    const feed: number[] = [];
    for (let j = tweets.length - 1; j >= 0 && feed.length < 10; j--) {
      const [authorId, tweetId] = tweets[j];
      // 7. Keep a tweet whose author is the user or someone the user follows
      if (authorId === userId || follows.get(userId)?.has(authorId))
        feed.push(tweetId);
    }
    return feed;
  });
}

def solve(operations, values):
    # 1. Keep every tweet in one list, oldest first, with its author
    tweets = []
    # 2. Keep, for each user, the set of users they follow
    follows = {}
    # 3. Carry out the operations in order and collect one result for each
    out = []
    for op, args in zip(operations, values):
        result = None
        # 4. A post adds the author and the tweet id to the end of the list
        if op == "postTweet":
            user_id, tweet_id = args
            tweets.append((user_id, tweet_id))
        # 5. A follow or an unfollow changes the follower's set
        elif op == "follow":
            follower_id, followee_id = args
            if follower_id not in follows:
                follows[follower_id] = set()
            follows[follower_id].add(followee_id)
        elif op == "unfollow":
            follower_id, followee_id = args
            if follower_id in follows:
                follows[follower_id].discard(followee_id)
        # 6. A feed walks the list from the newest tweet until it has kept 10
        elif op == "getNewsFeed":
            user_id = args[0]
            feed = []
            for author_id, tweet_id in reversed(tweets):
                if len(feed) == 10:
                    break
                # 7. Keep a tweet whose author is the user or someone the user follows
                if author_id == user_id or author_id in follows.get(user_id, set()):
                    feed.append(tweet_id)
            result = feed
        # "Twitter" and the updates leave the result as None.
        out.append(result)
    return out

Example 1, traced

Input
operations = ["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
values = [[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

Output
[null,null,[5],null,null,[6,5],null,[5]]

Why it works

The list holds every tweet in posting order, so a walk from its end sees the tweets from newest to oldest. A tweet belongs in a user's feed exactly when its author is that user or is in that user's set, and that is the test the walk applies. So the first 10 tweets kept are the 10 newest that belong.

Time and space

Time O(total tweets) feed; O(1) average updates, extra space O(tweets + follows). A post, a follow and an unfollow each take about one step on average, like any lookup in a map or a set. A feed can walk the whole list when fewer than 10 tweets belong in it. Every tweet and every follow is stored once.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Compare the author with the user as well as with the set. If own tweets appear only because the user sits in their own set, the unfollow in example 2 empties the last feed: [] instead of [8].
• A user who never followed anyone has no set. Reading that set directly fails when their feed meets another user's tweet: Python raises a KeyError and JavaScript a TypeError. Treat a missing set as an empty one.
• Order by when a tweet was posted, not by its id. Ids are unique but need not grow: after tweet 9 and then tweet 3, the feed is [3, 9], and sorting by id would give [9, 3].

Pattern

Purpose-built data structure. Builds on Contains Duplicate and Time Based Key Value Store.

Keep going