Find Median from Data Stream

▶

Steps

setup

Initialize MedianFinder

Create empty max heap 'small' and min heap 'large', initialize delayed removals map and size counters.

💡 Starting with empty heaps and counters sets the foundation for adding numbers and balancing heaps.

Line:

self.small = []  # max heap (invert values)
self.large = []  # min heap
self.delayed = {}
self.small_size = 0
self.large_size = 0

💡 Heaps and counters are ready to track numbers and maintain balance.

insert

Add number 1 to 'small' heap

Since 'small' is empty, add 1 to 'small' as -1 (max heap stores negatives). Increment small_size.

💡 First number goes to 'small' heap to start building the data structure.

Line:

if not self.small or num <= -self.small[0]:
    heapq.heappush(self.small, -num)
    self.small_size += 1

💡 The first number always goes to 'small' heap to start balancing.

insert

Add number 2 to 'large' heap

Number 2 is greater than -small[0] (which is 1), so add 2 to 'large' heap and increment large_size.

💡 Numbers greater than the max of 'small' go to 'large' heap to keep order.

Line:

else:
    heapq.heappush(self.large, num)
    self.large_size += 1

💡 Splitting numbers between heaps keeps them balanced and ordered.

shrink

Balance heaps after adding 2

Heaps are balanced: small_size=1, large_size=1, difference is 0, so no rebalancing needed.

💡 Balancing ensures heaps differ in size by at most 1 for correct median calculation.

Line:

if self.small_size > self.large_size + 1:
    ...
elif self.large_size > self.small_size:
    ...

💡 Balanced heaps mean median can be computed from tops directly.

compare

Find median after adding 1 and 2

Since both heaps have equal size, median is average of tops: (1 + 2) / 2 = 1.5.

💡 Median for even count is average of max of 'small' and min of 'large'.

Line:

if self.small_size == self.large_size:
    median = (-self.small[0] + self.large[0]) / 2

💡 Median depends on top elements of both heaps when sizes match.

insert

Add number 3 to 'large' heap

Number 3 is greater than -small[0] (1), so add 3 to 'large' heap and increment large_size.

💡 New number goes to 'large' because it is greater than max of 'small'.

Line:

else:
    heapq.heappush(self.large, num)
    self.large_size += 1

💡 Adding to 'large' may unbalance heaps, requiring rebalancing.

shrink

Balance heaps after adding 3

Since large_size (2) > small_size (1), move smallest from 'large' (2) to 'small' as -2. Update sizes accordingly.

💡 Balancing keeps heaps sizes within 1 to maintain median correctness.

Line:

elif self.large_size > self.small_size:
    val = heapq.heappop(self.large)
    self.large_size -= 1
    heapq.heappush(self.small, -val)
    self.small_size += 1

💡 Rebalancing moves elements between heaps to maintain size property.

compare

Find median after adding 3

Now small_size (2) > large_size (1), median is top of 'small' heap: 2 (negate -2).

💡 Median for odd count is top of larger heap.

Line:

else:
    median = -self.small[0]

💡 Median depends on heap sizes and top elements.

reconstruct

Summary: Median after first findMedian call

Median after adding 1 and 2 is 1.5, computed from tops of both heaps.

💡 Shows how median is derived from balanced heaps with even count.

Line:

return median

💡 Median calculation depends on heap sizes and top elements.

reconstruct

Summary: Median after second findMedian call

Median after adding 3 is 2, the top of 'small' heap which has more elements.

💡 Shows median for odd count from the larger heap top.

Line:

return median

💡 Median is the middle element when count is odd.

import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max heap (invert values)  # STEP 1
        self.large = []  # min heap  # STEP 1
        self.delayed = {}  # STEP 1
        self.small_size = 0  # STEP 1
        self.large_size = 0  # STEP 1

    def _prune(self, heap):
        while heap and self.delayed.get(abs(heap[0]), 0):
            num = abs(heap[0])
            self.delayed[num] -= 1
            if self.delayed[num] == 0:
                del self.delayed[num]
            heapq.heappop(heap)

    def addNum(self, num: int) -> None:
        if not self.small or num <= -self.small[0]:  # STEP 2,6
            heapq.heappush(self.small, -num)  # STEP 2,6
            self.small_size += 1  # STEP 2,6
        else:
            heapq.heappush(self.large, num)  # STEP 3,6
            self.large_size += 1  # STEP 3,6

        # Balance heaps
        if self.small_size > self.large_size + 1:  # STEP 7
            val = -heapq.heappop(self.small)  # STEP 7
            self.small_size -= 1  # STEP 7
            heapq.heappush(self.large, val)  # STEP 7
            self.large_size += 1  # STEP 7
        elif self.large_size > self.small_size:  # STEP 7
            val = heapq.heappop(self.large)  # STEP 7
            self.large_size -= 1  # STEP 7
            heapq.heappush(self.small, -val)  # STEP 7
            self.small_size += 1  # STEP 7

    def findMedian(self) -> float:
        if self.small_size == self.large_size:  # STEP 5
            return (-self.small[0] + self.large[0]) / 2  # STEP 5
        else:
            return -self.small[0]  # STEP 8

    def removeNum(self, num: int) -> None:
        self.delayed[num] = self.delayed.get(num, 0) + 1
        if self.small and num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self._prune(self.small)
        else:
            self.large_size -= 1

📊

Find Median from Data Stream - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the two heaps maintain a balanced state to efficiently find the median at any point in the data stream.

setup

insert

small_top

