Design Twitter (Top K Recent Tweets)

🎯

Design Twitter (Top K Recent Tweets)

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

1. Maintain a map from userId to list of their tweets (each tweet has a timestamp).
2. Maintain a map from userId to set of followees.
3. To getNewsFeed(userId), collect all tweets from userId and their followees.
4. 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.

🧠

Better Approach (Use Max Heap for K-Way Merge)

💡 This approach improves efficiency by merging the tweet lists of followed users using a max heap, avoiding sorting all tweets at once.

Intuition

Each user’s tweets are stored in descending order by timestamp. To get the news feed, we perform a k-way merge of these sorted lists using a max heap to efficiently find the next most recent tweet.

Algorithm

1. Store each user’s tweets in a linked list or array in descending order of timestamp.
2. Maintain a map of followees for each user.
3. For getNewsFeed(userId), initialize a max heap and push the most recent tweet from each followee and the user.
4. Pop from the heap to get the next most recent tweet, then push the next tweet from the same user’s list if available.
5. Repeat until 10 tweets are collected or heap is empty.

💡 The key insight is to merge sorted lists efficiently using a heap, which is faster than sorting all tweets together.

</>

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].insert(0, (self.time, tweetId))  # newest at front

    def getNewsFeed(self, userId: int) -> list:
        users = self.followees.get(userId, set()).copy()
        users.add(userId)
        heap = []  # max heap simulated by pushing negative time
        indices = {}  # userId -> current index in tweets list

        for u in users:
            if u in self.tweets and self.tweets[u]:
                indices[u] = 0
                time, tweetId = self.tweets[u][0]
                heapq.heappush(heap, (-time, tweetId, u))

        res = []
        while heap and len(res) < 10:
            neg_time, tweetId, u = heapq.heappop(heap)
            res.append(tweetId)
            indices[u] += 1
            if indices[u] < len(self.tweets[u]):
                time, nextTweetId = self.tweets[u][indices[u]]
                heapq.heappush(heap, (-time, nextTweetId, u))
        return res

    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.tweets[userId].insert(0, (self.time, tweetId))Insert newest tweet at front for descending order

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

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

heap = []Initialize max heap (using negative time)

indices = {}Track current index in each user's tweet list

heapq.heappush(heap, (-time, tweetId, u))Push most recent tweet from each user

neg_time, tweetId, u = heapq.heappop(heap)Pop tweet with max timestamp

indices[u] += 1Move to next tweet in user's list

if indices[u] < len(self.tweets[u])If more tweets exist, push next one to heap

import java.util.*;

class Twitter {
    private static int time = 0;
    private Map<Integer, LinkedList<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 LinkedList<>());
        tweets.get(userId).addFirst(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);

        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        Map<Integer, Integer> indices = new HashMap<>();

        for (int u : users) {
            if (tweets.containsKey(u) && !tweets.get(u).isEmpty()) {
                indices.put(u, 0);
                int[] tweet = tweets.get(u).get(0);
                heap.offer(new int[]{tweet[0], tweet[1], u});
            }
        }

        List<Integer> res = new ArrayList<>();
        while (!heap.isEmpty() && res.size() < 10) {
            int[] top = heap.poll();
            res.add(top[1]);
            int u = top[2];
            int idx = indices.get(u) + 1;
            if (idx < tweets.get(u).size()) {
                indices.put(u, idx);
                int[] nextTweet = tweets.get(u).get(idx);
                heap.offer(new int[]{nextTweet[0], nextTweet[1], u});
            }
        }
        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

tweets.get(userId).addFirst(new int[]{time, tweetId});Add newest tweet at front for descending order

Set<Integer> users = new HashSet<>();Collect all users to consider

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

PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);Max heap by timestamp

indices.put(u, 0);Track current index in user's tweet list

heap.offer(new int[]{tweet[0], tweet[1], u});Push most recent tweet from user

int[] top = heap.poll();Pop tweet with max timestamp

indices.put(u, idx);Update index for next tweet

