Arrays, Strings, and Collections Fundamentals Questions

Core knowledge of linear data structures and common collection types and the techniques used to manipulate them. Covers arrays and strings operations such as iteration, indexing, in place modification, reversing, rotating, two pointer techniques, sliding window patterns, searching and basic sorting approaches for these containers, and typical interview problems like finding duplicates and subarray or substring problems. Also covers collection types such as lists, sets, dictionaries and hash tables, when to use each, loop constructs and recursion for traversal, and basic time and space complexity reasoning to choose appropriate data structures and algorithms.

HardTechnical

53 practiced

Given a large multilingual corpus, implement a robust tokenizer normalization function that: (1) normalizes Unicode (NFC/NFKC), (2) strips control characters, (3) maps whitespace to a single space, and (4) returns both tokenized text and a mapping from token index back to original character offsets. Explain why maintaining offsets matters for downstream annotation tasks.

Sample Answer

Approach: normalize text per Unicode grapheme cluster (to preserve mapping), remove control characters, collapse any run of Unicode whitespace to a single ASCII space, then tokenize (Unicode-aware) and create a map from each token index to the original-character [start, end) offsets (byte offsets could be derived similarly). Using the regex third-party package gives robust grapheme and Unicode property support; an alternative is ICU/Python-bindings.

python

import unicodedata
import regex as re

# Pattern: grapheme clusters, control chars, whitespace, tokenization
GRAPHEME = re.compile(r'\X', re.UNICODE)
CONTROL = re.compile(r'[\p{Cc}\p{Cf}]')          # control + format chars
WHITESPACE = re.compile(r'\s+', re.UNICODE)
TOKEN_RE = re.compile(r'\p{L}+\p{M}*|\p{N}+|[^\s\p{L}\p{N}]+', re.UNICODE)

def normalize_and_tokenize_with_offsets(text):
    # Build normalized string while mapping each normalized char -> original char index
    norm_chars = []
    norm_to_orig = []  # for each normalized codepoint index, the original char index it came from
    for i, grapheme in enumerate(GRAPHEME.findall(text)):
        # normalize each grapheme cluster to avoid cross-cluster compaction breaking offsets
        normalized = unicodedata.normalize('NFKC', grapheme)
        for ch in normalized:
            norm_chars.append(ch)
            norm_to_orig.append(i)  # map normalized char to original grapheme index

    s = ''.join(norm_chars)
    # strip control characters (remove them)
    s = CONTROL.sub('', s)
    # map whitespace runs to single ASCII space
    s = WHITESPACE.sub(' ', s).strip()

    # Tokenize on Unicode-aware token regex
    tokens = []
    token_offsets = []  # list of (orig_start_char_index, orig_end_char_index)
    for m in TOKEN_RE.finditer(s):
        tok = m.group(0)
        tokens.append(tok)
        # compute normalized char index range for this token, then map to original
        norm_start = m.start()
        norm_end = m.end()  # end is exclusive
        # map normalized char indices to original grapheme indices
        orig_indices = norm_to_orig[norm_start:norm_end]
        if orig_indices:
            orig_start = orig_indices[0]
            orig_end = orig_indices[-1] + 1  # exclusive
        else:
            orig_start = orig_end = None
        token_offsets.append((orig_start, orig_end))

    return tokens, token_offsets

Key concepts:- Normalize per grapheme cluster to keep mapping between normalized chars and original grapheme indices (avoids normalization combining chars across boundaries).- Remove control chars then collapse whitespace to a single space for consistent token boundaries.- Use Unicode-aware token regex so multilingual scripts (CJK, accented Latin, etc.) are handled.

Complexity: O(n) time and O(n) space (n = input length) — single pass to build mapping and another for tokenization.

Edge cases:- Normalization can change lengths (ligatures → multiple chars); grapheme-based mapping preserves meaningful offsets.- Combining marks, ZWJ sequences, and surrogate pairs are handled by grapheme segmentation (regex \X).- If downstream needs byte offsets (UTF-8), map original grapheme indices to byte offsets separately.

