What happens if you sorting all tweets every time in getnewsfeed?

Leads to timeouts or slow responses on large inputs Fix: Use a heap to merge sorted tweet lists instead of sorting all tweets

What happens if you not including user's own tweets in their news feed?

User's own tweets never appear in their feed, failing correctness Fix: Always add userId to the set of users considered in getNewsFeed

Interview Prepcustom-data-structuresmediumAmazonGoogle

Design Twitter (Top K Recent Tweets)

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumDESIGNAmazonGoogle

Imagine building a mini Twitter where users can post tweets and see the most recent tweets from people they follow. How do you efficiently retrieve the top K recent tweets?

💡 This is a design problem that requires managing multiple users' tweet streams and efficiently merging them to get the most recent tweets. Beginners often struggle with how to combine multiple sorted lists efficiently and how to design data structures that support fast updates and queries.

📋

Problem Statement

Design a simplified version of Twitter where users can post tweets, follow/unfollow other users, and retrieve the 10 most recent tweets in their news feed. Each tweet has a unique ID and a timestamp. Implement the following methods: - postTweet(userId, tweetId): Compose a new tweet. - getNewsFeed(userId): Retrieve the 10 most recent tweet IDs in the user's news feed. Tweets must be ordered from most recent to least recent. - follow(followerId, followeeId): Follower follows a followee. - unfollow(followerId, followeeId): Follower unfollows a followee. Assume all tweets are timestamped in the order they are posted.

1 ≤ userId, followerId, followeeId ≤ 10^5Tweet IDs are unique integersAt most 10^5 calls will be made to all methodsEach user can follow at most 10^4 usersgetNewsFeed returns up to 10 tweets

💡

Example

Input"postTweet(1, 5)\ngetNewsFeed(1)"

Output[5]

User 1 posts a tweet with ID 5. Their news feed returns this tweet.

Input"postTweet(1, 5)\nfollow(1, 2)\npostTweet(2, 6)\ngetNewsFeed(1)"

Output[6, 5]

User 1 follows user 2. User 2 posts tweet 6. User 1's news feed shows tweets 6 and 5 in order.

User follows no one and has no tweets → getNewsFeed returns empty list
User follows themselves only → getNewsFeed returns their own tweets
User unfollows someone they do not follow → no effect
Multiple tweets posted at the same timestamp → order by posting sequence

⚠️

Common Mistakes

Sorting all tweets every time in getNewsFeed

Leads to timeouts or slow responses on large inputs

✅ Use a heap to merge sorted tweet lists instead of sorting all tweets

Not including user's own tweets in their news feed

User's own tweets never appear in their feed, failing correctness

✅ Always add userId to the set of users considered in getNewsFeed

Allowing a user to follow themselves multiple times or unfollow themselves

Can cause inconsistent data or errors

✅ Prevent self-follow or ignore unfollow if followerId == followeeId

Using inefficient data structures like arrays for frequent insertions at head

PostTweet becomes O(n) instead of O(1), slowing down the system

✅ Use linked lists or data structures supporting O(1) head insertion

Not handling empty followee lists or missing users gracefully

Code throws exceptions or returns wrong results

✅ Use safe lookups and default empty sets/lists

🧠

Brute Force (Scan All Tweets Each Time)

💡 This approach exists to establish a baseline understanding by directly scanning all tweets from followed users every time we need the news feed. It is simple but inefficient, highlighting why better data structures are needed.

Intuition

For each getNewsFeed call, gather all tweets from the user and their followees, then sort them by timestamp to pick the top 10 most recent tweets.

Algorithm

Maintain a map from userId to list of their tweets (each tweet has a timestamp).
Maintain a map from userId to set of followees.
To getNewsFeed(userId), collect all tweets from userId and their followees.
Sort all collected tweets by timestamp descending and return the top 10 tweet IDs.

💡 The main challenge is realizing that scanning and sorting all tweets every time is expensive and will not scale.

</>

Code