heap.offer(new int[]{nextTweet[0], nextTweet[1], u});Push next tweet from same user

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

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].insert(tweets[userId].begin(), {time, tweetId});
    }

    vector<int> getNewsFeed(int userId) {
        unordered_set<int> users;
        if (followees.count(userId)) {
            users = followees[userId];
        }
        users.insert(userId);

        struct cmp {
            bool operator()(const tuple<int,int,int>& a, const tuple<int,int,int>& b) {
                return get<0>(a) < get<0>(b); // max heap by time
            }
        };

        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, cmp> heap;
        unordered_map<int,int> indices;

        for (int u : users) {
            if (tweets.count(u) && !tweets[u].empty()) {
                indices[u] = 0;
                auto& t = tweets[u][0];
                heap.emplace(t.first, t.second, u);
            }
        }

        vector<int> res;
        while (!heap.empty() && (int)res.size() < 10) {
            auto [timeStamp, tweetId, u] = heap.top(); heap.pop();
            res.push_back(tweetId);
            indices[u]++;
            if (indices[u] < (int)tweets[u].size()) {
                auto& t = tweets[u][indices[u]];
                heap.emplace(t.first, t.second, u);
            }
        }
        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

tweets[userId].insert(tweets[userId].begin(), {time, tweetId});Insert newest tweet at front for descending order

unordered_set<int> users;Collect all users to consider

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

priority_queue<tuple<int,int,int>, ...> heap;Max heap by timestamp

indices[u] = 0;Track current index in user's tweet list

heap.emplace(t.first, t.second, u);Push next tweet from same user

auto [timeStamp, tweetId, u] = heap.top();Pop tweet with max timestamp

indices[u]++;Move to next tweet

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).unshift([this.time, tweetId]); // newest at front
    }

    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);

        const heap = [];
        const indices = new Map();

        for (const u of users) {
            if (this.tweets.has(u) && this.tweets.get(u).length > 0) {
                indices.set(u, 0);
                const [time, tweetId] = this.tweets.get(u)[0];
                heap.push([-time, tweetId, u]);
            }
        }

        // Heapify
        heap.sort((a, b) => a[0] - b[0]);

        const res = [];
        while (heap.length > 0 && res.length < 10) {
            const [negTime, tweetId, u] = heap.shift();
            res.push(tweetId);
            let idx = indices.get(u) + 1;
            if (idx < this.tweets.get(u).length) {
                indices.set(u, idx);
                const [time, nextTweetId] = this.tweets.get(u)[idx];
                // Insert in sorted order to maintain min-heap
                let inserted = false;
                for (let i = 0; i < heap.length; i++) {
                    if (-time < heap[i][0]) {
                        heap.splice(i, 0, [-time, nextTweetId, u]);
                        inserted = true;
                        break;
                    }
                }
                if (!inserted) {
                    heap.push([-time, nextTweetId, u]);
                }
            }
        }
        return res;
    }

    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.tweets.get(userId).unshift([this.time, tweetId]);Add newest tweet at front for descending order

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

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

heap.push([-time, tweetId, u]);Push most recent tweet with negative time for max heap

heap.sort((a, b) => a[0] - b[0]);Heapify by sorting (inefficient but simple)

const [negTime, tweetId, u] = heap.shift();Pop tweet with max timestamp

indices.set(u, idx);Update index for next tweet

heap.splice(i, 0, [-time, nextTweetId, u]);Insert next tweet maintaining heap order

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

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

⏱

Complexity

TimeO(N log F) where N is number of tweets retrieved (up to 10) and F is number of followees + 1

SpaceO(F) for heap and indices

Heap merges k sorted lists efficiently, only processing up to 10 tweets per getNewsFeed call.

💡 This approach is much faster than brute force because it avoids sorting all tweets, only merging the top tweets from each user.

Interview Verdict: Accepted / Efficient for large inputs

This is the standard approach to implement in interviews for this problem.

🧠

Optimal Approach (Linked List + HashMap + Heap for O(1) Post and O(k log F) Feed)

💡 This approach uses linked lists to store tweets per user for O(1) insertion and a heap to merge feeds efficiently, combining data structure design with algorithmic optimization.

Intuition

Each user's tweets are stored as a linked list with newest tweet at the head. For getNewsFeed, we use a max heap to merge the heads of each followee's tweet list, popping the most recent and pushing the next tweet from that list.

Algorithm

1. Define a TweetNode class with tweetId, timestamp, and next pointer.
2. Store each user's tweets as a linked list with newest tweet at head.
3. Maintain a map of followees per user.
4. For getNewsFeed(userId), push the head of each followee's tweet list into a max heap.
5. Pop from heap to get most recent tweet, then push the next tweet from that user's list.
6. Repeat until 10 tweets are collected or heap is empty.

