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

67 practiced

Implement in Python a function longest_substring_k_distinct(s: str, k: int) -> int that returns the length of the longest substring containing at most k distinct characters. Your solution must be O(n). Show example: s='eceba', k=2 -> 3.

Sample Answer

We can solve this with a sliding-window + hashmap tracking character counts. Expand the right end, add chars; when distinct count > k, shrink left until it’s <= k. This is O(n) time and O(min(n, alphabet)) space.

python

def longest_substring_k_distinct(s: str, k: int) -> int:
    """
    Return length of longest substring with at most k distinct characters.
    O(n) time, O(min(n,|alphabet|)) space.
    """
    if k == 0 or not s:
        return 0

    left = 0
    freq = {}
    max_len = 0

    for right, ch in enumerate(s):
        freq[ch] = freq.get(ch, 0) + 1

        # shrink window until we have at most k distinct chars
        while len(freq) > k:
            left_ch = s[left]
            freq[left_ch] -= 1
            if freq[left_ch] == 0:
                del freq[left_ch]
            left += 1

        # window [left, right] is valid
        max_len = max(max_len, right - left + 1)

    return max_len

# Example
# s = 'eceba', k = 2 -> longest is 'ece' length 3
print(longest_substring_k_distinct('eceba', 2))  # 3

Key points:- We maintain counts to know when a character can be removed.- Each character enters/exits window at most once => O(n) time.- Space is number of distinct chars in current window (≤ alphabet size).

Edge cases:- k = 0 -> 0- empty string -> 0- k >= len(set(s)) -> len(s) (function naturally handles this).

EasyTechnical

70 practiced

Metric selection pattern: when should you prioritize ROC AUC, Precision-Recall AUC, F1, or a task-specific business metric? Provide concrete examples mapping illustration (fraud detection, ad click prediction, medical diagnosis) and explain how class imbalance and cost asymmetry influence choice.

Sample Answer

Short answer: pick the metric that reflects the decision you’ll make in production. Use ROC AUC for balanced classes and when ranking across thresholds matters; use Precision-Recall AUC (PR AUC) when positive class is rare; use F1 when you need a single operating-point trade-off between precision and recall; and prioritize a task-specific business metric when costs or downstream impacts dominate.

Why class imbalance matters:- ROC AUC uses true/false positive rates and can be overly optimistic with rare positives because many true negatives inflate specificity.- PR AUC focuses on precision (positive predictive value) vs. recall — it is sensitive to performance on the rare positive class.

Why cost asymmetry matters:- If false positives and false negatives have different costs, choose a metric or loss that weights them (e.g., cost-weighted accuracy, expected monetary loss) or optimize for business KPIs directly.

Concrete mappings:- Fraud detection (very imbalanced, high cost of missed fraud and moderate cost of false alarms): prioritize PR AUC to judge ranking of fraud scores; choose an operating point by maximizing expected monetary value or recall at an acceptable precision (e.g., recall at precision ≥ 0.8). Use business metric = expected fraud loss reduction after human review costs.- Ad click prediction (sparse clicks, objective is maximizing revenue): use PR AUC for model ranking but ultimately optimize downstream metric like click-through-rate lift or revenue per mille (RPM) in A/B tests; calibrate probabilities for bidding strategies.- Medical diagnosis (rare but high-cost false negatives): prioritize high recall (sensitivity); use F1 only if you need balance, otherwise optimize recall at constrained false-positive rate and evaluate using cost-based clinical outcome metric (e.g., lives saved, unnecessary procedures).

Practical guidance:- Start with PR AUC for imbalanced positives, ROC AUC for balanced problems or when negatives matter too.- Always translate model scores into expected business value and validate with business metrics (A/B tests, cost-sensitivity analysis).- Report multiple metrics (ROC AUC, PR AUC, precision@k, recall@k, and a business metric) so stakeholders can choose thresholding aligned with operational costs.

EasyTechnical

75 practiced

Explain the two-sum pattern and when a hashmap approach is preferable to sorting plus two-pointers. In your answer, discuss time and space complexity trade-offs and practical considerations in ML pipelines such as preserving element order, streaming input, and memory constraints.

Sample Answer

The two-sum pattern asks: given an array and a target, find two elements whose values sum to the target. Two common approaches are a hashmap (value → index) and sorting + two-pointers.

Hashmap approach:- Idea: single pass; for each value x, check if target - x exists in the map; if not, store x with its index.- Time: O(n) average, Space: O(n).- Pros: preserves original indices/order (you can return original positions), works naturally on unsorted data, and is single-pass so good for streaming (maintain the map incrementally).- Cons: extra memory; worst-case hash collisions could degrade but rare.

Sorting + two-pointers:- Idea: sort array (keeping value+original index if you need indices), then use low/high pointers to search in O(n) after sort.- Time: O(n log n) due to sort, Space: O(1) or O(n) if you must keep original indices.- Pros: lower additional memory if in-place sort allowed; simpler for small memory budgets when indices aren’t required.- Cons: destroys original order unless you track indices; not suitable for streaming; higher latency for large batches because of sort cost.