-1

0

insert

small_top

-1

0

large_top

2

1

compare

small_top

-1

0

large_top

2

1

compare

small_top

-1

0

large_top

2

1

Result: 1.5

insert

small_top

-1

0

large_top

2

1

3

2

Result: 1.5

rebalance

small_top

-2

0

-1

1

large_top

3

2

Result: 1.5

compare

small_top

-2

0

-1

1

large_top

3

2

Result: 2

record

small_top

-1

0

large_top

2

1

Result: 1.5

record

small_top

-2

0

-1

1

large_top

3

2

Result: 2

Key Takeaways

✓ Two heaps maintain a balanced partition of the data stream to efficiently compute median.

This balance is hard to see from code alone but is clear when watching heaps grow and shrink.

✓ Median calculation depends on heap sizes: average of tops if equal, top of larger heap if odd count.

Visualizing heap sizes and top elements clarifies why median formulas differ.

✓ Rebalancing moves elements between heaps to maintain size constraints after each insertion.

Seeing the actual element moved during rebalance helps understand the heap size invariants.

Practice

1. Given the following code snippet for the optimal Twitter design, what is the output of getNewsFeed(1) after these operations?

twitter = Twitter()
twitter.postTweet(1, 5)
twitter.postTweet(2, 6)
twitter.followees[1] = {2}
print(twitter.getNewsFeed(1))

Assume getNewsFeed returns a list of tweetIds sorted from most recent to oldest.

easy

A. [6]

B. [5, 6]

C. [5]

D. [6, 5]

Solution

1. Step 1: Trace postTweet calls

   User 1 posts tweet 5 at time=1, user 2 posts tweet 6 at time=2.

2. Step 2: Trace getNewsFeed(1)

   User 1 follows user 2, so heap contains tweets with times 1 (tweet 5) and 2 (tweet 6). Max heap pops tweet 6 first, then tweet 5.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Heap orders tweets by descending time, so output is [6, 5] [OK]

Hint: Heap orders tweets by negative time for max behavior [OK]

Common Mistakes:

• Returning tweets in posting order instead of time order
• Ignoring followees' tweets

2. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call? Operations: insert(1), insert(1), insert(2), remove(1), getRandom()

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = null
        self.next = null

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(null)
        self.tail = Node(null)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        if val not in self.idx_map:
            self.idx_map[val] = set()
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    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)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        if not self.idx_map[val]:
            del self.idx_map[val]
        return true

    def getRandom(self) -> int:
        return random.choice(self.nums)

rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()

easy

A. Either 1 or 2 but 1 is twice as likely

B. 2

C. Either 1 or 2 with equal probability

D. 1

Solution

1. Step 1: Trace insertions

   After insert(1), nums=[1], idx_map={1:{0}}; after insert(1), nums=[1,1], idx_map={1:{0,1}}; after insert(2), nums=[1,1,2], idx_map={1:{0,1},2:{2}}.

2. Step 2: Trace removal of one 1

   Remove one 1: remove_idx=1 (pop from idx_map[1]). Swap last element 2 into index 1: nums=[1,2], idx_map={1:{0},2:{1}}. So now nums has one 1 and one 2.

3. Step 3: Analyze getRandom probabilities

   nums=[1,2], so getRandom picks index 0 or 1 equally. But initially there were two 1's, after removal only one remains. So 1 and 2 are equally likely, but since the original had duplicates, the final collection has one 1 and one 2.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   After removal, one 1 and one 2 remain, so 1 is as likely as 2 [OK]

Hint: Track indices and swaps carefully to find final array state [OK]

Common Mistakes:

• Forgetting to update idx_map after swap
• Assuming getRandom returns only 2
• Ignoring that one 1 remains after removal

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

4. What is the average time complexity of search, insert, and erase operations in a skiplist with dynamic max level and probability tuning, assuming n elements?

medium

A. O(log n) average due to probabilistic multi-level structure

B. O(1) average due to direct indexing in arrays

C. O(log^2 n) because each level requires a separate traversal

D. O(n) because linked lists require linear traversal

Solution

1. Step 1: Understand skiplist structure

   Skiplist uses multiple levels with probabilistic promotion, reducing expected search path length to logarithmic in n.

2. Step 2: Analyze average operation cost

   Each operation traverses from top level down, with expected O(log n) steps due to geometric level distribution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Skiplist average complexity is well-known as O(log n) [OK]

Hint: Skiplist average complexity is logarithmic, not linear or constant [OK]

Common Mistakes:

• Assuming linear time due to linked list base
• Confusing traversal at each level as multiplicative
• Thinking arrays provide O(1) search in skiplist

5. What is the time complexity of the get and put operations in an optimal LRU Cache implementation using a hash map and a doubly linked list with capacity n?

medium

A. O(n) for get and put due to list traversal

B. O(1) amortized for get and put using hash map and doubly linked list

C. O(log n) due to balancing the linked list

D. O(1) for get but O(n) for put due to eviction

Solution

1. Step 1: Analyze get operation

   Hash map provides O(1) access to node; doubly linked list allows O(1) removal and insertion to update usage order.

2. Step 2: Analyze put operation

   Insertion involves hash map update and linked list insertion/removal, all O(1). Eviction removes tail node in O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both get and put run in constant time using combined data structures [OK]

Hint: Hash map + doubly linked list -> O(1) get and put [OK]

Common Mistakes:

• Assuming list removal is O(n)
• Confusing amortized with worst-case
• Thinking linked list needs balancing