Problem overview
The class Twitter models a tiny social feed with four operations:
postTweet(userId, tweetId)records a new tweet. Every call posts later than all the calls before it.getNewsFeed(userId)returns the ids of the 10 most recent tweets written by the user and by the people the user follows, newest first. A shorter feed returns all its tweets, and an empty feed returns an empty list.follow(followerId, followeeId)andunfollow(followerId, followeeId)change who sees whose tweets.
Following goes one way. If user 1 follows user 2, user 1 sees user 2's tweets, old and new, but user 2 does not see user 1's. Following someone twice, following yourself and unfollowing someone you don't follow all change nothing, and your own tweets are always in your feed.
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 unfollow(1, 2) it is [5] again.
Approach: merge sorted lists with a heap
The simple approach keeps all tweets in one list. To build a feed, it scans every tweet ever posted, keeps those whose author is in the user's group, sorts them by time and takes 10. That costs time that grows with every tweet in the system, even if the user follows only two quiet people.
A better design keeps each user's tweets in their own list. Because the clock only goes up, each list is already sorted from oldest to newest, with no sorting needed. A feed is then a merge of a few sorted lists, and only the 10 newest tweets matter. The newest overall tweet is the newest tweet of one of the people involved, so the merge starts with just one candidate per person. Taking the newest candidate and replacing it with that same person's next older tweet gives the next newest overall, and so on, at most 10 times. A max-heap on time holds the candidates.
The stated costs are 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 heap holds at most one entry per person, so each push and pop costs O(log F), and a feed does at most F pushes at the start and 10 more pops and pushes after that.
Step by step
- In
__init__, setself.timeto 0. This global clock counts every tweet ever posted. Tweet ids can't serve as the clock, because an id says nothing about when the tweet was posted. - Set
self.tweetsto an empty dictionary: for each user id, a list of(time, tweetId)pairs, oldest first. A user gets a list on their first tweet. - Set
self.followingto an empty dictionary: for each user id, the set of ids that user follows. A set ignores a second follow of the same person. - In
postTweet, add 1 toself.time, so each tweet has a unique, larger time than the one before. - If the user has no list yet, create an empty one.
- Append
(self.time, tweetId). Times only grow, so the list stays sorted and the newest tweet is at the end. - In
getNewsFeed, start a listuserswithuserId, then extend it with everyone the user follows, if anyone.follownever stores a user as following themselves, so nobody appears twice. - Build the heap
newest. For each person who has posted, push one entry(-time, user, index): the time of their newest tweet with a minus sign, the person, and the position of that tweet in their list.heapqis a min-heap, so negating the time puts the newest tweet on top. - Create
feed, an empty list. Loop whilenewestisn't empty andfeedhas fewer than 10 ids. - Pop the top entry, unpack it into
_,userandindex, and append that tweet's id tofeed. The time has done its job, so it goes into_. - If the person has an older tweet (
index > 0), push it the same way, withindex - 1. That tweet is now their newest not yet shown. - Return
feed. - In
follow, return at once if the two ids are equal. Otherwise create the follower's set if needed and add the followee. - In
unfollow, if the follower has a set, calldiscardon it. Unlikeremove,discarddoes nothing when the value is missing, so unfollowing a stranger is harmless. The followee's tweets stay stored; they are just no longer collected.
The solution in Python
class Twitter:
def __init__(self):
self.time = 0
self.tweets = {}
self.following = {}
def postTweet(self, userId: int, tweetId: int) -> None:
self.time += 1
if userId not in self.tweets:
self.tweets[userId] = []
self.tweets[userId].append((self.time, tweetId))
def getNewsFeed(self, userId: int) -> List[int]:
users = [userId]
if userId in self.following:
users.extend(self.following[userId])
newest = []
for user in users:
if user in self.tweets:
index = len(self.tweets[user]) - 1
heapq.heappush(newest, (-self.tweets[user][index][0], user, index))
feed = []
while newest and len(feed) < 10:
_, user, index = heapq.heappop(newest)
feed.append(self.tweets[user][index][1])
if index > 0:
heapq.heappush(newest, (-self.tweets[user][index - 1][0], user, index - 1))
return feed
def follow(self, followerId: int, followeeId: int) -> None:
if followerId == followeeId:
return
if followerId not in self.following:
self.following[followerId] = set()
self.following[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
if followerId in self.following:
self.following[followerId].discard(followeeId)
To see the merge at work, let user 1 follow user 2, and let them post four tweets in turn:
t = Twitter()
t.follow(1, 2)
t.postTweet(1, 10)
t.postTweet(2, 20)
t.postTweet(2, 21)
t.postTweet(1, 11)
print(t.tweets)
print(t.following)
print(t.getNewsFeed(1))
{1: [(1, 10), (4, 11)], 2: [(2, 20), (3, 21)]}
{1: {2}}
[11, 21, 20, 10]
Each list is sorted by time. The heap starts with the newest tweet of each person, 11 (time 4) and 21 (time 3). Popping 11 pushes user 1's older tweet 10. The next pop is 21, which pushes 20. Then 20 comes out, and then 10.
Python details worth knowing:
- Heap entries are tuples, and tuples compare element by element. The times are all different, so the comparison is always settled by the first element; the user and the index just travel along to say where the tweet is.
set()makes an empty set.{}would be an empty dictionary.users.extend(a_set)appends every element of the set. Sets have no order, which doesn't matter here because the heap orders the tweets.- The lesson's editor already has
heapqandListavailable. In a file of your own, addimport heapqandfrom typing import List.
Complexity
Time: postTweet, follow and unfollow are a few dictionary and set operations, so O(1) on average. getNewsFeed pushes at most one entry per person, F + 1 in all, and then does at most 10 pop-and-push rounds on a heap of at most F + 1 entries. That gives O(F log F), and it does not depend on how many tweets exist.
Space: the object stores every tweet once and every follow relation once. A feed needs O(F) extra space for the heap and at most 10 ids for the result.
Edge cases and common mistakes
- An empty feed. If nobody in the group has posted, the heap stays empty and the result is
[]. - Following yourself. Storing it would put the user in
userstwice and show each of their tweets twice. The early return infollowprevents it. - Following before posting. The followee has no list yet, so the loop skips them. After they post, their tweets show up in the feed.
- Using tweet ids as time. The ids don't say which tweet is newer. In the lesson's second example tweet 106 is newer than tweet 201.
- More than 10 tweets. The loop stops once the feed holds 10 ids.
- Unfollowing someone you don't follow.
discardmakes it a no-op, whileremovewould raise aKeyError.
Testing
Two users post six tweets each, taking turns, and user 1 follows user 2:
t2 = Twitter()
t2.follow(1, 2)
for i in range(1, 7):
t2.postTweet(1, 100 + i)
t2.postTweet(2, 200 + i)
print(t2.getNewsFeed(1))
print(t2.getNewsFeed(2))
[206, 106, 205, 105, 204, 104, 203, 103, 202, 102]
[206, 205, 204, 203, 202, 201]
User 1's feed holds 12 tweets and shows the newest 10. User 2 does not follow user 1, so their feed holds only their own six.
The special cases, on a fresh object:
t3 = Twitter()
print(t3.getNewsFeed(3))
t3.follow(3, 3)
t3.postTweet(3, 7)
print(t3.getNewsFeed(3), t3.following)
t3.unfollow(3, 4)
t3.follow(3, 4)
t3.postTweet(4, 8)
print(t3.getNewsFeed(3))
[]
[7] {}
[8, 7]
Following yourself stores nothing, the tweet appears once, and user 3 sees user 4's tweet even though they followed before it was posted.
