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 snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

2. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

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

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

Solution

1. Step 1: Trace bisect indices on empty starts list

   Initially, self.starts = []. Calling bisect_left([], 2) returns 0, and bisect_right([], 6) returns 0.

2. Step 2: Update intervals and starts

   Since i == 0, the first if condition is skipped. Also, j == 0, so second if is skipped. No intervals to delete. Insert left=2 at self.starts[0:0], so self.starts = [2]. Interval stored as {2:6}.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starts list after first addRange is [2] [OK]

Hint: Bisect on empty list returns 0, so starts list gets single element [OK]

Common Mistakes:

• Assuming right endpoint is also inserted in starts list

3. What is the time complexity of the inc and dec operations in the optimized AllOne data structure that uses doubly linked list buckets and hash maps, and why?

medium

A. O(1) worst-case because all operations involve only pointer and hash map updates

B. O(1) amortized because bucket insertion and removal are constant time with hash maps

C. O(log n) due to maintaining sorted order of buckets

D. O(n) because updating buckets requires scanning keys

Solution

1. Step 1: Identify operations involved in inc/dec

   Operations include moving keys between buckets, inserting/removing buckets, and updating hash maps.

2. Step 2: Analyze complexity of each operation

   All pointer updates and hash map lookups/inserts/removals are O(1). No scanning or sorting is needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All operations are pointer and hash map updates, no loops over keys [OK]

Hint: Pointer and hash map ops are O(1), no scanning or sorting [OK]

Common Mistakes:

• Confusing bucket insertion as O(log n) or scanning keys as O(n)

4. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random  # Bug here
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

medium

A. Line assigning curr.next.random = curr.random

B. Line inserting copied nodes: curr.next = new_node

C. Line advancing curr in Step 1: curr = new_node.next

D. Line separating original and copied lists: curr.next = curr.next.next

Solution

1. Step 1: Analyze random pointer assignment

   The line assigns curr.next.random = curr.random, but curr.random points to original nodes, not copied nodes.

2. Step 2: Correct assignment

   It should be curr.next.random = curr.random.next to point to the copied node corresponding to curr.random.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect random pointer assignment breaks copied list correctness [OK]

Hint: Random pointer must point to copied node, not original [OK]

Common Mistakes:

• Assigning random pointer directly to original node
• Mixing original and copied nodes after weaving
• Forgetting to advance curr by two nodes

5. Examine the following buggy remove method from the optimized Insert Delete GetRandom O(1) with duplicates data structure. Which line contains the subtle bug that can cause incorrect behavior or runtime errors?

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)
    # BUG: missing discard of old index for last_val
    self.nums.pop()
    if not self.idx_map[val]:
        del self.idx_map[val]
    return true

medium

A. Missing line to discard old index of last_val from idx_map[last_val]

B. Line adding remove_idx to idx_map[last_val] (self.idx_map[last_val].add(remove_idx))

C. Line popping remove_idx from idx_map[val] (remove_idx = self.idx_map[val].pop())

D. Line removing the last element from nums (self.nums.pop())

Solution

1. Step 1: Understand index updates during removal

   When swapping last_val into remove_idx, we must update idx_map[last_val] by adding remove_idx and discarding the old index (len(nums)-1).

2. Step 2: Identify missing discard

   The code adds remove_idx to idx_map[last_val] but does not discard the old index, causing stale indices and incorrect removals later.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing discard leads to incorrect index tracking [OK]

Hint: Always discard old indices after swapping during removal [OK]

Common Mistakes:

• Forgetting to discard old index after swap
• Removing wrong element from idx_map
• Incorrect pop from idx_map[val]