Recognizing Patterns and Selecting Algorithms Questions

Ability to recognize problem patterns and know which algorithm/data structure is appropriate. Includes pattern matching like 'this looks like a sliding window problem' or 'this is a backtracking problem'.

MediumTechnical

83 practiced

You're building an entity recognition system where entities can overlap and nested structures appear. Recognize whether greedy tagging, dynamic programming (e.g., CRF/Viterbi), or a graph-based parsing approach is more appropriate. Explain your decision with complexity estimates and consequences for inference and training.

Sample Answer

Short answer: choose a graph/span-based parsing approach (e.g., span classifier or hypergraph/constituency-style parser) when you must handle overlapping and nested entities. Greedy tagging is too limited; standard linear-chain CRFs/Viterbi assume a single label per token position and can’t represent overlaps/nesting without awkward engineering.

Why:- Greedy token tagging (O(n) per example) is fast and simple but cannot represent overlapping spans or true nesting (it produces one label sequence). It’s acceptable only if overlaps are rare and you can accept heuristics (stacked passes, left-to-right extraction), but this leads to many errors and inconsistent outputs.- Linear-chain CRF + Viterbi: inference is O(n · T^2) for T states and handles sequence-level dependencies well, but still enforces a single state per token so no overlaps/nesting. You can extend with layered CRFs (multiple passes) or hypergraph CRFs, but that increases complexity and label engineering.- Graph/span-based parsing: treat entities as spans or a hierarchical constituency graph. Two practical families: - Span classification: enumerate O(n^2) spans and score with a model (biaffine or MLP). Complexity: O(n^2) scoring; selecting spans can be O(n^2 log n) if you sort by score or use thresholding. Training is simple (binary cross-entropy per span or multi-class). Works well for overlapping spans (multiple positive spans can share tokens) and nested entities (spans can contain spans). - Chart/CKY-style constituency parsing or hypergraph CRF: can recover hierarchical structure with exact inference; worst-case O(n^3) (classical CKY) or depends on grammar size. Hypergraph CRF gives exact marginals but training/inference cost and memory are higher.

Consequences for inference & training:- Inference latency: greedy ≪ linear-chain CRF ≪ span O(n^2) ≪ chart O(n^3). For real-time systems prefer optimized span models with pruning/beam.- Training complexity: span models require O(n^2) labeled span supervision (or distant supervision); hypergraph models need dynamic programming over many states and more memory. Data annotation must include nested/overlapping spans.- Model complexity & performance: span/graph models better expressivity and accuracy for complex entity phenomena; they allow multi-label overlapping spans naturally. They also integrate easily with contextual encoders (BERT → span representations).- Engineering trade-offs: span methods are easier to implement and scale; chart/hypergraph approaches are more principled for deep nesting but heavier.

Recommendation: use a neural span-based model (BERT encoder → span pooling → biaffine/multi-class scorer) with pruning (max span length, score threshold, or candidate pre-filtering). If you need full hierarchical structure (constituency-style) and correctness guarantees, use a chart parser/hypergraph CRF despite higher O(n^3) cost.

HardTechnical

82 practiced

As a staff AI engineer, you must balance a product requirement for high throughput recommendations, a legal constraint requiring interpretability, and a data team's constraint to minimize per-query joins. Describe how you would recognize the conflicting-constraints pattern, lead the team to select algorithms and an architecture that balances latency, interpretability (e.g., rule-based or linear models), and data access costs, and present a rollout plan for a hybrid solution.

Sample Answer

Situation: Our product team pushed for higher-throughput personalized recommendations, legal required interpretability for decisions affecting users, and the data team warned that per-query joins would blow up latency and cost.

Task: As staff AI engineer, I needed to resolve these conflicting constraints and deliver a design that balanced latency, interpretability, and minimal data access.

Action:- I convened stakeholders (product, legal, data, infra, ML) and mapped constraints into measurable SLOs: 50ms p99 latency, human-explainable decision trace, and ≤1 join per request.- Framed the conflict as a “conflicting-constraints” pattern: throughput vs interpretability vs data-cost.- Proposed a hybrid architecture: - Lightweight, interpretable first-stage scorer (rule-based + sparse linear model) using denormalized features served from a Feature Store / online store (pre-joined, per-user feature blob) to produce top-K candidates at <10ms. - Second-stage re-ranker (optional) using a moderately expressive model (gradient-boosted trees or small transformer) operating asynchronously or on a batched stream for top-K refinement where legal allows; this stage logs full explanations and can be gated. - Feature engineering: precompute joins offline into denormalized feature vectors (feature blobs or vector table) refreshed frequently (minutes/hour) to avoid per-query joins. - Explainability: keep coefficients/rule traces for first-stage; for second-stage, provide surrogate linear explanations (LIME/SHAP) and store provenance.- Led a decision matrix comparing options (pure rules, linear only, deep models) against SLOs and legal acceptance; chose hybrid to maximize throughput and interpretability while enabling higher accuracy later.

