Heaps, Priority Queues and Greedy Interview Questions for Data Structures and Algorithms

import heapq def kth_largest(nums, k): heap = [] for x in nums: heapq.heappush(heap, x) if len(heap) > k: heapq.heappop(heap) # drop the smallest return heap[0] # smallest of the k largest # kth_largest([3, 2, 1, 5, 6, 4], 2) -> 5 # O(n log k) time, O(k) space; quickselect gives O(n) average

import heapq def merge_k_lists(lists): heap = [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) # i breaks ties dummy = tail = ListNode() while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next # O(N log K) for N total nodes

// Java static int minPlatforms(int[] arr, int[] dep) { Arrays.sort(arr); Arrays.sort(dep); int i = 0, j = 0, cur = 0, best = 0; while (i < arr.length) { if (arr[i] <= dep[j]) { // a train arrives before the next departs cur++; i++; best = Math.max(best, cur); } else { cur--; j++; } } return best; } // O(n log n) for sorting, O(1) extra space.

def can_jump(nums): farthest = 0 for i, step in enumerate(nums): if i > farthest: # this index is unreachable return False farthest = max(farthest, i + step) if farthest >= len(nums) - 1: return True return True # [2,3,1,1,4] -> True, [3,2,1,0,4] -> False # Greedy: track the farthest reachable index, O(n) time, O(1) space

import heapq class MedianFinder: def __init__(self): self.low = [] # max-heap via negation (smaller half) self.high = [] # min-heap (larger half) def add(self, x): heapq.heappush(self.low, -x) heapq.heappush(self.high, -heapq.heappop(self.low)) if len(self.high) > len(self.low): heapq.heappush(self.low, -heapq.heappop(self.high)) def median(self): if len(self.low) > len(self.high): return -self.low[0] return (-self.low[0] + self.high[0]) / 2 # add is O(log n), median is O(1)