Design Twitter (Top K Recent Tweets)

▶

Steps

setup

Initialize Twitter Object

Create a new Twitter instance with empty userTweets and followees maps, and time set to zero.

💡 This sets up the data structures needed to store tweets and follow relationships.

Line:

def __init__(self):
    self.time = 0
    self.userTweets = {}
    self.followees = {}

💡 The Twitter object starts empty, ready to record tweets and follows.

insert

Post Tweet: User 1 posts Tweet 5

Increment global time to 1. Create a new TweetNode with tweetId=5 and time=1. Set its next pointer to current head of user 1's tweets (none). Update user 1's tweet head to this new node.

💡 Posting a tweet adds a new node at the head of the user's tweet linked list, keeping newest tweets first.

Line:

self.time += 1
node = TweetNode(tweetId, self.time)
node.next = self.userTweets.get(userId, None)
self.userTweets[userId] = node

💡 New tweets are always added at the front, so the head pointer always points to the newest tweet.

setup

Prepare to Get News Feed for User 1

Retrieve followees of user 1 (none), add user 1 to the set of users to consider for news feed.

💡 News feed includes tweets from the user and their followees; here only user 1 is included.

Line:

users = self.followees.get(userId, set()).copy()
users.add(userId)

💡 Even if no followees exist, the user’s own tweets are included in their news feed.

fill_cells

Push User 1's Head Tweet into Max Heap

Get user 1's tweet head node (tweetId=5, time=1). Push it into the max heap with priority -time to simulate max heap using Python's min heap.

💡 Heap stores the newest tweets from each user to efficiently get the most recent overall tweet.

Line:

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

💡 Heap initialization includes the newest tweet from each user considered for the feed.

compare

Pop Most Recent Tweet from Heap

Pop the tweet with highest timestamp from heap (tweetId=5, time=1). Add tweetId=5 to the result list.

💡 Extracting the top tweet from the heap gives the most recent tweet to add to the news feed.

Line:

neg_time, node = heapq.heappop(heap)
res.append(node.tweetId)

💡 Heap pop returns the newest tweet available among all users considered.

traverse

Check for Next Tweet in User 1's List

Check if the popped tweet node has a next tweet. Since node.next is null, no further tweets to push into heap.

💡 If there were older tweets, they would be pushed into the heap to continue merging.

Line:

if node.next:
    heapq.heappush(heap, (-node.next.time, node.next))

💡 The linked list traversal ends when no older tweets remain.

compare

Check Heap and Result Length to Continue

Heap is empty and result length is 1, less than 10, so loop ends.

💡 The loop stops when either 10 tweets are collected or no more tweets remain.

Line:

while heap and len(res) < 10:

💡 The algorithm correctly stops when no more tweets are available.

reconstruct

Return News Feed Result

Return the collected list of tweet IDs [5] as the news feed for user 1.

💡 The final result is the top recent tweets merged from all relevant users.

Line:

return res

💡 The news feed is correctly generated from the linked list and heap merging process.

setup

Summary: User 1's Tweet List

Visualize the final linked list of user 1's tweets with a single node containing tweetId=5.

💡 This confirms the tweet list structure after posting.

Line:

N/A - visualization step

💡 User 1's tweet list is a single node linked list with the newest tweet at head.

reconstruct

Final State: News Feed Result

The final news feed for user 1 is [5], showing the most recent tweet posted.

💡 This final step confirms the output matches the expected result.

Line:

N/A - final output

💡 The algorithm correctly returns the top recent tweets for the user.

import heapq

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

class Twitter:
    def __init__(self):
        self.time = 0          # STEP 1
        self.userTweets = {}   # STEP 1
        self.followees = {}    # STEP 1

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

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

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

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

    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)

📊

Design Twitter (Top K Recent Tweets) - Watch the Algorithm Execute, Step by Step

Watching each pointer and heap operation live reveals how the linked list and heap combine to efficiently produce the news feed, which is hard to grasp from code alone.

advance

insert

Tweet Id:5

Time:1

advance

