Algorithmic Problem Solving Questions

import random
from typing import Iterable, List, TypeVar

T = TypeVar("T")

def reservoir_sample(stream: Iterable[T], k: int) -> List[T]:
    """
    Reservoir sampling (Algorithm R) — return k items sampled uniformly at random from stream.
    """
    if k <= 0:
        return []
    reservoir: List[T] = []
    it = iter(stream)
    # Fill initial reservoir with first k elements
    for _ in range(k):
        try:
            reservoir.append(next(it))
        except StopIteration:
            return reservoir  # stream shorter than k
    # Process remaining elements
    i = k  # number of items seen so far
    for item in it:
        i += 1  # this is the i-th item (1-based)
        j = random.randrange(i)  # uniform integer in [0, i-1]
        if j < k:
            reservoir[j] = item
    return reservoir

from collections import Counter
import heapq
from typing import List

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    if k <= 0:
        return []
    # Count frequencies: O(n)
    freq = Counter(nums)
    # Use a min-heap of (frequency, num). Keep size <= k: O(u log k) where u = unique elements
    heap = []
    for num, f in freq.items():
        if len(heap) < k:
            heapq.heappush(heap, (f, num))
        else:
            # If current freq bigger than smallest in heap, replace
            if f > heap[0][0]:
                heapq.heapreplace(heap, (f, num))
    # Extract results: O(k log k) or O(k)
    return [num for _, num in heapq.nlargest(k, heap)]

# assume loss_scale, accum_steps, optimizer, model_fp32, model_fp16
accum_grads = zero_like_fp32_params(model_fp32)
for micro_i, batch in enumerate(dataloader):
    outputs = model_fp16(batch)
    loss = loss_fn(outputs) * loss_scale / accum_steps   # scale and distribute
    loss.backward()  # produces fp16 grads scaled by loss_scale/accum_steps

    # convert and unscale per-parameter, accumulate into fp32 buffers
    overflow = False
    for p16, p32, g_acc in zip(model_fp16.params, model_fp32.params, accum_grads):
        g16 = p16.grad
        if g16 is None: continue
        g32 = g16.to(torch.float32)
        if torch.isinf(g32).any() or torch.isnan(g32).any():
            overflow = True
            break
        g32 = g32 / loss_scale  # unscale
        g_acc.add_(g32)        # accumulate in fp32

    if (micro_i + 1) % accum_steps == 0:
        if overflow:
            loss_scale = reduce_loss_scale(loss_scale)
            zero(accum_grads); zero(model_fp16.grads)
            continue
        # optional: compute norm on accumulated fp32 grads, clip if needed
        clip_grad_norm_(accum_grads, max_norm)
        optimizer.step_with_fp32_grads(accum_grads, model_fp32)
        model_fp16.load_state_dict(model_fp32.to(fp16))
        zero(accum_grads); zero(model_fp16.grads)