Design Twitter

The machine must model a miniature Twitter: users post tweets with global monotonically increasing ids, users follow and unfollow each other, and getNewsFeed(userId) returns the 10 most recent tweet ids from the user plus everyone they follow, newest first.

Three structures carry the state. A user → set-of-followees map holds the follow graph; a user → list-of-tweet-ids map holds each user's stream in post order; a global counter issues tweet ids so recency is comparable across users. getNewsFeed gathers the followees' streams plus the user's own, takes the last 10 tweets of each (older entries can never make the top 10), and runs a k-way merge with a max-heap keyed by tweet id. Pop 10 times, or until the heap empties; tweets come out newest-first.

The merge is the trickiest part. Each stream is consumed newest to oldest, so the machine pushes (tweet_id, stream_index, position) and, on each pop, pushes the next-older tweet from the same stream. Duplicate tweets are impossible — every tweet id is unique — so no dedup is needed. follow/unfollow are O(1) set operations; postTweet is O(1) append; getNewsFeed is O(f log f) for f followees, bounded by 10 × f heap pushes.

Edge cases: a user with no followees — the feed is just their own stream. Unfollowing someone never followed is a no-op. The feed must be strictly newest-first, so tweet ids must be globally ordered, never per-user counters.

import heapq
 
class Twitter:
    def __init__(self):
        self.following = defaultdict(set)
        self.tweets = defaultdict(list)
        self.time = 0
 
    def postTweet(self, userId, tweetId):
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1
 
    def getNewsFeed(self, userId):
        users = self.following[userId] | {userId}
        heap = []
        for u in users:
            if not self.tweets[u]: continue
            t, tid = self.tweets[u][-1]
            heap.append((-t, tid, u, len(self.tweets[u]) - 1))
        heapq.heapify(heap)
        feed = []
        while heap and len(feed) < 10:
            neg_t, tid, u, i = heapq.heappop(heap)
            feed.append(tid)
            if i > 0:
                t, ptid = self.tweets[u][i - 1]
                heapq.heappush(heap, (-t, ptid, u, i - 1))
        return feed