💡 This approach optimizes both posting and feed retrieval by using linked lists for O(1) insertion and heaps for efficient merging.

</>

Code

import heapq

class TweetNode:
    def __init__(self, tweetId, time):
        self.tweetId = tweetId
        self.time = time
        self.next = None

class Twitter:
    def __init__(self):
        self.time = 0
        self.userTweets = {}  # userId -> head of linked list of tweets
        self.followees = {}  # userId -> set of followees

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time += 1
        node = TweetNode(tweetId, self.time)
        node.next = self.userTweets.get(userId, None)
        self.userTweets[userId] = node

    def getNewsFeed(self, userId: int) -> list:
        users = self.followees.get(userId, set()).copy()
        users.add(userId)
        heap = []  # max heap by time

        for u in users:
            head = self.userTweets.get(u, None)
            if head:
                heapq.heappush(heap, (-head.time, head))

        res = []
        while heap and len(res) < 10:
            neg_time, node = heapq.heappop(heap)
            res.append(node.tweetId)
            if node.next:
                heapq.heappush(heap, (-node.next.time, node.next))
        return res

    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

class TweetNode:Define linked list node for tweets

node.next = self.userTweets.get(userId, None)Insert new tweet at head for O(1) insertion

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

heapq.heappush(heap, (-head.time, head))Push head tweet of each user into max heap

neg_time, node = heapq.heappop(heap)Pop most recent tweet

if node.next: heapq.heappush(heap, (-node.next.time, node.next))Push next tweet from same user

import java.util.*;

class Twitter {
    private static int time = 0;

    private static class TweetNode {
        int tweetId, time;
        TweetNode next;
        TweetNode(int tweetId, int time) {
            this.tweetId = tweetId;
            this.time = time;
            this.next = null;
        }
    }

    private Map<Integer, TweetNode> userTweets;
    private Map<Integer, Set<Integer>> followees;

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

    public void postTweet(int userId, int tweetId) {
        time++;
        TweetNode node = new TweetNode(tweetId, time);
        node.next = userTweets.getOrDefault(userId, null);
        userTweets.put(userId, node);
    }

