Interview Prepcustom-data-structuresmediumAmazonGoogle

Design Twitter (Top K Recent Tweets)

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

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?

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

Edge cases: User follows no one and has no tweets → getNewsFeed returns empty listUser follows themselves only → getNewsFeed returns their own tweetsUser unfollows someone they do not follow → no effect

</>

IDE

class Twitter:
    def __init__(self):
        pass
    def postTweet(self, userId: int, tweetId: int) -> None:
        pass
    def getNewsFeed(self, userId: int) -> list:
        pass
    def follow(self, followerId: int, followeeId: int) -> None:
        pass
    def unfollow(self, followerId: int, followeeId: int) -> None:
        pass

class Twitter:
    def __init__(self):
        # Write your solution here
        pass
    def postTweet(self, userId: int, tweetId: int) -> None:
        pass
    def getNewsFeed(self, userId: int) -> list:
        pass
    def follow(self, followerId: int, followeeId: int) -> None:
        pass
    def unfollow(self, followerId: int, followeeId: int) -> None:
        pass

public class Twitter {
    public Twitter() {
        // Write your solution here
    }
    public void postTweet(int userId, int tweetId) {
    }
    public List<Integer> getNewsFeed(int userId) {
        return new ArrayList<>();
    }
    public void follow(int followerId, int followeeId) {
    }
    public void unfollow(int followerId, int followeeId) {
    }
}

class Twitter {
public:
    Twitter() {
        // Write your solution here
    }
    void postTweet(int userId, int tweetId) {
    }
    vector<int> getNewsFeed(int userId) {
        return {};
    }
    void follow(int followerId, int followeeId) {
    }
    void unfollow(int followerId, int followeeId) {
    }
};

class Twitter {
    constructor() {
        // Write your solution here
    }
    postTweet(userId, tweetId) {
    }
    getNewsFeed(userId) {
        return [];
    }
    follow(followerId, followeeId) {
    }
    unfollow(followerId, followeeId) {
    }
}

0/9

Common Bugs to Avoid

Wrong: News feed missing followee tweetsNot including followees' tweets in getNewsFeed or not updating follow relationships.✅ In getNewsFeed, collect tweets from user and all followees before sorting and slicing.

Wrong: News feed includes duplicate tweetsCounting tweets multiple times due to incorrect data structure or logic.✅ Ensure each tweet is stored once and included once in news feed; avoid duplicates in merging.

Wrong: News feed returns more than 10 tweetsNot limiting output size to 10 in getNewsFeed.✅ After sorting tweets by timestamp descending, slice the list to first 10 elements.

Wrong: Unfollow causes error or removes wrong followeesNot checking if follower actually follows followee before unfollowing.✅ Check if followee exists in follower's followees set before removing.

Wrong: Solution times out on large inputsUsing brute force scanning of all tweets instead of heap-based merge.✅ Implement max heap to merge tweets from followees efficiently in O(k log F) time.

✓

Test Cases

t1_01basic

Input[["postTweet",1,5],["getNewsFeed",1]]

Expected[[5]]

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

t1_02basic

Input[["postTweet",2,6],["postTweet",2,7],["follow",1,2],["getNewsFeed",1]]

Expected[[7,6]]

User 2 posts tweets 6 and 7. User 1 follows user 2, so their news feed returns tweets 7 and 6 in order.

Practice

(1/5)

1. You need to design a system that tracks passengers checking in and out of stations, and efficiently calculates average travel times between stations. Which approach best balances time and space efficiency for frequent queries?

easy

A. Use hash maps to store running totals of travel times and counts per route.

B. Store all trips explicitly and scan them to compute averages on demand.

C. Use dynamic programming to precompute all possible route averages.

D. Use a priority queue to keep track of the shortest travel times per route.

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

Design Twitter (Top K Recent Tweets)

Practice

Solution

Step 1: Understand the problem requirements

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Analyze addNum complexity

Step 2: Analyze findMedian complexity

Final Answer:

Quick Check:

Solution

Step 1: Identify data structure operations

Step 2: Clarify average vs worst-case

Final Answer:

Quick Check:

Solution

Step 1: Understand reuse operation

Step 2: Efficiently update usage order

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?