Design Twitter (Top K Recent Tweets)

📋

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: passpublic class Twitter { public Twitter() { // constructor } public void postTweet(int userId, int tweetId) { // method } public List<Integer> getNewsFeed(int userId) { return new ArrayList<>(); } public void follow(int followerId, int followeeId) { // method } public void unfollow(int followerId, int followeeId) { // method } }class Twitter { public: Twitter() { // constructor } void postTweet(int userId, int tweetId) { // method } vector<int> getNewsFeed(int userId) { return {}; } void follow(int followerId, int followeeId) { // method } void unfollow(int followerId, int followeeId) { // method } };class Twitter { constructor() { // constructor } postTweet(userId, tweetId) { // method } getNewsFeed(userId) { return []; } follow(followerId, followeeId) { // method } unfollow(followerId, followeeId) { // method } }

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) {
    }
}

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

Try testing your code with users who have no tweets or followees to catch base cases.

Consider cases where multiple followees post tweets; test merging logic carefully.

Think about how to efficiently merge tweets from many followees without scanning all tweets.

t1_01basic

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

Expected[[5]]

⏱ Performance - must finish in 2000ms

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

💡 Focus on storing tweets per user and retrieving recent ones.

💡 Use a data structure that keeps tweets ordered by timestamp.

💡 Implement getNewsFeed to merge tweets from user and followees, returning top 10.

Why it failed: Returned news feed missing or incorrect tweets. Likely not merging user and followees' tweets correctly or not sorting by recency. Fix by collecting tweets from user and followees, sorting by timestamp descending, and returning top 10.

✓ Correctly returns the user's own tweets in news feed.

t1_02basic

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

Expected[[7,6]]

⏱ Performance - must finish in 2000ms

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

💡 Remember to update follow relationships before fetching news feed.

💡 Ensure getNewsFeed merges tweets from all followees plus the user.

💡 Sort combined tweets by timestamp descending and return top 10.

Why it failed: News feed missing followee's tweets or not ordered by recency. Fix by including followees' tweets and sorting by timestamp descending before slicing top 10.

✓ Correctly merges and orders tweets from followees and user.

t2_01edge

Input[["getNewsFeed",10]]

Expected[[]]

⏱ Performance - must finish in 2000ms

User 10 has no tweets and follows no one, so news feed is empty.

💡 Check behavior when user has no tweets and no followees.

💡 Ensure getNewsFeed returns empty list if no tweets found.

💡 Return empty list instead of null or error.

Why it failed: Returned non-empty or error for user with no tweets/followees. Fix by returning empty list when no tweets available.

✓ Correctly returns empty news feed for user with no tweets or followees.

t2_02edge

Input[["postTweet",3,10],["follow",3,3],["getNewsFeed",3]]

Expected[[10]]

⏱ Performance - must finish in 2000ms

User 3 follows themselves only and has one tweet, so news feed returns their own tweet.

💡 Check that following self is handled correctly.

💡 Ensure getNewsFeed includes user's own tweets even if only self-followed.

💡 Do not duplicate tweets if user follows self multiple times.

Why it failed: News feed missing user's own tweets or duplicates present. Fix by always including user's own tweets once regardless of followees.

✓ Correctly returns user's own tweets when following self.

t2_03edge

Input[["unfollow",4,5],["postTweet",4,20],["getNewsFeed",4]]

Expected[[20]]

⏱ Performance - must finish in 2000ms

User 4 unfollows user 5 whom they do not follow; no effect. User 4's own tweet appears in news feed.

💡 Check unfollow operation when follower does not follow followee.

💡 Ensure no error or state change occurs in such cases.

💡 News feed should still include user's own tweets.

Why it failed: Unfollow causes error or removes unintended followees. Fix by checking if followee exists before removing.

✓ Unfollow of non-followed user has no effect; news feed correct.

t3_01corner

Input[["postTweet",1,100],["postTweet",2,101],["postTweet",3,102],["follow",4,1],["follow",4,2],["follow",4,3],["getNewsFeed",4]]

Expected[[102,101,100]]

⏱ Performance - must finish in 2000ms

User 4 follows users 1,2,3 each with one tweet; news feed merges tweets ordered by recency.

💡 Beware of greedy approach that picks tweets from one user only.

💡 Use a heap to merge tweets from multiple followees efficiently.

💡 Implement k-way merge to get top 10 recent tweets from all followees.

Why it failed: News feed missing tweets from some followees or not ordered by recency. Fix by using a max heap to merge tweets from all followees.

✓ Correctly merges tweets from multiple followees in recency order.

t3_02corner

Input[["postTweet",1,200],["postTweet",1,201],["postTweet",1,202],["follow",2,1],["getNewsFeed",2]]

Expected[[202,201,200]]

⏱ Performance - must finish in 2000ms

User 2 follows user 1 who posted multiple tweets; news feed returns most recent 10 tweets correctly.

💡 Check that tweets are not counted multiple times (0/1 vs unbounded confusion).

💡 Ensure each tweet is included once and order is by timestamp descending.

💡 Do not allow duplicates or infinite repeats in news feed.

Why it failed: News feed contains duplicates or infinite repeats of tweets. Fix by storing tweets uniquely and returning each once.

✓ Correctly returns unique tweets in descending order.

t3_03corner

Input[["postTweet",1,300],["postTweet",1,301],["postTweet",1,302],["postTweet",1,303],["postTweet",1,304],["postTweet",1,305],["postTweet",1,306],["postTweet",1,307],["postTweet",1,308],["postTweet",1,309],["postTweet",1,310],["getNewsFeed",1]]

Expected[[310,309,308,307,306,305,304,303,302,301]]

⏱ Performance - must finish in 2000ms

