Coding Interview Patterns and Meta Strategies Questions

# simple HLL wrapper pseudocode
from xxhash import xxh64

class HLL:
    def __init__(self, p=14):
        self.p = p
        self.m = 1 << p
        self.registers = [0] * self.m

    def _rho(self, w, max_bits):
        # count leading zeros in w (1-based)
        return min(max_bits, (w.bit_length() ^ (1 << (max_bits-1))).bit_length())  # placeholder

    def add(self, ip):
        h = xxh64(ip).intdigest()  # 64-bit hash
        idx = h & (self.m - 1)       # lower p bits
        w = h >> self.p              # remaining bits
        rank = self._rho(w, 64 - self.p)
        self.registers[idx] = max(self.registers[idx], rank)

    def merge(self, other):
        assert self.p == other.p
        for i in range(self.m):
            if other.registers[i] > self.registers[i]:
                self.registers[i] = other.registers[i]

    def count(self):
        # apply HLL bias correction and alpha_m constants (omitted details)
        Z = 1.0 / sum(2 ** (-r) for r in self.registers)
        E = alpha(self.m) * (self.m ** 2) * Z
        # small-cardinality correction (linear counting) and large range correction applied here
        return corrected_E(E)

from typing import List, Tuple, Optional

def longest_period_under_threshold(samples: List[Tuple[int, float]], threshold: float
                                  ) -> Optional[Tuple[int, int]]:
    """
    samples: list of (timestamp, latency), timestamps strictly increasing
    threshold: maximum allowed average latency (per-sample average)
    Returns (start_ts, end_ts) inclusive timestamps of longest contiguous period by time,
    or None if no window meets the threshold.
    """
    n = len(samples)
    if n == 0:
        return None

    left = 0
    sum_lat = 0.0
    best_start = best_end = None
    best_duration = -1

    for right in range(n):
        sum_lat += samples[right][1]

        # shrink while average exceeds threshold
        while left <= right and (sum_lat / (right - left + 1)) > threshold:
            sum_lat -= samples[left][1]
            left += 1

        # now window [left..right] has avg <= threshold (or left > right => empty)
        if left <= right:
            start_ts = samples[left][0]
            end_ts = samples[right][0]
            duration = end_ts - start_ts
            if duration > best_duration:
                best_duration = duration
                best_start, best_end = start_ts, end_ts

    return (best_start, best_end) if best_start is not None else None