Rollout plan:1. Implement first-stage interpretable scorer behind prod API using denormalized feature store; unit tests and interpretation unit tests.2. Canary (1% traffic) with full logging of decisions, explanation payloads, latency, and cost metrics; legal reviews of explanation format.3. A/B test adding the second-stage re-ranker on a fraction of traffic, measuring CTR, fairness, and explanation consistency; ensure re-ranker only applied when permitted.4. SLO gating: only expand rollout if p99 latency and join-cost remain within thresholds and legal accepts explanations.5. Monitoring/observability: real-time dashboards for latency, cost, explainability disputes, and data freshness; periodic audits and rollback plan.6. Documentation and runbook for legal/data queries and model updates.

Result / Learning: This approach protects legal requirements and data constraints while allowing incremental accuracy improvements. The hybrid pattern provides predictable latency and clear explanations, and decoupling via precomputed feature store eliminated per-query joins—an approach that stakeholders accepted because trade-offs were explicit and measured.

EasyTechnical

143 practiced

Implement a function in Python that, given a list of floating-point sensor measurements and an integer k, returns the maximum average of any contiguous subarray of length k. Your implementation must run in O(n) time and use O(1) extra space. Use the signature: def max_average_subarray(nums: List[float], k: int) -> float: Handle edge cases where k > len(nums) appropriately.

Sample Answer

To solve this, use a sliding-window of fixed size k: keep the sum of the current window, slide one element at a time updating the sum in O(1), and track the maximum average. This is O(n) time and O(1) extra space.

python

from typing import List

def max_average_subarray(nums: List[float], k: int) -> float:
    """
    Returns the maximum average of any contiguous subarray of length k.
    Raises ValueError if k <= 0 or k > len(nums).
    """
    n = len(nums)
    if k <= 0:
        raise ValueError("k must be positive")
    if k > n:
        raise ValueError("k cannot be greater than number of elements")

    # initial window sum
    window_sum = sum(nums[:k])
    max_sum = window_sum

    # slide the window across the array
    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]  # update sum in O(1)
        if window_sum > max_sum:
            max_sum = window_sum

    return max_sum / k

Key points:- Uses fixed-size sliding window; only one running sum stored (O(1) space).- Time complexity O(n): each element visited once after initial sum.- Handles floating-point values naturally.Edge cases:- k == n returns average of entire list.- k <= 0 or k > len(nums) raises ValueError (you can alternatively return None).Alternative: keep running average but that’s numerically equivalent; sliding-window is simplest and most efficient.

EasyTechnical

126 practiced

Explain how to recognize whether a problem calls for a greedy algorithm versus dynamic programming. Provide concrete criteria (e.g., optimal substructure, overlapping subproblems, matroid properties) and give an AI example where greedy is suboptimal and dynamic programming is required to find the true optimum.

MediumTechnical

128 practiced

Implement a Count-Min Sketch in Python to estimate frequencies of items in a data stream, with methods add(item) and estimate(item). Include parameters to control error (epsilon) and failure probability (delta). Explain how to choose width and depth for desired error bounds.

Sample Answer

To implement a Count–Min Sketch (CMS), use an array of d rows and w columns. Each row uses an independent hash to map an item to a column; add increments counts in each row, and estimate returns the minimum across rows. For error bounds: choose width w = ceil(e / epsilon) (commonly w = ceil(e / epsilon)) and depth d = ceil(ln(1/delta)). This gives with probability 1-delta an estimate within true_count + epsilon * total_count.

python

import math
import random

class CountMinSketch:
    def __init__(self, epsilon=0.01, delta=1e-3, seed=None):
        """
        epsilon: additive error guarantee (as fraction of total count)
        delta: failure prob that estimate exceeds error bound
        """
        if seed is not None:
            random.seed(seed)
        # width and depth per standard CMS bounds
        self.w = int(math.ceil(math.e / epsilon))
        self.d = int(math.ceil(math.log(1 / delta)))
        self.total = 0
        # initialize d x w counters
        self.table = [[0] * self.w for _ in range(self.d)]
        # generate pairwise-independent-ish hash salts
        self.salts = [random.randrange(1 << 30) for _ in range(self.d)]

    def _hash(self, item, i):
        # combine builtin hash with salt, ensure non-negative
        h = hash(item) ^ self.salts[i]
        return (h & 0x7FFFFFFF) % self.w

    def add(self, item, count=1):
        """Add count occurrences of item"""
        for i in range(self.d):
            self.table[i][self._hash(item, i)] += count
        self.total += count

    def estimate(self, item):
        """Return estimated frequency (upper bound)"""
        vals = [self.table[i][self._hash(item, i)] for i in range(self.d)]
        return min(vals)

Key points:- Width w ≈ e/epsilon gives additive error ≤ epsilon * total_count.- Depth d ≈ ln(1/delta) gives failure prob ≤ delta (use median-of-hashes via min).- Time per add/estimate: O(d). Space: O(w * d).Edge cases:- Very small epsilon leads to large memory; choose epsilon/delta to fit resources.- Hash collisions cause overestimation but never underestimation.Alternatives:- Use conservative update (increment only minimum counters) to reduce overestimation.- Use better hash functions (e.g., MurmurHash3) or pairwise-independent hashing for stronger guarantees.

Unlock Full Question Bank

Get access to hundreds of Recognizing Patterns and Selecting Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.