User 1 posts 11 tweets; news feed returns only the 10 most recent tweets.

💡 Check boundary condition when more than 10 tweets exist.

💡 Ensure getNewsFeed limits output to 10 tweets max.

💡 Slice or limit the result after sorting by timestamp descending.

Why it failed: News feed returns more than 10 tweets or fewer than expected. Fix by slicing the sorted tweets to top 10 only.

✓ Correctly limits news feed to 10 most recent tweets.

t4_01performance

Input[["postTweet",1,1],["postTweet",2,2],["postTweet",3,3],["postTweet",4,4],["postTweet",5,5],["postTweet",6,6],["postTweet",7,7],["postTweet",8,8],["postTweet",9,9],["postTweet",10,10],["follow",100000,1],["follow",100000,2],["follow",100000,3],["follow",100000,4],["follow",100000,5],["follow",100000,6],["follow",100000,7],["follow",100000,8],["follow",100000,9],["follow",100000,10],["getNewsFeed",100000]]

Expectednull

⏱ Performance - must finish in 2000ms

Test with 10^5 users and 10 followees for user 100000; must complete getNewsFeed in O(k log F) time within 2s.

💡 Naive scanning of all tweets will time out.

💡 Use a max heap to merge tweets from followees efficiently.

💡 Optimize data structures for O(k log F) retrieval of news feed.

Why it failed: Solution times out due to scanning all tweets or inefficient merges. Fix by implementing heap-based k-way merge for getNewsFeed.

✓ Solution runs within time limits using efficient heap-based merge.

Practice

1. You are given a singly linked list where each node contains an additional random pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both next and random pointers. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Sort nodes by their values and then copy them sequentially, assigning random pointers based on sorted order.

B. Use a brute force approach with nested loops to assign random pointers after copying nodes.

C. Use dynamic programming to store intermediate results of copied nodes and their random pointers.

D. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires copying a linked list with random pointers efficiently, preserving structure.

2. Step 2: Identify the optimal approach

   Interleaving copied nodes within the original list allows O(1) extra space and O(n) time by leveraging the original list's structure to assign random pointers without extra data structures.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Interleaving nodes avoids extra hash maps and nested loops [OK]

Hint: Interleaving nodes enables O(1) space copying [OK]

Common Mistakes:

• Assuming nested loops are needed for random pointer assignment
• Thinking sorting helps with random pointers
• Confusing DP with linked list copying

2. 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.

Solution

1. Step 1: Understand the problem requirements

   The system must support frequent check-ins, check-outs, and quick average time queries between stations.

2. Step 2: Evaluate approaches

   Storing all trips (B) leads to slow queries. Dynamic programming (C) is not applicable as routes are dynamic and not fixed. Priority queues (D) do not help compute averages efficiently. Hash maps with running totals (A) allow O(1) updates and queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash maps maintain running sums and counts for O(1) average time queries [OK]

Hint: Running totals enable O(1) average queries [OK]

Common Mistakes:

• Thinking storing all trips is efficient for queries

3. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child lists can themselves have children, and so on. Which approach best guarantees an in-place flattening of this multilevel list into a single-level doubly linked list without using extra space?

easy

A. Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.

B. Use a recursive depth-first traversal that returns the tail of each flattened child list to connect nodes.

C. Apply a greedy approach that always appends child lists at the end of the main list after full traversal.

D. Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flattening a multilevel doubly linked list in-place without extra space.

2. Step 2: Identify the approach that guarantees in-place flattening without extra space

   Using a recursive depth-first traversal that returns the tail of each flattened child list allows splicing child lists correctly and efficiently without extra data structures.

3. Step 3: Evaluate other options

   Iterative splicing (Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.) can cause repeated tail searches leading to O(n^2) time and is less straightforward. Greedy appending (Apply a greedy approach that always appends child lists at the end of the main list after full traversal.) fails to maintain order. Dynamic programming (Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.) is not applicable.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Recursive DFS approach is standard and efficient for in-place flattening [OK]

Hint: Recursive DFS returns tail to connect lists efficiently [OK]

Common Mistakes:

• Assuming iterative splicing is always best despite complexity
• Appending child lists only at the end
• Using DP which is not applicable here

4. Given the following LFUCache code snippet and operations, what is the return value of cache.get(2) after these operations?

cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)

Assume the LFUCache uses the optimal approach shown.

easy

A. -1

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys 1 and 2 with freq=1. get(1) increments freq of key 1 to 2. Then put(3,3) triggers eviction of key with min freq=1, which is key 2 (least recently used among freq=1). Key 2 is evicted.

2. Step 2: Evaluate get(2)

   Key 2 was evicted, so get(2) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 2 evicted before get(2) call, so returns -1 [OK]

Hint: Evicted keys return -1 on get [OK]

Common Mistakes:

• Forgetting eviction removes key 2
• Assuming get(2) returns old value
• Confusing frequency increments

5. What is the time complexity of the checkOut operation in the optimal UndergroundSystem implementation that uses a linked list for check-ins, assuming n is the number of active check-ins at the time of checkout?

medium

A. O(1) because the linked list head always points to the correct check-in node

B. O(n) due to updating route data hash map entries

C. O(log n) because the linked list is sorted by check-in time

D. O(n) because it may need to traverse the linked list to find the matching check-in node

Solution

1. Step 1: Identify linked list traversal

   The checkOut method traverses the linked list from head to find the node with matching id, which can take up to O(n) time.

2. Step 2: Analyze route data update

   Updating the hash map for route data is O(1) average, so it does not dominate complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Traversal over n nodes dominates, so O(n) time [OK]

Hint: Linked list traversal dominates checkOut time [OK]

Common Mistakes:

• Assuming O(1) because head is used directly