Handling Problem Variations and Constraints Questions

This topic covers the ability to adapt an initial proposed solution when an interviewer introduces follow-up questions, new constraints, a changed goal, or a much larger scale of the problem. Candidates should quickly clarify what exactly changed, analyze how it affects correctness, quality, and complexity, and propose concrete modifications, such as choosing a different method, tool, or structure, adding buffering or caching, introducing parallel or incremental processing, or adopting approximation and heuristics when an exact solution becomes impractical. They should articulate trade-offs between speed, resource usage, simplicity, and robustness, explain how they would validate the modified solution and handle edge cases, and describe incremental steps and fallback plans if the primary approach becomes infeasible. Interviewers use this to assess adaptability, structured problem solving under evolving requirements, and clear communication of design decisions, regardless of technical domain.

HardTechnical

19 practiced

Implement the Misra-Gries algorithm in Python to find approximate top-k frequent items in a stream using one pass and O(k) memory. Your function should return candidate items with approximate counts and explain the theoretical error guarantee. Demonstrate on stream [a,b,a,c,a,b,d,a].

Sample Answer

Approach: Use the Misra–Gries algorithm with k counters (store at most k distinct items). For each stream element: if it's tracked, increment; else if fewer than k counters, add with count 1; otherwise decrement every counter by 1 and remove zeros. The algorithm is one-pass, O(k) memory. Theoretical guarantee: let n be stream length and r = k. For any item i, the returned estimated count c_hat(i) satisfies 0 ≤ true_count(i) - c_hat(i) ≤ n / (r+1). Any item with true frequency > n/(r+1) must appear among candidates.

Code (Python) with demonstration on [a,b,a,c,a,b,d,a]:

python

def misra_gries(stream, k):
    """
    Misra-Gries algorithm.
    Returns dict: candidate -> approximate count (c_hat).
    Memory: O(k). One pass.
    """
    counters = {}  # item -> count
    for x in stream:
        if x in counters:
            counters[x] += 1
        elif len(counters) < k:
            counters[x] = 1
        else:
            # decrement all counters
            to_delete = []
            for key in list(counters.keys()):
                counters[key] -= 1
                if counters[key] == 0:
                    to_delete.append(key)
            for key in to_delete:
                del counters[key]
    return counters

# Demonstration
stream = ['a','b','a','c','a','b','d','a']
k = 2
candidates = misra_gries(stream, k)
print("Candidates (approx counts):", candidates)

Explanation of demo: For stream length n=8 and k=2, the error bound is at most n/(k+1)=8/3≈2.66. Output might be {'a':3, 'b':1} meaning true_count(a)=4 so true_count - c_hat = 1 ≤ 2.66; true_count(b)=2 → difference 1 ≤ 2.66. Complexity: time O(n * amortized cost per update) — using a dict makes updates O(1) average and decrements O(k) when needed; overall O(nk) worst-case but practical average O(n). Space: O(k).

Notes / Extensions:- To get final exact top-k, a second pass can compute true counts only for candidates.- Use heap or ordered structure if you need faster eviction checks, but classic MG uses simple dict.

MediumTechnical

25 practiced

Implement a Bloom filter in Python for an expected element count n and false positive rate p. Provide add(item) and contains(item) functions and a helper to compute required bit array size m and number of hash functions k. Explain the memory versus false positive trade-off and how hashing is implemented.

Sample Answer

To implement a Bloom filter for expected count n and false positive rate p, we compute the required bit-array size m and number of hash functions k using standard formulas, store bits compactly (bytearray), and use double-hashing (two cryptographic hashes) to generate k hash values deterministically.

python

import math
import hashlib

def optimal_m(n, p):
    """Return number of bits m for expected n items and false positive rate p."""
    if p <= 0 or p >= 1:
        raise ValueError("p must be in (0,1)")
    return int(math.ceil(- (n * math.log(p)) / (math.log(2) ** 2)))

def optimal_k(m, n):
    """Return optimal number of hash functions k (rounded)."""
    return max(1, int(round((m / n) * math.log(2))))

class BloomFilter:
    def __init__(self, n, p):
        self.n = n
        self.p = p
        self.m = optimal_m(n, p)
        self.k = optimal_k(self.m, n)
        self.bytes = bytearray((self.m + 7) // 8)  # compact bit storage

    def _bit_set(self, idx):
        self.bytes[idx >> 3] |= 1 << (idx & 7)

    def _bit_get(self, idx):
        return (self.bytes[idx >> 3] >> (idx & 7)) & 1

    def _hashes(self, item):
        """Generate k indices using double hashing: h(i) = (h1 + i*h2) mod m."""
        if isinstance(item, str):
            item = item.encode('utf-8')
        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):
        for idx in self._hashes(item):
            self._bit_set(idx)

    def contains(self, item):
        return all(self._bit_get(idx) for idx in self._hashes(item))

Key points and reasoning:- m and k formulas minimize false positives given n and p. m grows linearly with n and log(1/p); k ≈ (m/n) * ln2.- Memory vs false positive trade-off: larger m (more bits per element) lowers p. Doubling m roughly squares improvement in p up to diminishing returns; choose m based on acceptable p and available memory.- Hashing: double hashing with two cryptographic hashes is efficient and avoids needing many independent hash functions while maintaining uniformity.- Time: add and contains are O(k) hashes; space: O(m) bits (~m/8 bytes).- Edge cases: ensure n>0, p in (0,1). Bloom filters do not support deletion (unless using a counting Bloom filter) and can have false positives but no false negatives.

MediumTechnical

19 practiced

Estimate memory requirements for training a dataset with 50 million rows and 200 numeric features using float32 on a single machine. Show your calculation and propose concrete engineering approaches if memory is insufficient (out-of-core training, feature selection, sparse storage, sharding across machines).

Sample Answer

Quick estimate (raw dense numeric matrix stored as float32):

- Rows = 50,000,000- Features = 200- float32 = 4 bytes

Memory for feature matrix = 50e6 * 200 * 4 bytes = 40e9 bytes ≈ 40 GB.

Additional memory to budget:- Target column(s): +50e6 * 4 = 0.2 GB- Index/overhead, in-memory dataframe copies (pandas/numpy ops), model structures, minibatch buffers, gradients, and frameworks (TensorFlow/PyTorch): conservatively x2–x3 overhead → total ≈ 80–120 GB.

If 40 GB is just raw data but end-to-end training needs ~80–120 GB, single-machine with e.g. 32–64 GB RAM is insufficient.

Concrete engineering approaches if memory is insufficient:

1) Out-of-core training- Use frameworks that stream data (e.g., TensorFlow tf.data from TFRecord, PyTorch DataLoader with mmap/IterableDataset, scikit-learn partial_fit, Vowpal Wabbit).- Store data in optimized on-disk binary format (TFRecord, Parquet with row-groups) and feed minibatches.

2) Feature selection / dimensionality reduction- Remove low-variance or low-importance features (univariate filters).- Use incremental/online feature selection or PCA/IncrementalPCA to reduce features from 200→e.g. 50 (reduces memory 4x).

3) Sparse storage- If many zeros, store as CSR/CSC or SparseTensor (saves factor proportional to sparsity).- Convert categorical one-hot encodings to hashed feature vectors.

4) Sharding across machines (distributed)- Horizontal sharding: split rows across workers (data-parallel training) using Spark + MLlib, Horovod, or TF distributed strategy.- Vertical sharding: split feature columns if model supports block-wise training.

5) Memory optimizations- Use float16/mixed precision for model and data (float16 halves memory; be careful with numeric stability).- Memory-mapped numpy arrays (np.memmap) to avoid full copies.- Batch processing, generator-based pipelines, and avoid materializing full pandas DataFrames.

Recommendation (practical): Start with out-of-core pipeline + Incremental feature selection. Store data as compressed Parquet or TFRecord, stream minibatches, use mixed precision where safe. If throughput or model complexity requires, move to distributed training (data-parallel) or use a cluster with >128 GB RAM.

EasyTechnical

25 practiced

Implement an LRU cache in Python with O(1) get and put operations and capacity parameter. Use an API class LRUCache with get(key) and put(key, value). Explain how this cache could be used to store computed features in a data pipeline and any thread-safety considerations.

Sample Answer

To implement an O(1) LRU cache we combine a hashmap (dict) for O(1) key lookup with a doubly linked list to track recency (move nodes to head on access, evict from tail). Here's a clean Python implementation:

python

class Node:
    def __init__(self, k, v):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}  # key -> Node
        # dummy head/tail to avoid null checks
        self.head, self.tail = Node(None, None), Node(None, None)
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if not node:
            return -1
        # mark as recently used
        self._remove(node)
        self._add_to_head(node)
        return node.v

    def put(self, key, value):
        node = self.map.get(key)
        if node:
            node.v = value
            self._remove(node)
            self._add_to_head(node)
        else:
            if len(self.map) >= self.cap:
                # evict least recently used (tail.prev)
                lru = self.tail.prev
                self._remove(lru)
                del self.map[lru.k]
            newn = Node(key, value)
            self._add_to_head(newn)
            self.map[key] = newn

Key points:- get and put are O(1) average: dict lookup + constant pointer updates.- Space O(capacity).

Using in a data pipeline:- Cache expensive computed features (e.g., feature vectors per user/session) keyed by ID to avoid recomputation across batches or model scoring steps.- Keep capacity sized to memory budget; use serialization for large objects or store only summaries.- Eviction ensures recent/active entities remain cached.

Thread-safety considerations:- This implementation is not thread-safe. In multi-threaded environments (e.g., concurrent preprocessing or serving), protect get/put with a threading.Lock or use concurrent.futures with locks, or use thread-safe LRU structures (collections.OrderedDict with lock) or external caches (Redis, memcached) for cross-process safety.- Minimize lock contention by using sharded caches or read-write locks if reads dominate.

