The Held-Karp Bitmask DP algorithm is the premier textbook demonstration of converting a factorial combinatorial explosion into a manageable exponential dynamic programming state space.

1. The Core Insight (Subproblem Overlap)

Suppose a drone visits cities in the order: 1 → 2 → 3 → 4.

Another candidate path visits cities in the order: 1 → 3 → 2 → 4.

Notice that in both cases, the set of visited cities is identical ({1, 2, 3, 4}), and the current ending city is identical (City 4)!

For future route choices (visiting the remaining cities 5 through 20), it does not matter how you traveled between 1, 2, and 3—all that matters is what is the minimum cost to have visited that exact subset and currently be sitting at City 4!

2. The State Definition

We define our DP state with two parameters: dp(mask, u)

• mask: An integer whose binary bits represent the subset of visited cities. If bit i is 1, City i has been visited. If bit i is 0, City i is unvisited.
• u: The current city where the drone is currently parked.

Transition:

To move to an unvisited city v (where (mask & (1 << v)) == 0):

dp(mask | (1 << v), v) = min(
    dp(mask | (1 << v), v),
    dp(mask, u) + dist[u][v]
)

Clean Python 3.12 Implementation with Memoization

from functools import lru_cache

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    ALL_VISITED = (1 << n) - 1

    @lru_cache(maxsize=None)
    def solve(mask: int, curr: int) -> int:
        # Base case: All cities have been visited -> return to starting city 0
        if mask == ALL_VISITED:
            return dist[curr][0]

        min_cost = float('inf')

        # Try visiting every unvisited city
        for nxt in range(n):
            if not (mask & (1 << nxt)):
                cost = dist[curr][nxt] + solve(mask | (1 << nxt), nxt)
                min_cost = min(min_cost, cost)

        return min_cost

    # Start at city 0 with only bit 0 set (1 << 0 = 1)
    return solve(1, 0)

Complexity Breakdown: From 10^17 down to 10^7

• Total Distinct States: $2^N$ masks $ imes N$ current cities = $N cdot 2^N$.
• Work per State: Loop over $N$ candidate next cities.
• Total Time Complexity: $O(N^2 cdot 2^N)$.

For $N = 20$:

• Brute force $19! pprox 1.21 imes 10^{17}$ operations (would take 3,800 years at 1 GHz).
• Held-Karp $20^2 cdot 2^{20} = 400 imes 1,048,576 pprox 4.19 imes 10^8$ operations (runs in under 1.5 seconds on a modern CPU)!

Consistent Hashing is one of the foundational building blocks of distributed systems (used in Apache Cassandra, Amazon DynamoDB, Akamai CDN, and Envoy Proxy).

1. The Problem with Naive Modulo Hashing

If you have 4 servers and use hash(key) % 4, when server 4 crashes, you now compute hash(key) % 3. Because almost every number changes its remainder modulo 3, nearly 100% of cached keys instantly miss, hammering your backend database in a catastrophic thundering herd.

In Consistent Hashing, when a server is added or removed, only $1/N$ of keys need to be remapped on average. All other keys stay on their existing servers!

2. The Hash Ring & Why Virtual Nodes are Mandatory

Imagine a circular ring of numbers from $0$ to $2^{32} – 1$ (the output space of a 32-bit hash function like Murmur3 or MD5).

• Each physical server is hashed onto a point on this ring.
• To find where a key belongs, you hash the key, find its coordinate on the ring, and walk clockwise until you hit the first server!

The Hot Spot Problem: If you only place 3 physical servers on the ring, their hash positions might be clustered close together (e.g. at 10 degrees, 25 degrees, and 280 degrees). Server 3 will end up handling 70% of all traffic, causing a massive hot spot!

The Solution (Virtual Nodes): Instead of hashing Server A once, we hash it 100 or 200 times under different labels ("server-A#1", "server-A#2", …, "server-A#200"). By distributing hundreds of virtual replicas uniformly across the 360-degree ring, standard deviations drop to near zero, and load is balanced evenly across all physical hardware.

Production Python 3.12 Implementation with bisect

import bisect
import hashlib

