Backend Relevant Problem Domains Questions

def remove_duplicates(nums):
    """
    Removes duplicates in-place from sorted list nums.
    Returns new length (number of unique elements).
    Modifies the first part of nums to contain the unique values in order.
    """
    if not nums:
        return 0

    write = 1  # index where next unique value should be written
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1

    return write

import random
from typing import Iterator, Optional

def exp_backoff(
    base: float = 0.5,
    multiplier: float = 2.0,
    max_delay: float = 30.0,
    max_retries: Optional[int] = None,
    jitter: str = "none",
) -> Iterator[float]:
    """
    Yields delay seconds for retries using exponential backoff.

    base: initial delay in seconds
    multiplier: exponential multiplier per attempt
    max_delay: upper cap for delay
    max_retries: None for infinite, or integer limit
    jitter: "none", "full", "equal", or "decorrelated"
    """
    attempt = 0
    prev = base
    while max_retries is None or attempt < max_retries:
        # compute exponential delay capped
        exp = base * (multiplier ** attempt)
        delay = min(exp, max_delay)

        # apply jitter
        if jitter == "none":
            out = delay
        elif jitter == "full":
            out = random.uniform(0, delay)
        elif jitter == "equal":
            out = random.uniform(delay / 2.0, delay)
        elif jitter == "decorrelated":
            # decorrelated jitter: random between base and min(max, prev * multiplier)
            upper = min(max_delay, prev * multiplier)
            out = random.uniform(base, upper)
            prev = out
        else:
            raise ValueError("unsupported jitter strategy")

        yield out
        attempt += 1

import math
import hashlib
from typing import Iterable

class SimpleBloom:
    def __init__(self, expected_n: int, false_positive_rate: float):
        # Compute optimal size m and number of hashes k
        m = - (expected_n * math.log(false_positive_rate)) / (math.log(2) ** 2)
        self.m = int(m)
        k = (self.m / expected_n) * math.log(2)
        self.k = max(1, int(round(k)))
        self.bit_array = bytearray((self.m + 7) // 8)
        self.n = 0

    def _hashes(self, item: bytes):
        # double hashing: h1 + i*h2 mod m
        h1 = int(hashlib.md5(item).hexdigest(), 16)
        h2 = int(hashlib.sha1(item).hexdigest(), 16)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item: str):
        b = item.encode('utf-8')
        for idx in self._hashes(b):
            self.bit_array[idx // 8] |= 1 << (idx % 8)
        self.n += 1

    def might_contain(self, item: str) -> bool:
        b = item.encode('utf-8')
        for idx in self._hashes(b):
            if not (self.bit_array[idx // 8] & (1 << (idx % 8))):
                return False
        return True

    def reset(self):
        self.bit_array = bytearray(len(self.bit_array))
        self.n = 0

    def serialize(self) -> bytes:
        # Persist: store metadata + raw bitarray
        meta = f"{self.m},{self.k},{self.n}\n".encode()
        return meta + bytes(self.bit_array)

    @classmethod
    def deserialize(cls, data: bytes):
        header, bits = data.split(b'\n', 1)
        m, k, n = map(int, header.decode().split(','))
        obj = cls.__new__(cls)
        obj.m, obj.k, obj.n = m, k, n
        obj.bit_array = bytearray(bits)
        return obj