Problem overview
The lesson asks for a small social network. 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.
The Twitter struct has five parts: Constructor creates an empty one, PostTweet(userId, tweetId) posts a tweet, GetNewsFeed(userId) returns up to 10 tweet ids, newest first, Follow(followerId, followeeId) starts following and Unfollow(followerId, followeeId) stops. Following goes one way: if user 1 follows user 2, user 1 sees user 2's tweets, old and new, but not the other way round. Following someone twice, following yourself, and unfollowing someone you don't follow all change nothing, and your own tweets are always in your feed.
In the first example, user 1 posts tweet 5, so the feed is [5]. User 1 follows user 2, who posts tweet 6. The feed is now [6 5], because 6 is newer. After the unfollow it is [5] again.
Approach: merge the users' lists with a heap
Collecting every tweet of everyone in the feed and sorting them works, but its cost grows with every tweet ever posted, even though only 10 are shown. The statement asks for O(1) for PostTweet, Follow and Unfollow, and O(F log F) for GetNewsFeed, where F is the number of people the user follows.
The data is arranged to make that possible:
- A global clock counts every tweet ever posted, so a newer tweet always has a bigger time. Tweet ids can't tell which tweet is newer (in the second example tweet 106 is newer than 201), but the clock can.
- Each user has a list of tweets, oldest first. Because the clock only grows, appending keeps each list sorted, and the newest tweet is at the end.
- Each user has a set of the people they follow.
The feed is then a merge of several sorted lists, the same idea as merging sorted linked lists. A max-heap holds one candidate per person: that person's newest tweet not yet shown. The top of the heap is the newest tweet overall. Take it, add it to the feed, and push the same person's previous tweet in its place. After at most 10 rounds the feed is done. An older tweet of a person can't be in the feed before their newer one, so one entry per person is enough, and the heap never holds more than F + 1 entries.
The lesson provides the maxHeap type for container/heap. Its entries are slices of ints ordered by their first number, biggest on top.
Step by step
- Declare the clock
timeas anint. - Declare
tweetsas amap[int][][]int: for each user id, a list of tweets, each a[]intholding its time and its id. - Declare
followingas amap[int]map[int]bool. Go has no set type, so a map withtruevalues plays the role of a set: adding twice changes nothing, and adding and removing areO(1). - Make both maps in
Constructor. Storing into a nil map stops the program, so they must be created first.timestarts at 0. - In
PostTweet, advance the clock withthis.time++, so every tweet has its own time. - Append
[]int{this.time, tweetId}to the user's list and store the result back. A missing key reads as a nil slice, andappendworks on nil. - In
GetNewsFeed, startusersas a slice holdinguserId, because your own tweets are always in your feed. - Add the followees with a
rangeloop overthis.following[userId]. Ranging over a map with one variable gives its keys, and over a nil map it gives nothing.Follownever stores a user following themselves, so nobody is inuserstwice. - Create the heap
newestas&maxHeap{}. Each entry is[]int{time, user, index}: the tweet's time, its author and its position in that author's list. - Push each author's newest tweet. For every user who has posted, the newest tweet is at the last index,
len(this.tweets[user]) - 1. Users who never posted have nothing to show. - Loop while the heap isn't empty and
feedhas fewer than 10 ids. Aforwith only a condition is Go'swhile. - Pop the top entry with
heap.Pop(newest)and convert it with.([]int), becauseheap.Popreturns anany. - Read the user and the index from the entry and append that tweet's id to
feed. Tweets come out newest first, so the order is right. - If the user has an older tweet (
index > 0), push it: its time, the user andindex - 1. - Return
feed. Followreturns at once when both ids are equal, makes the inner map if it is nil, and sets the entry totrue.Unfollowcallsdelete, which does nothing when the key or the whole map is missing.
The solution in Go
type Twitter struct {
time int
tweets map[int][][]int
following map[int]map[int]bool
}
func Constructor() Twitter {
return Twitter{tweets: map[int][][]int{}, following: map[int]map[int]bool{}}
}
func (this *Twitter) PostTweet(userId int, tweetId int) {
this.time++
this.tweets[userId] = append(this.tweets[userId], []int{this.time, tweetId})
}
func (this *Twitter) GetNewsFeed(userId int) []int {
users := []int{userId}
for followee := range this.following[userId] {
users = append(users, followee)
}
newest := &maxHeap{}
for _, user := range users {
if len(this.tweets[user]) > 0 {
index := len(this.tweets[user]) - 1
heap.Push(newest, []int{this.tweets[user][index][0], user, index})
}
}
feed := []int{}
for newest.Len() > 0 && len(feed) < 10 {
top := heap.Pop(newest).([]int)
user, index := top[1], top[2]
feed = append(feed, this.tweets[user][index][1])
if index > 0 {
heap.Push(newest, []int{this.tweets[user][index-1][0], user, index - 1})
}
}
return feed
}
func (this *Twitter) Follow(followerId int, followeeId int) {
if followerId == followeeId {
return
}
if this.following[followerId] == nil {
this.following[followerId] = map[int]bool{}
}
this.following[followerId][followeeId] = true
}
func (this *Twitter) Unfollow(followerId int, followeeId int) {
delete(this.following[followerId], followeeId)
}
The Go details worth a closer look:
- Map iteration order is random. The order of
userschanges from run to run. That is harmless, because the heap orders the tweets by time, and every tweet has a different time. - Nil maps. Reading from a nil map is safe and gives the zero value, so
this.tweets[user]for a user who never posted is a nil slice of length 0. Writing to a nil map stops the program, which is whyFollowcreates the inner map before storing in it. deleteon a missing map or key does nothing, soUnfollowneeds no checks.- Type assertion.
heap.Pop(newest).([]int)asserts that theanyvalue holds a[]int. It would panic on any other type. - Empty feeds.
feed := []int{}is an empty, non-nil slice, so an empty feed is returned as[].
Complexity
Time. PostTweet, Follow and Unfollow are O(1) on average: a counter step, an append and a few map operations. GetNewsFeed builds the list of F + 1 users, pushes up to F + 1 entries and then runs at most 10 rounds of one pop and one push. The heap never holds more than F + 1 entries, so the call takes O(F log F), however many tweets exist.
Space. The tweets take O(T) for T tweets posted, plus the follow sets. A feed call needs O(F) extra space for the heap.
Edge cases and common mistakes
- Using the tweet id as the time. Ids are unrelated to age. In the second example, tweet 201 is older than tweet 106 although its id is bigger; only the clock gives the order.
- An empty feed. Before anyone posts,
GetNewsFeed(3)returns[]. - Following yourself. After
Follow(3, 3)andPostTweet(3, 7), the feed is[7], with tweet 7 once. Storing the self-follow would put user 3 inuserstwice and show the tweet twice. - Following someone before they post. After
Follow(3, 4)and thenPostTweet(4, 8), the feed is[8 7]. Following is stored as a relationship, not as a copy of tweets. - Following twice. A second
Follow(3, 4)leaves one entry in the set. - Pushing every tweet into the heap. It works, but then the heap grows with all tweets of everyone in the feed. One entry per person keeps it small.
- More than 10 tweets. With 12 tweets in a feed, only the 10 newest are returned.
Testing
The first example, run on a new Twitter:
[5]
[6 5]
[5]
Users 1 and 2 each post six tweets, taking turns (101 to 106 and 201 to 206), and user 1 follows user 2. User 1's feed is [206 106 205 105 204 104 203 103 202 102]: 12 tweets exist and the two oldest are cut. User 2 follows nobody, so user 2's feed is [206 205 204 203 202 201].
Starting from a new Twitter, GetNewsFeed(3) gives []. Then Follow(3, 3) and PostTweet(3, 7) give [7], then Unfollow(3, 4), Follow(3, 4) and Follow(3, 4) again still give [7] with one followee stored. After PostTweet(4, 8) the feed is [8 7].