Why offsets matter:- Downstream annotation tasks (NER, QA, token classification) require mapping model tokens back to original text spans to align labels, display highlights, or compute evaluation metrics. Incorrect offsets break training labels, degrade evaluation, and corrupt human review/UIs. Accurate offsets ensure annotations remain consistent after normalization/tokenization.

Alternatives:- Use ICU (PyICU) or HuggingFace tokenizers for production-grade, faster implementations and to obtain byte-level offsets directly.

HardTechnical

44 practiced

Given a long array of floating activations from a model run, design an efficient algorithm to detect plateau regions where values remain within epsilon for at least L consecutive positions (useful for detecting saturation or vanishing gradients). Provide an O(n) algorithm and discuss numerical stability for floats and noise tolerance.

Sample Answer

Approach (O(n)): maintain two monotonic deques to track the sliding-window minimum and maximum so you can check in O(1) whether max - min <= epsilon for any window. Scan once with a right pointer; when window length >= L and condition holds, record a plateau start at right-L+1 and optionally extend the window while condition remains true. This is linear because each element is pushed/popped at most once from each deque.

python

from collections import deque
import math

def detect_plateaus(arr, eps, L):
    """
    Returns list of (start, end) indices (inclusive) of plateau regions where
    for every index i..j the values remain within eps and length >= L.
    O(n) time, O(L) worst-case auxiliary (deques).
    """
    n = len(arr)
    if L <= 0 or n < L:
        return []
    min_q = deque()  # stores indices, arr[idx] increasing
    max_q = deque()  # stores indices, arr[idx] decreasing
    plateaus = []
    left = 0
    for right, v in enumerate(arr):
        # ignore NaN/inf: treat them as breakers
        if not (math.isfinite(v)):
            min_q.clear(); max_q.clear(); left = right + 1
            continue

        # maintain min deque (increasing)
        while min_q and arr[min_q[-1]] >= v:
            min_q.pop()
        min_q.append(right)
        # maintain max deque (decreasing)
        while max_q and arr[max_q[-1]] <= v:
            max_q.pop()
        max_q.append(right)

        # shrink left until window satisfies numeric validity (we keep left as is;
        # but we need to ensure left points to earliest index in current valid block)
        # Slide left forward only if left beyond deque heads
        while left <= right and (arr[max_q[0]] - arr[min_q[0]] > eps):
            # advance left to remove influence
            if min_q and min_q[0] == left:
                min_q.popleft()
            if max_q and max_q[0] == left:
                max_q.popleft()
            left += 1

        # if current window length >= L, record plateau(s)
        if right - left + 1 >= L:
            # record a plateau starting at left and ending at right.
            # To avoid duplicates when we slide right, only append when right expands.
            plateaus.append((left, right))
            # optional: to return maximal disjoint intervals, you can merge/extend later
    return merge_intervals(plateaus)

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort()
    merged = [list(intervals[0])]
    for s,e in intervals[1:]:
        if s <= merged[-1][1] + 1:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s,e])
    return [(a,b) for a,b in merged]

Key concepts:- Monotonic deques support O(1) min/max in a sliding window; each index enqueued/dequeued at most once.- Use absolute or relative epsilon: use abs(max-min) <= eps for absolute; for values spanning magnitudes use relative: (max-min) <= eps * max(1, |mean|).- Handle NaN/Inf as boundaries that break plateaus.Numerical stability & noise tolerance:- Floating noise can create tiny fluctuations; choose eps >= typical numeric noise or pre-smooth (low-pass, moving average, median filter) before detection.- Use fused operations and avoid subtracting nearly equal large numbers; when using relative tolerance compare normalized difference (e.g., (max-min)/max_abs).- Consider hysteresis: require condition hold for L and allow up to k intermittent violations (tolerance window) to reduce false negatives.Complexity: O(n) time, O(L) worst-case space for deques.Edge cases: constant arrays, sequences with NaN/Inf, varying scale — choose absolute vs relative eps accordingly.

HardSystem Design

53 practiced