class ConsistentHashRing:
    def __init__(self, replicas: int = 150):
        self.replicas = replicas  # Virtual nodes per physical server
        self.ring: list[int] = [] # Sorted list of virtual node hash keys
        self.node_map: dict[int, str] = {} # hash_key -> physical_node_id

    def _hash(self, key: str) -> int:
        """Returns 32-bit integer hash using MD5."""
        return int(hashlib.md5(key.encode('utf-8')).hexdigest()[:8], 16)

    def add_node(self, node: str) -> None:
        """Adds a physical node by creating virtual replicas across the ring."""
        for i in range(self.replicas):
            v_key = f"{node}#vn_{i}"
            h = self._hash(v_key)
            idx = bisect.bisect_left(self.ring, h)
            self.ring.insert(idx, h)
            self.node_map[h] = node

    def remove_node(self, node: str) -> None:
        """Removes all virtual replicas belonging to the physical node."""
        for i in range(self.replicas):
            v_key = f"{node}#vn_{i}"
            h = self._hash(v_key)
            idx = bisect.bisect_left(self.ring, h)
            if idx < len(self.ring) and self.ring[idx] == h:
                self.ring.pop(idx)
                del self.node_map[h]

    def get_node(self, key: str) -> str | None:
        """Finds the physical server responsible for the given key in O(log(V * N))."""
        if not self.ring:
            return None

        h = self._hash(key)
        # Binary search clockwise to the nearest virtual node
        idx = bisect.bisect_right(self.ring, h)
        
        # If we walked past the end of the ring, wrap around to index 0
        if idx == len(self.ring):
            idx = 0

        return self.node_map[self.ring[idx]]

Complexity Breakdown

• Key Lookup: O(log(R * N)) using binary search, where R is replicas (e.g. 150) and N is physical servers (e.g. 10). Searching an array of 1,500 numbers takes 11 comparisons (< 1 microsecond).
• Node Add/Remove: O(R * log(R * N)). Adding a server only migrates keys from its immediate clockwise neighbor!

The classic, production-proven design for calculating running medians is the Dual-Heap Balancing Architecture (one Max-Heap and one Min-Heap).

1. The Mental Model

Imagine splitting all numbers you’ve seen so far into two equal halves:

• The Lower Half (all numbers $le$ median): We store these in a Max-Heap. Why? Because we only care about the largest number in this half!
• The Upper Half (all numbers $ge$ median): We store these in a Min-Heap. Why? Because we only care about the smallest number in this half!

   Lower Half (Max-Heap)          Upper Half (Min-Heap)
[1, 3, 5, 7, 9  -> (TOP: 9)]  <-->  [(TOP: 11) <- 11, 14, 18, 22]
                                     /
                        The Median is 
                     between 9 and 11!

The median is ALWAYS right at the fingertips: either the top of the Max-Heap, or the average of the two tops!

2. The Two Golden Invariants

To make this work 100% reliably, you must maintain two invariants after every single number is added:

1. Ordering Invariant: Every element in max_heap must be $le$ every element in min_heap. (If max_heap.top() > min_heap.top(), swap them).
2. Size Balance Invariant: The size difference between the two heaps must never exceed 1: 0 <= len(max_heap) - len(min_heap) <= 1.

Production Python 3.12 Implementation

import heapq

class MedianFinder:
    def __init__(self):
        # Python heapq is a min-heap by default.
        # To simulate a max-heap, multiply values by -1.
        self.small = []  # Max-heap (stores inverted values)
        self.large = []  # Min-heap (stores normal values)

    def add_num(self, num: int) -> None:
        # Step 1: Push to max-heap (small half)
        heapq.heappush(self.small, -num)
        
        # Step 2: Ensure ordering invariant (all small <= all large)
        if self.small and self.large and (-self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
            
        # Step 3: Ensure size invariant (len(small) can be at most 1 larger than len(large))
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        elif len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

    def find_median(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0

Performance & Production Benchmarks

• add_num() Time: O(log N). Pushing and popping from heaps of size N/2 takes ~15-20 CPU instructions.
• find_median() Time: O(1). Simply peek at heap roots (index 0). Instantaneous!
• Space Complexity: O(N) total memory to store the incoming stream numbers.