HardTechnical

19 practiced

Compare label shift and covariate shift: how to detect each in production, how each affects model predictions, and concrete correction methods (importance weighting, EM for label shift, density ratio estimation). Provide relevant equations and discuss common pitfalls when applying corrections.

Sample Answer

Short definitions and consequences- Covariate shift: p_train(x) ≠ p_test(x) but p(y|x) is assumed invariant. Consequence: an estimator minimizing empirical risk under p_train may be biased under p_test because the sample weighting of x changes.- Label shift (prior shift): p_train(y) ≠ p_test(y) but p(x|y) is assumed invariant. Consequence: class posterior p(y|x) changes because p(y) in Bayes’ rule changes, causing miscalibrated predicted probabilities and wrong class prevalences.

Detection in production- Covariate shift: - Train a domain classifier on (x, domain) where domain∈{train,test}. High AUC or calibrated probability s(x)=P(domain=test|x) indicates shift. Then estimate r(x)=p_test(x)/p_train(x) ≈ s(x)/(1−s(x)). - Distribution tests per feature: KS test, MMD, chi-square for categorical features. Multivariate tests or sliced-Wasserstein for complex X.- Label shift: - Compare marginal predicted label distribution q̂_test(y)=E_test[1{ŷ=y}] vs training p_train(y). If model is well-calibrated and p(y|x) unchanged, a difference suggests label shift. - Use a confusion matrix C where C_{ij}=P(ŷ=i | y=j) estimated on validation. If q̂_test ≠ C p_train(y) then label priors likely changed.

Mathematical corrections- Importance weighting for covariate shift: - Reweight training loss by w(x)=p_test(x)/p_train(x). Minimize E_train[w(x) ℓ(f(x),y)] ≈ E_test[ℓ(f(x),y)]. - If using domain classifier s(x): w(x) ≈ s(x)/(1−s(x)).- Label shift via importance on classes: - Under p(x|y) invariance, p_test(y)=π_test, p_train(y)=π_train, and p_test(x)=∑_y p(x|y)π_test(y). - Reweight training examples by w(y)=π_test(y)/π_train(y) so E_test[ℓ]=E_train[w(Y)ℓ].- EM for label shift (Saerens et al. approach): - Initialize π^(0)=π_train. - E-step: for each x, compute posterior under current priors: p^(t)(y|x) ∝ p(y|x)_train × π^(t)(y) / π_train(y) (or use model scores calibrated to p_train). - M-step: π^(t+1)(y)=E_test[p^(t)(y|x)] (average over test X). - Iterate until convergence; it returns π_test estimates.- Density-ratio estimation (direct): - KLIEP, uLSIF, or train logistic regression to discriminate domains. If s(x)=P(domain=test|x) then r(x)=s(x)/(1−s(x)) (up to prior domain class weights). - Fit r(x) directly to minimize divergence without density estimation.

Equations summary- Covariate shift assumption: p_train(y|x)=p_test(y|x), p_train(x)≠p_test(x).- Importance weight: w(x)=p_test(x)/p_train(x).- Label shift relation: p_test(x)=∑_y p(x|y)π_test(y) with π_test(y)=p_test(y).- Confusion-based linear system: q̂_test = C · π_test, solve for π_test (may need regularization).

Practical tips and common pitfalls- Support mismatch: if support_test ⊄ support_train, importance weights blow up; collect new labeled data or restrict domain.- High-variance weights: clip or regularize weights; use normalized weights w̃ = w / E_train[w].- Misidentifying shift type: performing class-reweighting under covariate shift (or vice versa) yields wrong corrections. Use detection tests (domain classifier vs predicted-label drift) before choosing method.- Calibration requirement: EM for label shift and confusion-matrix methods assume p(y|x) or predicted scores calibrated for training priors. If model is miscalibrated, calibrate (Platt/ isotonic) on validation first.- Estimation error from finite data: solve linear system q̂_test = C π with regularization (non-negative least squares, add λI) or Bayesian priors to avoid negative/unrealistic π.- Correlated shifts: real data may violate pure assumptions (both p(x|y) and p(y) change). Consider mixture approaches, collect labeled test data, domain adaptation techniques, or robust training (invariant representations).- Model selection: evaluate corrected model on held-out labeled test data where possible; use importance-weighted validation metrics with variance estimation.

Recommendation- Detect shift with lightweight domain classifier and predicted-label checks.- If label shift holds, use confusion-matrix/EM or solve q̂_test=Cπ with regularization; ensure calibration.- If covariate shift holds, estimate density ratio via domain classifier or KLIEP and apply importance weighting with clipping/regularization.- Always validate corrections with some labeled test samples and monitor stability over time.

Unlock Full Question Bank

Get access to hundreds of Handling Problem Variations and Constraints interview questions and detailed answers.

Join thousands of developers preparing for their dream job.