You need to batch and pad variable-length token sequences efficiently for training. Design data structures and an algorithm to create padded batches that minimize padding tokens while supporting fast tensor creation on GPU. Discuss bucketing, sorting by length, ragged tensors, and the trade-offs for shuffling and convergence in training.

Sample Answer

Requirements and constraints:- Minimize padding waste (reduce tokens per batch).- Maintain high GPU throughput (large contiguous tensors, minimal CPU-GPU copy fragmentation).- Support shuffling for SGD convergence but avoid excessive padding variance.- Handle variable-length sequences (text) efficiently at scale.

High-level design:1. Precompute sequence lengths and keep dataset as (id, length, serialized-example).2. Bucketing: define length buckets (e.g., powers-of-two or fixed-width ranges). Assign each example to a bucket by length.3. Within each bucket, sort or partially sort by length (descending). Create batches by grouping contiguous examples until batch token budget is reached (max_tokens_per_batch), not just max_examples.4. For GPU-friendly tensors, create dense padded tensors per batch: allocate [batch_size, max_len_in_batch] contiguous buffer, fill from CPU using vectorized ops, then one async memcpy to GPU.5. Optionally support ragged tensors or packed sequences (lengths + values) when framework supports them (PyTorch's PackedSequence or TF RaggedTensor) to avoid full padding — use when model/layer supports it (RNN pack_padded_sequence) but note many transformer ops expect dense tensors.

Algorithm (batch creation):- Shuffle bucket order each epoch to keep stochasticity.- For each bucket: - Option A (tight packing): sort by length descending, repeatedly take smallest set of examples where sum(lengths) ≤ max_tokens. This minimizes padding. - Option B (fast approximate): maintain length-quantiles and greedy-fill until token budget reached.- Emit batches as (padded_tensor, lengths, attention_mask, ids).

Data structures:- Bucket index: array of lists of example pointers.- Length-sorted arrays per bucket (for fast windowing).- Batch descriptor: {start_idx, count, max_len, total_tokens} for zero-copy assembly.

Trade-offs:- Bucketing + sorting reduces padding substantially but reduces per-example randomness. Shuffle bucket order and shuffle inside small windows to restore stochasticity.- Fine-grained buckets lower padding but increase metadata and potential imbalance; coarse buckets increase padding but simplify IO.- Ragged/packed avoids padding but can break kernel fusion, reducing throughput; many GPU kernels are optimized for dense tensors.- Using max_tokens_per_batch instead of fixed batch_size keeps GPU memory utilization steady.- For convergence: small loss of randomness from bucketing can be mitigated by epoch-wise reshuffle, bucket boundary jittering, and mixing a fraction of cross-bucket examples.

Practical tips:- Choose bucket scheme based on length distribution (visualize histogram).- Use asynchronous prefetching and pinned memory for CPU→GPU memcpy.- Profile: compute tokens/second and memory utilization; tune max_tokens_per_batch and bucket sizes.- Implement deterministic seeding for reproducibility.

HardTechnical

39 practiced

Design a weighted reservoir sampling algorithm to sample k items from an unbounded stream where each item has a positive weight and selection probability should be proportional to weight. Provide the algorithm, prove correctness at high level, and discuss numerical stability when weights vary by many orders of magnitude.

Sample Answer

Approach (brief): use the Efraimidis–Spirakis weighted-reservoir method. For each arriving item i with positive weight wi, draw u ~ Uniform(0,1) and compute a priority/key. Two numerically-equivalent choices:- key = u^(1/wi) and keep top-k keys (largest).- numerically preferred: key = -ln(u) / wi (i.e. exponential/Gumbel trick) and keep k smallest keys.

Algorithm (Python):

python

import math
import heapq
import random

def weighted_reservoir(stream, k):
    """
    stream: iterable of (item, weight)
    returns k sampled items with probability proportional to weight
    """
    # max-heap of size k storing (-key, item) so top is largest key
    heap = []
    for item, w in stream:
        if w <= 0:
            continue
        # stable key: draw exponential variate ~ Exp(rate = w) by -ln(u)/w
        key = -math.log(random.random()) / w
        # we want k smallest keys -> store negative to use python's min-heap as max-heap
        if len(heap) < k:
            heapq.heappush(heap, (-key, item))
        else:
            if key < -heap[0][0]:
                heapq.heapreplace(heap, (-key, item))
    return [it for (_, it) in heap]

High-level correctness proof:- For any two items i,j, let Xi = -ln(Ui)/wi (independent exponentials with rates wi). P(Xi < Xj) = wi / (wi + wj). Thus ranking by Xi gives pairwise odds proportional to weights. For selecting k smallest Xi, probability an item is among the k smallest equals its weight proportion relative to the population — formalized via order-statistic properties of independent exponentials: selection is equivalent to sampling without replacement with inclusion probabilities proportional to weights.

Numerical stability and practical notes:- u^(1/w) is unstable when w is large/small (underflow/rounding); using -ln(u)/w avoids underflow because -ln(u) is ~Exp(1) and dividing by w stays in magnitude similar to 1/w. Still watch extremes: - Very small w -> key can be enormous; compare keys using floats may lose precision. Very large w -> key near zero; distinguish near-zero keys requires precision. - Use double or long double if available. If weights span >~1e308 or <~1e-308, rescale weights by a common factor before processing (scaling cancels out since keys depend on relative weights). - If streaming across shards, combine by keeping top-k keys and merging heaps.- Complexity: O(n log k) time, O(k) memory.- Alternate: Poisson/priority sampling or A-Res variations; core practical recommendation: use -ln(u)/w with a size-k heap and rescale weights when extreme magnitudes appear.

MediumTechnical

43 practiced

Given two strings s and p, implement a function find_anagrams(s: str, p: str) -> List[int] in Python that returns starting indices of p's anagrams in s. Use a sliding-window and frequency counts to achieve O(n) time. Explain how this sliding-window pattern is analogous to finding n-gram matches in token streams.

Sample Answer

Approach:Use a fixed-size sliding window of length len(p) across s and maintain frequency counts for characters in p and for the current window. Update the window counts incrementally (add right char, remove left char) and compare counts — equality indicates an anagram start. Use an array of size 26 for lowercase letters or a defaultdict/Counter for general chars. This works in O(n) time.

python

from collections import Counter
from typing import List

def find_anagrams(s: str, p: str) -> List[int]:
    if len(p) > len(s):
        return []

    p_count = Counter(p)
    window_count = Counter(s[:len(p)])
    res = []
    if window_count == p_count:
        res.append(0)

    for i in range(len(p), len(s)):
        start = i - len(p)
        # add new char
        window_count[s[i]] += 1
        # remove old char
        window_count[s[start]] -= 1
        if window_count[s[start]] == 0:
            del window_count[s[start]]
        # compare counts
        if window_count == p_count:
            res.append(start + 1)
    return res

Key points:- We maintain counts incrementally rather than recomputing for each window (O(1) update amortized).- Counter equality checks are O(k) where k is alphabet size in practice; with fixed alphabets this is O(1) per comparison.

Time & Space complexity:- Time: O(n) where n = len(s) (each character added/removed once; comparisons constant for fixed alphabet).- Space: O(k) for frequency dictionaries (k = distinct characters, often <= 26 or vocabulary size).

Edge cases:- len(p) > len(s): return []- empty p: define behavior (here treat as no matches)- non-lowercase or Unicode: use Counter (works generally) but alphabet size affects constant factors.

Analogy to n-gram matching in token streams:- An n-gram is a contiguous token window of size n. Finding identical n-grams across streams is the same pattern: slide a fixed-size window over tokens, maintain token frequency or exact token sequence, and compare. For unordered-match (bag-of-tokens) we use frequency counts (like anagrams). For ordered-match (exact n-gram) we compare sequences or rolling hashes. The sliding-window approach enables streaming, O(n) processing, and incremental updates — essential in NLP pipelines for large corpora or real-time token streams.

Unlock Full Question Bank

Get access to hundreds of Arrays, Strings, and Collections Fundamentals interview questions and detailed answers.

Join thousands of developers preparing for their dream job.