Practical ML pipeline considerations:- Preserving element order/indices: hashmap is preferable when downstream features require original positions (e.g., join back to rows).- Streaming input: use hashmap or windowed hash structure; two-pointers requires the full dataset.- Memory constraints: if RAM is tight and dataset fits external storage, sort-on-disk or external merge sort may be better; alternatively, use sampling, hashing with limited-size caches, or approximate methods.- Feature-engineering: for dedup or pair-feature creation in large datasets, consider distributed hashing (e.g., Spark map-side combine) and monitor map sizes to avoid OOM; use spill-to-disk or chunking.In summary: prefer hashmap for one-pass, order-preserving, streaming-friendly needs; prefer sorting when memory is constrained and you can accept O(n log n) time and loss of original order or can efficiently track indices.

EasyTechnical

69 practiced

Compare K-fold cross-validation and bootstrap resampling for model evaluation. Explain patterns that make you prefer one over the other in ML experiments, including sample size, variance estimation, bias, computational cost, and applicability to time-series.

Sample Answer

K-fold cross-validation and bootstrap are both resampling methods for assessing model performance, but they have different strengths and trade-offs.

Definitions & basic behavior:- K-fold CV: split data into K disjoint folds; train on K-1 folds and validate on the held-out fold, repeat K times and average. Common choices: K=5 or 10.- Bootstrap: sample with replacement to create many bootstrap samples (typically B=100–1000); train on each bootstrap sample and evaluate on the out-of-bag (OOB) observations or on original data.

When I prefer K-fold CV:- Sample size moderate-to-large: K-fold gives low-bias estimates of generalization error when dataset is reasonably sized and IID.- Computational budget moderate: K folds require K training runs (cheap relative to many bootstraps).- Want stable point estimate of performance and easy stratification (stratified K-fold for class balance).- Not for time-series unless using time-aware variants (rolling/blocked CV).

When I prefer bootstrap:- Small sample sizes: bootstrap can better exploit limited data by sampling with replacement and producing many resamples; useful for estimating sampling variability.- Need robust variance/confidence intervals: bootstrap produces empirical distributions of metrics (useful for CI on accuracy, AUC, etc.).- When model is unstable and you want uncertainty estimates (bias-corrected and accelerated bootstrap helps).- More computationally expensive (B models), but parallelizable.

Bias vs variance:- K-fold (especially large K like LOOCV) tends to have low bias but higher variance for LOOCV; commonly K=5/10 balances bias/variance.- Bootstrap can have lower variance in small samples for estimates of variability, but naive bootstrap estimates of prediction error can be biased; adjustments exist (.632, .632+).

Computational cost:- K-fold: O(K) trainings. Bootstrap: O(B) trainings, typically B » K, so higher cost.- Both parallelizable; choose B/K based on compute.

Time-series applicability:- Standard K-fold and bootstrap assume IID. For time-series use blocked/time-series CV (forward chaining/rolling origin) to preserve temporal order. Bootstrap variants for time-series exist (moving block bootstrap) but are more complex.

Practical rule-of-thumb:- Use stratified 5–10 fold CV for typical supervised problems with reasonable data.- Use bootstrap when dataset is small and you need uncertainty estimates or CIs.- For time-series, use time-aware CV or block bootstrap—not standard implementations.

MediumTechnical

87 practiced

Implement a Python class SlidingWindowMax that supports push(value: int, timestamp: int) and get_max(current_timestamp: int) returning the maximum value within the window of width W seconds. Design for amortized O(1) push and get_max and assume timestamps are non-decreasing.

Sample Answer

Approach:Maintain a monotonic deque (values in decreasing order) storing pairs (value, timestamp). On push, evict from the back all elements with value < new value (they'll never be needed). On get_max, evict expired elements from the front whose timestamp <= current_timestamp - W. Timestamps are non-decreasing which gives amortized O(1) operations.

python

from collections import deque

class SlidingWindowMax:
    def __init__(self, W: int):
        """
        W: window width in seconds (inclusive of timestamps > current_timestamp - W)
        """
        self.W = W
        self.deque = deque()  # stores tuples (value, timestamp) with non-increasing values

    def push(self, value: int, timestamp: int) -> None:
        """
        Push new value with non-decreasing timestamp.
        Amortized O(1).
        """
        # Remove smaller values from back; they can't be max while this new value exists
        while self.deque and self.deque[-1][0] < value:
            self.deque.pop()
        self.deque.append((value, timestamp))

    def get_max(self, current_timestamp: int) -> int:
        """
        Return max value within window (current_timestamp - W, current_timestamp] or
        adjust condition per inclusive definition. Raises ValueError if empty.
        Amortized O(1).
        """
        expire_before = current_timestamp - self.W
        # Evict expired entries from front
        while self.deque and self.deque[0][1] <= expire_before:
            self.deque.popleft()
        if not self.deque:
            raise ValueError("No elements in window")
        return self.deque[0][0]

Key points:- Monotonic deque keeps candidate maxima only.- Timestamps non-decreasing ensures each element is pushed/popped at most once → amortized O(1).Time complexity: push O(1) amortized, get_max O(1) amortized.Space: O(n) worst-case where n is number of items in current window.Edge cases:- Empty window → raise or return sentinel as desired.- Equal values: keep them (use <= in comparisons if you prefer dropping equal older items).Alternative:- Use a max-heap with lazy deletion (higher cost), or segment tree if random timestamps.

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.