Blind 75 Linked Lists, Binary Search, And Heaps

Invariant: prev is the fully reversed prefix and cur is the first node in the unreversed suffix. The common mistake is overwriting cur.next before saving the original next node.

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

Invariant: the heap contains the smallest unmerged node from each active list. Use a tie-breaker counter because Python cannot compare list node objects directly. Test empty input, empty lists inside the input, duplicate values, one list, and lists with negative values.

from heapq import heappop, heappush

def merge_k_lists(lists):
    heap = []
    counter = 0
    for node in lists:
        if node:
            heappush(heap, (node.val, counter, node))
            counter += 1

    dummy = ListNode(0)
    tail = dummy
    while heap:
        _, _, node = heappop(heap)
        tail.next = node
        tail = tail.next
        if node.next:
            heappush(heap, (node.next.val, counter, node.next))
            counter += 1

    tail.next = None
    return dummy.next

Use Floyd's slow and fast pointers. If the fast pointer reaches null, the list terminates; if slow and fast meet, there is a cycle. Common mistakes are advancing fast.next.next before checking fast and fast.next, or returning false after only one unequal step.

Invariant: if the target exists, it is inside [lo, hi]. At least one half is sorted at every step. The common mistake is deciding which half is sorted but using strict comparisons that accidentally discard the midpoint value.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid

        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Invariant: the minimum is always inside [lo, hi]. If nums[mid] > nums[hi], the minimum is to the right; otherwise it is at mid or to the left. Test not rotated, rotated by one, two elements, and a single element.

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

Define a predicate ok(replicas) that returns true when the simulator or load test meets the p95 queue target. If adding replicas never worsens queue delay under the same traffic, the predicate is monotonic: false, false, true, true. Binary search finds the smallest passing replica count. In practice, add repeated trials and confidence bounds because load tests are noisy.

Invariant: the max heap stores the smaller half and the min heap stores the larger half; their sizes differ by at most one. Python only has a min heap, so store negative values for the lower half.

from heapq import heappop, heappush

class MedianFinder:
    def __init__(self):
        self.low = []
        self.high = []

    def addNum(self, num):
        heappush(self.low, -num)
        heappush(self.high, -heappop(self.low))
        if len(self.high) > len(self.low):
            heappush(self.low, -heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

Count first, then keep a min heap of size k. The heap contains the current top candidates. Test k = 1, k equal to the number of distinct values, ties, and an input with one repeated value.

from collections import Counter
from heapq import heappush, heappushpop

def top_k_frequent(nums, k):
    heap = []
    for value, count in Counter(nums).items():
        item = (count, value)
        if len(heap) < k:
            heappush(heap, item)
        else:
            heappushpop(heap, item)
    return [value for _, value in heap]

Use counts keyed by phrase plus a heap for top-k candidates. For a high-volume stream, handle stale heap entries by comparing the heap count against the latest count map when popping. Discuss windowing, tenant isolation, privacy redaction, and whether exact counts are required or approximate heavy hitters are enough.

If the same traffic replay shows latency worsening monotonically as exposure increases, binary search the exposure level with a predicate like p99_latency <= slo. In live systems, monotonicity can be broken by traffic mix and autoscaling, so pair the search with controlled replay, repeated trials, and slice-level checks before making a rollback rule.