Tweet Id:5

Time:1

insert

Tweet Id:5

Time:1

detach

Tweet Id:5

Time:1

Result: [5]

advance

Tweet Id:5

Time:1

Result: [5]

advance

Tweet Id:5

Time:1

Result: [5]

advance

Tweet Id:5

Time:1

Result: [5]

advance

Tweet Id:5

Time:1

advance

Tweet Id:5

Time:1

Result: [5]

Key Takeaways

✓ Tweets are stored as linked lists per user with newest tweets at the head.

This structure allows O(1) insertion and easy traversal from newest to oldest tweets.

✓ The news feed merges multiple users' tweet lists using a max heap keyed by timestamp.

This merging efficiently retrieves the top recent tweets across all followees without scanning all tweets.

✓ Each step of heap push/pop and linked list traversal corresponds to one meaningful operation in the algorithm.

Seeing these operations individually clarifies how the algorithm maintains the correct order and stops correctly.

Practice

1. Consider the following Python code implementing the optimal CustomStack with lazy increments. After executing the sequence of operations below, what is the output of the last pop() call?

cs = CustomStack(3)
cs.push(1)
cs.push(2)
cs.increment(2, 5)
print(cs.pop())

easy

A. 2

B. 7

C. 6

D. 1

Solution

1. Step 1: Trace the increment operation

   After pushing 1 and 2, stack = [1, 2], inc = [0, 0, 0]. increment(2, 5) sets inc[1] += 5 -> inc = [0, 5, 0].

2. Step 2: Trace the pop operation

   pop() removes top element at index 1 (value 2). Since i=1 > 0, inc[0] += inc[1] -> inc[0] = 0 + 5 = 5. Result = stack.pop() + inc[1] = 2 + 5 = 7. inc[1] reset to 0.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Increment applied lazily, pop returns 7 [OK]

Hint: Increment applies to inc array index k-1, added on pop [OK]

Common Mistakes:

• Forgetting to propagate increments down on pop
• Adding increments directly to popped element only

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

3. Consider the following buggy LFUCache get method. Which line contains the subtle bug that can cause incorrect eviction behavior?

def get(self, key: int) -> int:
    if key not in self.key_val_freq:
        return -1
    val, freq = self.key_val_freq[key]
    del self.freq_keys[freq][key]
    if not self.freq_keys[freq]:
        del self.freq_keys[freq]
        # BUG: missing update of min_freq here
    self.freq_keys[freq + 1][key] = None
    self.key_val_freq[key] = (val, freq + 1)
    return val

What is the bug?

medium

A. Missing update of min_freq after deleting freq_keys[freq]

B. Line deleting freq_keys[freq] when empty

C. Line deleting key from freq_keys[freq]

D. Line adding key to freq_keys[freq + 1]

Solution

1. Step 1: Identify the role of min_freq

   min_freq tracks the smallest frequency present in the cache, needed for correct eviction.

2. Step 2: Check frequency list deletion

   When freq_keys[freq] becomes empty and is deleted, if freq equals min_freq, min_freq must be incremented to freq + 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing min_freq update causes stale min_freq and wrong eviction [OK]

Hint: min_freq must update when freq list empties [OK]

Common Mistakes:

• Forgetting to update min_freq after freq list deletion
• Confusing key deletion with frequency list deletion
• Assuming min_freq updates automatically

4. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output?

medium

A. Line where merged.append([x, max_h]) is called unconditionally

B. Line where x, h1 = left[i] inside first if

C. Line where max_h is computed with max(h1, h2)

D. Line where i and j are incremented in the else block

Solution

1. Step 1: Identify difference from correct code

   The bug is that merged.append is called every iteration without checking if height changed, causing redundant points.

2. Step 2: Understand impact of redundant points

   Appending points even when max_h equals previous height leads to unnecessary key points, failing correctness checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct code appends only if height changes [OK]

Hint: Appending only on height change avoids redundant points [OK]

Common Mistakes:

• Appending every iteration regardless of height change
• Incorrect pointer increments

5. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness