LeetEye LeetEye
Hard Heap / Priority Queue ~5 min

Design Twitter

heap design-twitter

Problem

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in the user's news feed.

Implement the Twitter class:
- Twitter() Initializes your twitter object.
- void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
- List getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themselves. Tweets must be ordered from most recent to least recent.
- void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
- void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

Examples

Example 1
Input: ["Twitter", "postTweet", "getNewsFeed", "follow", "getNewsFeed", "unfollow", "getNewsFeed"]
Output: [null, null, [5], null, [6, 5], null, [5]]
Key Insight

NewsFeed = merge k sorted lists (each user's tweets are time-ordered).

Merge k sorted tweet lists using heap. Each user's tweets are time-ordered. Heap holds one 'pointer' per user, extracting top 10.

How to Approach This Problem

Pattern Recognition: When you see keywords like design twitter heap, think Heap / Priority Queue.

Step-by-Step Reasoning

1 Each user's tweets should be stored as:
Answer: List ordered by time
Need to retrieve by recency. Newest first (or append and iterate backwards).
2 User's followees should be stored as:
Answer: Set
Need O(1) add, remove, and lookup. Set provides all three.
3 To get 10 most recent from k users:
Answer: Use heap to merge k sorted lists
Merge k sorted lists is the classic heap problem. O(k log k) for 10 items.
4 For merging k tweet lists to get most recent:
Answer: Max-heap
We want the most recent (largest timestamp). Max-heap by timestamp.
5 Getting 10 tweets from k followed users:
Answer: O(k log k) for 10 items = O(k log k)
Initialize heap with k users' latest tweets: O(k). Extract 10: O(10 log k).

Solution

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)  # userId -> [(time, tweetId)]
        self.following = defaultdict(set)  # userId -> set of followeeIds
    
    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweets[userId].append((self.time, tweetId))
        self.time += 1
    
    def getNewsFeed(self, userId: int) -> List[int]:
        # Get tweets from user and all followees
        heap = []
        users = self.following[userId] | {userId}
        
        for uid in users:
            if self.tweets[uid]:
                idx = len(self.tweets[uid]) - 1
                time, tweetId = self.tweets[uid][idx]
                heap.append((-time, tweetId, uid, idx))
        
        heapq.heapify(heap)
        result = []
        
        while heap and len(result) < 10:
            _, tweetId, uid, idx = heapq.heappop(heap)
            result.append(tweetId)
            
            if idx > 0:
                time, tweetId = self.tweets[uid][idx - 1]
                heapq.heappush(heap, (-time, tweetId, uid, idx - 1))
        
        return result
    
    def follow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].add(followeeId)
    
    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

Complexity Analysis

Time O(k log k) for getNewsFeed
Space O(users + tweets)

Master This Pattern

Build intuition with interactive MCQs. Practice Heap / Priority Queue problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye