Design Twitter
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Design a mini Twitter: postTweet, follow, unfollow and getNewsFeed (the 10 most recent tweets from you and the people you follow).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What do you need to compare to know which tweet is newer?
- Hint 2How many tweets of one person can possibly appear in a feed of 10?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A noticeboard per person where they pin their posts, each stamped with a running clock number. To build your feed you glance at the latest 10 pins on the boards of everyone you follow (and your own), put those together, and keep the 10 with the biggest clock numbers. Following someone just means adding their name to your list of boards to glance at.
- The obvious way
Collect all tweets of all followees and sort: O(total tweets log total).
- The key insight
Keep a clock that increases with every post, a list of (time, tweetId) per user, and a set of followees per user. For the feed, take the last 10 tweets of the user and each followee, pick the 10 with the largest time. follow/unfollow just edit the set.
- The algorithm
- clock + 1 on every post; store (clock, tweet).
- follow adds to the set; unfollow removes (a user never unfollows itself).
- Feed: gather the last 10 tweets of yourself and your followees.
- Return the 10 newest, newest first.
Watch it run
Examplepost(1,5); feed(1); follow(1,2); post(2,6); feed(1); unfollow(1,2); feed(1)
User 1 posts tweet 5 (time 1). Their feed: [5].
feed(1) = [5]
Where people slip
- Use a global counter for time, not the tweet id (ids need not increase).
- The user sees their own tweets even with no followees.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class Twitter:
def __init__(self):
self.clock = 0 # grows with every post
self.posts = {} # user -> [(time, tweet id), ...] oldest first
self.following = {} # user -> set of people they follow
def postTweet(self, userId, tweetId):
self.clock += 1
self.posts.setdefault(userId, []).append((self.clock, tweetId))
def getNewsFeed(self, userId):
boards = self.following.get(userId, set()) | {userId} # whose boards to glance at
recent = []
for person in boards:
recent.extend(self.posts.get(person, [])[-10:]) # only their latest 10 can matter
recent.sort(reverse=True) # biggest clock number first
return [tweet_id for _, tweet_id in recent[:10]]
def follow(self, followerId, followeeId):
self.following.setdefault(followerId, set()).add(followeeId)
def unfollow(self, followerId, followeeId):
self.following.get(followerId, set()).discard(followeeId)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.