import heapq

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = {}  # userId -> list of (time, tweetId)
        self.followees = {}  # userId -> set of followeeIds

    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:
        users = self.followees.get(userId, set()).copy()
        users.add(userId)
        all_tweets = []
        for u in users:
            if u in self.tweets:
                all_tweets.extend(self.tweets[u])
        all_tweets.sort(key=lambda x: x[0], reverse=True)
        return [tweetId for _, tweetId in all_tweets[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId not in self.followees:
            self.followees[followerId] = set()
        self.followees[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followerId in self.followees:
            self.followees[followerId].discard(followeeId)

# Driver code
if __name__ == '__main__':
    twitter = Twitter()
    twitter.postTweet(1, 5)
    print(twitter.getNewsFeed(1))  # [5]
    twitter.follow(1, 2)
    twitter.postTweet(2, 6)
    print(twitter.getNewsFeed(1))  # [6, 5]

Line Notes

self.time = 0Initialize global timestamp to order tweets chronologically

self.tweets = {}Store tweets per user for direct access

self.followees = {}Track who each user follows

self.time += 1Increment timestamp on each new tweet to maintain order

self.tweets[userId].append((self.time, tweetId))Add tweet with timestamp to user's tweet list

users = self.followees.get(userId, set()).copy()Get all followees of user safely

users.add(userId)Include user's own tweets in news feed

all_tweets.extend(self.tweets[u])Collect all tweets from each followed user

all_tweets.sort(key=lambda x: x[0], reverse=True)Sort tweets by timestamp descending to get recent first

return [tweetId for _, tweetId in all_tweets[:10]]Return top 10 tweet IDs

self.followees[followerId].add(followeeId)Add followee to follower's followee set

self.followees[followerId].discard(followeeId)Remove followee if exists, no error if not

import java.util.*;

class Twitter {
    private static int time = 0;
    private Map<Integer, List<int[]>> tweets; // userId -> list of [time, tweetId]
    private Map<Integer, Set<Integer>> followees; // userId -> set of followees

    public Twitter() {
        tweets = new HashMap<>();
        followees = new HashMap<>();
    }

    public void postTweet(int userId, int tweetId) {
        time++;
        tweets.putIfAbsent(userId, new ArrayList<>());
        tweets.get(userId).add(new int[]{time, tweetId});
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> users = new HashSet<>();
        if (followees.containsKey(userId)) {
            users.addAll(followees.get(userId));
        }
        users.add(userId);
        List<int[]> allTweets = new ArrayList<>();
        for (int u : users) {
            if (tweets.containsKey(u)) {
                allTweets.addAll(tweets.get(u));
            }
        }
        allTweets.sort((a, b) -> b[0] - a[0]);
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < Math.min(10, allTweets.size()); i++) {
            res.add(allTweets.get(i)[1]);
        }
        return res;
    }

    public void follow(int followerId, int followeeId) {
        followees.putIfAbsent(followerId, new HashSet<>());
        followees.get(followerId).add(followeeId);
    }

    public void unfollow(int followerId, int followeeId) {
        if (followees.containsKey(followerId)) {
            followees.get(followerId).remove(followeeId);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Twitter twitter = new Twitter();
        twitter.postTweet(1, 5);
        System.out.println(twitter.getNewsFeed(1)); // [5]
        twitter.follow(1, 2);
        twitter.postTweet(2, 6);
        System.out.println(twitter.getNewsFeed(1)); // [6, 5]
    }
}

Line Notes

private static int time = 0;Global timestamp to order tweets

tweets = new HashMap<>();Map user to their tweets

followees = new HashMap<>();Map user to their followees

time++;Increment timestamp on each tweet

tweets.putIfAbsent(userId, new ArrayList<>());Initialize tweet list if missing

allTweets.sort((a, b) -> b[0] - a[0]);Sort tweets descending by timestamp

users.add(userId);Include user's own tweets

followees.putIfAbsent(followerId, new HashSet<>());Initialize followee set if missing

followees.get(followerId).add(followeeId);Add followee

followees.get(followerId).remove(followeeId);Remove followee if exists

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Twitter {
    int time;
    unordered_map<int, vector<pair<int,int>>> tweets; // userId -> vector of (time, tweetId)
    unordered_map<int, unordered_set<int>> followees; // userId -> set of followees
public:
    Twitter() {
        time = 0;
    }

    void postTweet(int userId, int tweetId) {
        time++;
        tweets[userId].push_back({time, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
        unordered_set<int> users;
        if (followees.count(userId)) {
            users = followees[userId];
        }
        users.insert(userId);
        vector<pair<int,int>> allTweets;
        for (int u : users) {
            if (tweets.count(u)) {
                allTweets.insert(allTweets.end(), tweets[u].begin(), tweets[u].end());
            }
        }
        sort(allTweets.begin(), allTweets.end(), [](auto &a, auto &b) {
            return a.first > b.first;
        });
        vector<int> res;
        for (int i = 0; i < (int)min(10, (int)allTweets.size()); i++) {
            res.push_back(allTweets[i].second);
        }
        return res;
    }

    void follow(int followerId, int followeeId) {
        followees[followerId].insert(followeeId);
    }

    void unfollow(int followerId, int followeeId) {
        if (followees.count(followerId)) {
            followees[followerId].erase(followeeId);
        }
    }
};

// Driver code
int main() {
    Twitter twitter;
    twitter.postTweet(1, 5);
    vector<int> feed1 = twitter.getNewsFeed(1);
    for (int id : feed1) cout << id << " ";
    cout << endl; // 5
    twitter.follow(1, 2);
    twitter.postTweet(2, 6);
    vector<int> feed2 = twitter.getNewsFeed(1);
    for (int id : feed2) cout << id << " ";
    cout << endl; // 6 5
    return 0;
}

Line Notes

int time;Global timestamp to order tweets

unordered_map<int, vector<pair<int,int>>> tweets;Store tweets per user

unordered_map<int, unordered_set<int>> followees;Track followees per user

time++;Increment timestamp on each tweet

tweets[userId].push_back({time, tweetId});Add tweet with timestamp

users.insert(userId);Include user's own tweets

allTweets.insert(allTweets.end(), tweets[u].begin(), tweets[u].end());Collect tweets from each followed user

sort(allTweets.begin(), allTweets.end(), ...Sort tweets descending by timestamp

followees[followerId].insert(followeeId);Add followee

followees[followerId].erase(followeeId);Remove followee if exists

class Twitter {
    constructor() {
        this.time = 0;
        this.tweets = new Map(); // userId -> array of [time, tweetId]
        this.followees = new Map(); // userId -> set of followees
    }

    postTweet(userId, tweetId) {
        this.time++;
        if (!this.tweets.has(userId)) {
            this.tweets.set(userId, []);
        }
        this.tweets.get(userId).push([this.time, tweetId]);
    }

    getNewsFeed(userId) {
        const users = new Set();
        if (this.followees.has(userId)) {
            for (const f of this.followees.get(userId)) {
                users.add(f);
            }
        }
        users.add(userId);
        let allTweets = [];
        for (const u of users) {
            if (this.tweets.has(u)) {
                allTweets = allTweets.concat(this.tweets.get(u));
            }
        }
        allTweets.sort((a, b) => b[0] - a[0]);
        return allTweets.slice(0, 10).map(x => x[1]);
    }

    follow(followerId, followeeId) {
        if (!this.followees.has(followerId)) {
            this.followees.set(followerId, new Set());
        }
        this.followees.get(followerId).add(followeeId);
    }

    unfollow(followerId, followeeId) {
        if (this.followees.has(followerId)) {
            this.followees.get(followerId).delete(followeeId);
        }
    }
}

// Driver code
const twitter = new Twitter();
twitter.postTweet(1, 5);
console.log(twitter.getNewsFeed(1)); // [5]
twitter.follow(1, 2);
twitter.postTweet(2, 6);
console.log(twitter.getNewsFeed(1)); // [6, 5]

Line Notes

this.time = 0;Global timestamp to order tweets

this.tweets = new Map();Map user to their tweets

this.followees = new Map();Map user to their followees

this.time++;Increment timestamp on each tweet

this.tweets.get(userId).push([this.time, tweetId]);Add tweet with timestamp

const users = new Set();Collect all users to consider for news feed

users.add(userId);Include user's own tweets

allTweets.sort((a, b) => b[0] - a[0]);Sort tweets descending by timestamp

this.followees.get(followerId).add(followeeId);Add followee

this.followees.get(followerId).delete(followeeId);Remove followee if exists

⏱

Complexity

TimeO(F * T log (F * T)) where F is number of followees + 1, T is average tweets per user

SpaceO(U + T) where U is number of users and T total tweets stored

Each getNewsFeed collects all tweets from followed users and sorts them, which is expensive when many tweets exist.

💡 If a user follows 1000 users each with 100 tweets, sorting 100,000 tweets each time is very slow.

Interview Verdict: TLE / Inefficient for large inputs

This approach is too slow for large data but helps understand the problem and motivates better solutions.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(FT log (FT))`	`O(U + T)`	No	N/A	Mention only - never code
2. Heap-based K-way Merge	`O(k log F)`	`O(F)`	No	N/A	Good to code if linked list not required
3. Linked List + Heap (Optimal)	`O(k log F)`	`O(F + U)`	No	N/A	Best approach to code in interviews

Practice

(1/5)

1. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call? Operations: insert(1), insert(1), insert(2), remove(1), getRandom()

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = null
        self.next = null

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(null)
        self.tail = Node(null)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        if val not in self.idx_map:
            self.idx_map[val] = set()
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or not self.idx_map[val]:
            return false
        remove_idx = self.idx_map[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        if not self.idx_map[val]:
            del self.idx_map[val]
        return true

    def getRandom(self) -> int:
        return random.choice(self.nums)

rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()

easy

A. Either 1 or 2 but 1 is twice as likely

B. 2

C. Either 1 or 2 with equal probability

D. 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace insertions

Step 2: Trace removal of one 1

Step 3: Analyze getRandom probabilities

Final Answer:

Quick Check:

Solution

Step 1: Trace first iterations of the merge loop

Step 2: Next iterations and final merge

Final Answer:

Quick Check:

Solution

Step 1: Identify erase steps

Step 2: Check for level adjustment

Final Answer:

Quick Check:

Solution

Step 1: Analyze data structures used

Step 2: Consider operations in put

Final Answer:

Quick Check:

Solution

Step 1: Understand impact of negative heights

Step 2: Modify merge logic accordingly

Step 3: Evaluate other options

Final Answer:

Quick Check:

Ready to prove it?