    public List<Integer> getNewsFeed(int userId) {
        Set<Integer> users = new HashSet<>();
        if (followees.containsKey(userId)) {
            users.addAll(followees.get(userId));
        }
        users.add(userId);

        PriorityQueue<TweetNode> heap = new PriorityQueue<>((a, b) -> b.time - a.time);
        for (int u : users) {
            TweetNode head = userTweets.get(u);
            if (head != null) {
                heap.offer(head);
            }
        }

        List<Integer> res = new ArrayList<>();
        while (!heap.isEmpty() && res.size() < 10) {
            TweetNode node = heap.poll();
            res.add(node.tweetId);
            if (node.next != null) {
                heap.offer(node.next);
            }
        }
        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 class TweetNode {Linked list node for tweets

node.next = userTweets.getOrDefault(userId, null);Insert new tweet at head for O(1) insertion

Set<Integer> users = new HashSet<>();Collect all users to consider

PriorityQueue<TweetNode> heap = new PriorityQueue<>((a, b) -> b.time - a.time);Max heap by timestamp

heap.offer(head);Push head tweet of each user

TweetNode node = heap.poll();Pop most recent tweet

if (node.next != null) heap.offer(node.next);Push next tweet from same user

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

using namespace std;

class Twitter {
    int time;
    struct TweetNode {
        int tweetId, time;
        TweetNode* next;
        TweetNode(int tId, int t) : tweetId(tId), time(t), next(nullptr) {}
    };

    unordered_map<int, TweetNode*> userTweets;
    unordered_map<int, unordered_set<int>> followees;

public:
    Twitter() {
        time = 0;
    }

    void postTweet(int userId, int tweetId) {
        time++;
        TweetNode* node = new TweetNode(tweetId, time);
        node->next = userTweets[userId];
        userTweets[userId] = node;
    }

    vector<int> getNewsFeed(int userId) {
        unordered_set<int> users;
        if (followees.count(userId)) {
            users = followees[userId];
        }
        users.insert(userId);

        struct cmp {
            bool operator()(TweetNode* a, TweetNode* b) {
                return a->time < b->time; // max heap
            }
        };

        priority_queue<TweetNode*, vector<TweetNode*>, cmp> heap;
        for (int u : users) {
            if (userTweets.count(u) && userTweets[u] != nullptr) {
                heap.push(userTweets[u]);
            }
        }

        vector<int> res;
        while (!heap.empty() && (int)res.size() < 10) {
            TweetNode* node = heap.top(); heap.pop();
            res.push_back(node->tweetId);
            if (node->next != nullptr) {
                heap.push(node->next);
            }
        }
        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

struct TweetNode {Linked list node for tweets

node->next = userTweets[userId];Insert new tweet at head for O(1) insertion

unordered_set<int> users;Collect all users to consider

priority_queue<TweetNode*, vector<TweetNode*>, cmp> heap;Max heap by timestamp

heap.push(userTweets[u]);Push head tweet of each user

TweetNode* node = heap.top();Pop most recent tweet

if (node->next != nullptr) heap.push(node->next);Push next tweet from same user

class TweetNode {
    constructor(tweetId, time) {
        this.tweetId = tweetId;
        this.time = time;
        this.next = null;
    }
}

class Twitter {
    constructor() {
        this.time = 0;
        this.userTweets = new Map(); // userId -> head TweetNode
        this.followees = new Map(); // userId -> set of followees
    }

    postTweet(userId, tweetId) {
        this.time++;
        const node = new TweetNode(tweetId, this.time);
        node.next = this.userTweets.get(userId) || null;
        this.userTweets.set(userId, node);
    }

    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);

        const heap = [];

        for (const u of users) {
            const head = this.userTweets.get(u);
            if (head) {
                heap.push(head);
            }
        }

        // Sort heap by time descending
        heap.sort((a, b) => b.time - a.time);

        const res = [];
        while (heap.length > 0 && res.length < 10) {
            const node = heap.shift();
            res.push(node.tweetId);
            if (node.next) {
                // Insert node.next maintaining descending order
                let inserted = false;
                for (let i = 0; i < heap.length; i++) {
                    if (node.next.time > heap[i].time) {
                        heap.splice(i, 0, node.next);
                        inserted = true;
                        break;
                    }
                }
                if (!inserted) {
                    heap.push(node.next);
                }
            }
        }
        return res;
    }

    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

class TweetNode {Define linked list node for tweets

node.next = this.userTweets.get(userId) || null;Insert new tweet at head for O(1) insertion

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

heap.push(head);Push head tweet of each user

heap.sort((a, b) => b.time - a.time);Sort heap by timestamp descending

const node = heap.shift();Pop most recent tweet

if (node.next) { ... }Insert next tweet maintaining order

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

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

⏱

Complexity

TimeO(k log F) where k=10 tweets retrieved, F is number of followees + 1

SpaceO(F) for heap and O(U) for linked lists

Posting is O(1) due to linked list insertion; feed retrieval merges heads with a heap efficiently.

💡 This is the most efficient design combining fast writes and fast reads, suitable for large scale.

Interview Verdict: Accepted / Optimal

This approach is the best practice for this problem in interviews and real systems.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the optimal linked list + heap approach unless asked otherwise. Mention brute force to show understanding.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(F*T log (F*T))	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

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem requirements and constraints.Step 2: Describe the brute force approach and its inefficiencies.Step 3: Introduce the heap-based k-way merge approach for better efficiency.Step 4: Present the optimal linked list + heap design for best performance.Step 5: Code the optimal solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test: 7min. Total ~30min

What the Interviewer Tests

Interviewer tests your ability to design efficient data structures, use heaps for merging sorted streams, and handle edge cases like self-follow and empty feeds.

Common Follow-ups

• What if we want to support unlimited tweets in the feed? → Use pagination or lazy loading.
• How to optimize memory usage? → Limit stored tweets per user or use database with caching.

💡 Follow-ups test your understanding of scalability and practical system design considerations.

🔍

Pattern Recognition

When to Use

1) Need to merge multiple sorted streams efficiently, 2) Need to maintain recent items per user, 3) Need fast insertion and retrieval, 4) Problem involves social network feed design.

Signature Phrases

top K recent tweetsfollow/unfollow usersnews feedmost recent tweets

NOT This Pattern When

Problems that only require sorting or simple hash maps without merging multiple sorted streams.

Similar Problems

Design Facebook News Feed - similar feed mergingMerge K Sorted Lists - core k-way merge techniqueTop K Frequent Elements - use of heaps for top K queries

Practice

1. You need to design a stack data structure that supports the usual push and pop operations, but also an increment operation that adds a given value to the bottom k elements of the stack efficiently. Which approach guarantees the most optimal time complexity for a sequence of n operations?

easy

A. Use a balanced binary search tree to store elements and increments, allowing O(log n) updates and queries.

B. Directly increment the bottom k elements on each increment call, resulting in O(n*k) time for n operations.

C. Use a lazy increment array to record increments and propagate them during pop operations, achieving O(n) total time.

D. Maintain a prefix sum array of increments and update it on each increment call, applying increments during pop.

Solution

1. Step 1: Understand the problem constraints

   The increment operation must be efficient even when called multiple times, so directly incrementing bottom k elements each time (O(n*k)) is too slow.

2. Step 2: Recognize the lazy increment pattern

   Using an auxiliary array to store increments lazily and applying them during pop operations reduces total time to O(n), as increments are propagated only once per element.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Lazy increments avoid repeated updates, achieving O(n) total time [OK]

Hint: Lazy increments reduce repeated updates to O(n) total time [OK]

Common Mistakes:

• Directly incrementing elements each time causes TLE
• Using complex data structures unnecessarily

2. What is the time complexity of adding a number and then finding the median using the balanced two heaps approach with lazy deletion for a data stream of size n?

medium

A. O(log n) per addNum and O(log n) per findMedian

B. O(n) per addNum and O(1) per findMedian

C. O(log n) per addNum and O(1) per findMedian

D. O(1) per addNum and O(n) per findMedian

Solution

1. Step 1: Analyze addNum complexity

   Adding a number involves pushing to a heap and balancing heaps, each O(log n) operations.

2. Step 2: Analyze findMedian complexity

   Median is retrieved from the top of heaps without modification, O(1) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion is O(log n), median retrieval O(1) [OK]

Hint: Heap push/pop are O(log n), median peek is O(1) [OK]

Common Mistakes:

• Assuming sorting each query is O(log n)
• Confusing addNum with findMedian complexity

3. Consider the following buggy addRange method for the RangeModule. Which line contains the subtle bug that causes incorrect interval merging?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] > left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

medium

A. Line with condition: if i != 0 and self.intervals[self.starts[i-1]] > left:

B. Line with bisect_left call: i = bisect_left(self.starts, left)

C. Line deleting intervals: for k in self.starts[i:j]: del self.intervals[k]

D. Line updating self.starts: self.starts[i:j] = [left]

Solution

1. Step 1: Analyze the condition for merging overlapping intervals

