Problem overview
The task is to build a small social feed. Users post tweets, follow and unfollow each other, and ask for a news feed: the 10 most recent tweets posted by the user and by the people the user follows, newest first. The class is Twitter, with four methods:
postTweet(userId, tweetId)posts a tweet. Each call is later than all the calls before it.getNewsFeed(userId)returns up to 10 tweet ids, newest first. A feed with fewer tweets returns all of them, and an empty feed returns an empty array.follow(followerId, followeeId)andunfollow(followerId, followeeId)change who sees whose tweets. Following is one way. Following someone you already follow, following yourself, and unfollowing someone you don't follow change nothing. Your own tweets are always in your feed.
Here is a short session on a new Twitter, with what each getNewsFeed(1) returns:
const t = new Twitter();
t.postTweet(1, 5);
console.log(t.getNewsFeed(1).join(" ")); // 5
t.follow(1, 2);
t.postTweet(2, 6);
console.log(t.getNewsFeed(1).join(" ")); // 6 5
t.unfollow(1, 2);
console.log(t.getNewsFeed(1).join(" ")); // 5Tweet 6 came later than tweet 5, so it comes first. After the unfollow, user 2's tweets leave user 1's feed again. Tweet ids say nothing about age: in a longer run where users 1 and 2 take turns posting 101 to 106 and 201 to 206, user 1's feed is:
206 106 205 105 204 104 203 103 202 102Tweet 106 is newer than tweet 201, so a clock must decide the order, not the ids.
Approach: a clock, per-user lists and a heap
The simple approach gathers all tweets of the user and everyone followed, sorts them by time and takes the first 10. That does work proportional to every tweet ever posted by those people, and it grows with each new tweet.
The better idea uses two facts. Each user's own tweets are already sorted by time, because tweets are appended as they are posted. And a feed needs only 10 tweets. So the feed is a merge of sorted lists, the same idea as merging k sorted linked lists: put the newest tweet of each person into a max-heap, take the top (the newest tweet overall), then replace it with that person's next older tweet. After at most 10 such steps the feed is complete, and older tweets are never touched.
The data kept by the class:
time: a global clock that goes up by 1 for each tweet posted, so a newer tweet always has a bigger time.tweets: for each user id, an array of[time, tweetId]pairs, oldest first.following: for each user id, aSetof the ids they follow. A set ignores a second follow of the same person, and adds and deletes in constant time.
The lesson provides a ready-to-use MaxHeap. You create it with new MaxHeap(compare), where the compare function works as in sort, and it has insert, extract, peek, size and isEmpty.
Step by step
- Declare the three fields.
timestarts at 0.tweetsis an empty object typed{ [userId: number]: number[][] }, an index signature meaning any number can be a key and each value is an array of number arrays.followingis typed the same way withSet<number>values. postTweet: add 1 tothis.time, create the user's array if!(userId in this.tweets)(the parentheses make!apply to the wholeintest), and push[this.time, tweetId]. Times only grow, so each array stays sorted with the newest tweet at the end.getNewsFeed, who is in the feed: start an arrayuserswithuserId, and if the user follows anyone, spread that set into it withusers.push(...this.following[userId]).follownever stores a user following themselves, so nobody appears twice.- Prepare the heap:
new MaxHeap((a, b) => a[0] - b[0])compares entries by their first number, the time, so the newest tweet is on top. Each entry is[time, user, index]: the tweet's time, its author, and its position in that author's array. - Seed it: for each person in
userswho has posted, insert the entry for their last tweet, at indexlength - 1. People who never posted have nothing to show. - Merge: while the heap isn't empty and
feedhas fewer than 10 ids, extract the top entry, unpack it withconst [time, user, index] = ..., and push that tweet's id,this.tweets[user][index][1], ontofeed. - Refill: if the author has an older tweet (
index > 0), insert it as[time of that tweet, user, index - 1]. It is now that person's newest tweet not yet shown. Then returnfeed. follow: return at once when the two ids are equal (===), create a newSetfor the follower if needed, and add the followee.unfollow: if the follower has a set, delete the followee from it. Deleting a value that isn't in a set does nothing.
The solution in TypeScript
class Twitter {
time: number = 0;
tweets: { [userId: number]: number[][] } = {};
following: { [userId: number]: Set<number> } = {};
postTweet(userId: number, tweetId: number): void {
this.time++;
if (!(userId in this.tweets)) {
this.tweets[userId] = [];
}
this.tweets[userId].push([this.time, tweetId]);
}
getNewsFeed(userId: number): number[] {
const users: number[] = [userId];
if (userId in this.following) {
users.push(...this.following[userId]);
}
const newest = new MaxHeap((a, b) => a[0] - b[0]);
for (const user of users) {
if (user in this.tweets) {
const index = this.tweets[user].length - 1;
newest.insert([this.tweets[user][index][0], user, index]);
}
}
const feed: number[] = [];
while (!newest.isEmpty() && feed.length < 10) {
const [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: number, followeeId: number): void {
if (followerId === followeeId) {
return;
}
if (!(followerId in this.following)) {
this.following[followerId] = new Set();
}
this.following[followerId].add(followeeId);
}
unfollow(followerId: number, followeeId: number): void {
if (followerId in this.following) {
this.following[followerId].delete(followeeId);
}
}
}TypeScript details:
- The index signatures and
Set<number>are only types; at run timetweetsandfollowingare plain objects, and their keys become strings.userId in this.tweetsworks becauseinconverts the number to a string key. new Set()without a type argument is accepted here, because the field's declared type tells the compiler what it holds.- Spreading a
Setwith...gives its values, one after another, which is whatpush(...set)needs. - The unpacked
timein the merge loop isn't used afterwards; the entry carries it only so the heap can order by it.
Complexity
postTweet,followandunfollowareO(1): an increment, a key check, a push, and a set add or delete.getNewsFeedbuildsuserswith F entries, where F is the number of people the user follows, plus the user. The heap never holds more than one entry per person, so each insert or extract isO(log F). Seeding takes at most F inserts, and the merge loop runs at most 10 times, so the total isO(F log F).- Space is
O(T + P)overall for T tweets and P follow pairs, andO(F)extra per feed call.
Edge cases and common mistakes
- An empty feed. On a new
Twitter,getNewsFeed(3)returns[]. - Following yourself. After
follow(3, 3)andpostTweet(3, 7), the feed is7, once. Without the early return, user 3 would be inuserstwice and tweet 7 would appear twice. - Unfollow then follow before any post.
unfollow(3, 4)on someone you don't follow changes nothing. Afterfollow(3, 4)and user 4 posting tweet 8, user 3's feed is8 7. - Ordering by tweet id. Ids are arbitrary, so the clock is what orders tweets.
- Pushing every tweet into the heap. Only one tweet per person goes in at first; an older tweet enters only after the newer one is taken. This keeps the work independent of the number of tweets.
- Forgetting users who never posted. Without the
user in this.tweetscheck, readingthis.tweets[user].lengthwould fail for a user with no array.