   The condition uses > instead of >=, so intervals that exactly touch at the boundary are not merged.

2. Step 2: Consequence of the bug

   This causes fragmented intervals and incorrect query results because adjacent intervals are not merged properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using > instead of >= misses boundary merges [OK]

Hint: Check interval overlap condition carefully for off-by-one errors [OK]

Common Mistakes:

• Using strict inequality instead of inclusive for merging intervals

4. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.

medium

A. O(n²)

B. O(n)

C. O(n log n)

D. O(n * w) where w is the width of the skyline

Solution

1. Step 1: Identify divide and conquer recurrence

   The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.

2. Step 2: Solve recurrence and analyze merge cost

   Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) [OK]

Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]

Common Mistakes:

• Confusing width w with n
• Assuming quadratic due to nested loops

5. Suppose the multilevel doubly linked list can have cycles introduced via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the flattening algorithm is necessary to handle this safely?

hard

A. Use recursion with a depth limit to prevent stack overflow on cycles.

B. Remove all child pointers before flattening to guarantee acyclic structure.

C. Use a hash set to track visited nodes and skip already visited ones to avoid infinite loops.

D. No modification needed; the existing in-place iterative approach handles cycles naturally.

Solution

1. Step 1: Understand the problem with cycles

   Cycles cause infinite loops during traversal if nodes are revisited.

2. Step 2: Identify safe traversal method

   Tracking visited nodes with a hash set prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Removing child pointers loses structure; recursion depth limit is unreliable; existing code does not detect cycles.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Visited set prevents infinite loops in cyclic graphs [OK]

Hint: Track visited nodes to handle cycles safely [OK]

Common Mistakes:

• Assuming no cycles exist in input
• Relying on recursion depth limits
• Ignoring cycle detection altogether