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.

HardSystem Design

44 practiced

Design a deduplication pipeline for multiple large CSV datasets containing user records. Specify steps for ingestion, hashing fingerprints, chunked external sorting or sharding, handling collisions, and ensuring determinism across reruns. Discuss memory, disk IO, and how to scale horizontally.

Sample Answer

Requirements:- Remove duplicates across many large CSVs (dozens–hundreds of GB), deterministic results across reruns, handle near-duplicates vs exact duplicates, low memory footprint, horizontally scalable.

High-level pipeline:1. Ingestion- Stream CSVs from object store (S3/GCS) or message queue; read in blocks (e.g., 64–256 MB) to avoid OOM.- Validate and normalize fields (trim, lowercase, canonical date formats) to make hashing deterministic.

2. Fingerprinting (hashing)- Construct a canonical string for each record using selected key fields (order fixed).- Use a fast non-cryptographic 128-bit hash (e.g., xxHash3 or FarmHash) to create fingerprint; include a version salt/version-id to ensure determinism when logic changes.- Emit (fingerprint, shard_id, serialized record pointer/offset).

3. Sharding / Chunked external sort- Two options: a) Hash-based sharding: mod fingerprint → N shards written to disk/object store. Each shard fits into memory or is externally sorted. b) External sort per shard: within a shard, perform external sort by fingerprint using multi-way merge (read/write temporaries).- Both ensure duplicates map to same shard so dedupe is local.

4. Deduplication & collision handling- Within a shard, for identical fingerprints: - Compare full canonicalized records byte-by-byte to confirm match (protects against hash collisions). - If near-duplicate logic required, compute token-based similarity (Jaccard, edit distance) or ML model to decide merge.- Keep deterministic tie-breaker: e.g., pick record with latest updated_at, or lowest source_priority + earliest ingestion_order (ingestion_order must be stable).

5. Output and metadata- Write deduped records to final sink; emit provenance and chosen-record metadata.- Store manifest with shard checksums, version salt, and processing parameters for reproducibility.

Memory, Disk IO, and Performance:- Memory: limit per worker to in-memory shard buffer size; use streaming/parquet row groups to control footprint.- Disk IO: write/read N shard files once; external sort causes O(n log n) I/O but bounded by shard size. Prefer sequential IO (append, large block reads) to minimize seeks.- Use compression (snappy) to reduce IO; tune buffer sizes to maximize throughput.

Horizontal scaling:- Use a distributed processing framework (Spark/Flink/Dask) or orchestrate workers that read input partitions and write shard files to shared storage.- Scale shards (N) with cluster size; increase N to reduce per-shard memory and parallelize more.- Use consistent hashing + leader election for shard assignment to avoid hotspots.

Determinism across reruns:- Fix canonicalization rules, hash function/version, shard count, chunk sizes, and stable tie-breakers; store these in pipeline manifest.- Make ingestion order deterministic by using stable sorting of input file names and offsets or capturing stable offsets from source.

Trade-offs:- Larger N reduces memory but increases metadata/files. Choosing hash size affects collision risk; confirm collisions via full-record compare.- External sort costs IO but is simple and deterministic; streaming hash-shard reduce sorting cost.

This pipeline provides robust, scalable, and reproducible deduplication suitable for downstream modeling and feature engineering.

HardTechnical

42 practiced

Implement find_median_sorted_arrays(A, B) in Python that returns the median of two sorted arrays in O(log(min(m, n))) time. Explain partitioning strategy, edge cases when partitions are empty, and how to handle even total length.

Sample Answer

To solve this in O(log min(m,n)) we binary-search the smaller array to find a partition such that left halves from both arrays contain exactly half (or half ±1) of total elements and every element on left <= every element on right. Median is max(left) or average of max(left) and min(right) depending on parity.

python

def find_median_sorted_arrays(A, B):
    # Ensure A is the smaller array
    if len(A) > len(B):
        A, B = B, A
    m, n = len(A), len(B)
    total = m + n
    half = (total + 1) // 2  # left side size

    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2        # A's left size
        j = half - i              # B's left size

        A_left = A[i-1] if i > 0 else float("-inf")
        A_right = A[i] if i < m else float("inf")
        B_left = B[j-1] if j > 0 else float("-inf")
        B_right = B[j] if j < n else float("inf")

        if A_left <= B_right and B_left <= A_right:
            # correct partition
            if total % 2:  # odd
                return max(A_left, B_left)
            else:          # even
                return (max(A_left, B_left) + min(A_right, B_right)) / 2.0
        elif A_left > B_right:
            hi = i - 1
        else:
            lo = i + 1

    raise ValueError("Input arrays not sorted or invalid")

Key points:- Partition sizes: i+j = half ensures left side has correct count.- Use sentinels (-inf, +inf) to handle empty partitions (i==0 or i==m, j==0 or j==n).- For odd total, median is max(lefts). For even, average of max(lefts) and min(rights).Time: O(log min(m,n)). Space: O(1).Edge cases: one array empty (works due to sentinels), duplicates, all elements equal, arrays of very different sizes.

MediumTechnical

32 practiced

Write a Python function sliding_window_max(nums, k) that returns an array of the maximum for each sliding window of size k. Target O(n) time using a deque; explain how it maintains candidates and why amortized cost is O(1) per element.

Sample Answer

We can maintain a deque of indices whose corresponding values are in decreasing order; the front is the max for the current window. For each new element i:- Pop from the right while nums[i] >= nums[deque[-1]] to remove dominated candidates.- Append i.- Pop from the left while deque[0] <= i - k to remove indices outside the window.- When i >= k-1, record nums[deque[0]] as the window max.

This keeps only useful candidates; each index is pushed and popped at most once, so amortized O(1) per element and overall O(n).

python

from collections import deque

def sliding_window_max(nums, k):
    """
    Return list of maximums for each sliding window of size k.
    Time: O(n), Space: O(k)
    """
    if k <= 0:
        raise ValueError("k must be >= 1")
    n = len(nums)
    if n == 0:
        return []
    if k == 1:
        return nums[:]  # every element is a window

    dq = deque()      # stores indices, values decreasing
    result = []

    for i, val in enumerate(nums):
        # Remove smaller values from right; they can't be max while val is in window
        while dq and nums[dq[-1]] <= val:
            dq.pop()

        dq.append(i)

        # Remove indices outside the window
        if dq[0] <= i - k:
            dq.popleft()

        # Record max once first window is complete
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result

Key points:- Deque stores candidate indices in decreasing value order; dominated elements are removed immediately.- Each index is appended once and removed at most once → O(n) total operations, so amortized O(1) per element.- Handles edge cases: k > n (returns single max if desired — current code returns windows only when full), k == 1, empty input. Adjust behavior for k > n if different semantics required.

HardSystem Design

36 practiced

You need to compute top-k most frequent user IDs from terabytes of log data that cannot fit into memory. Describe practical algorithms and system approaches: single-machine external algorithms, MapReduce approach, and streaming/approximate algorithms (e.g., Count-Min Sketch, Space-Saving). Discuss accuracy, memory, and IO trade-offs.

Sample Answer

Requirements & constraints:- Inputs: terabytes of log lines with user IDs => cannot fit in memory.- Output: top-k most frequent user IDs (exact or approximate), with latency/accuracy trade-offs.

Single-machine external algorithms:1) External sort + scan:- Phase 1: read chunks, sort each chunk by userID, write sorted runs to disk.- Phase 2: multi-way merge of runs and count contiguous equal IDs to accumulate frequencies, maintain top-k using a min-heap.- Pros: exact counts. Cons: heavy IO, requires multiple passes and disk space for runs; time ~ O(N log M) for chunk sorts + merge IO.2) Hash-partition to disk:- Stream records, hash userID into P partitions written to disk (P chosen so each partition fits memory).- For each partition: load into memory, count with a hash map, extract local top-k; finally merge P local top-k to global top-k.- Pros: fewer passes, parallelizable, exact. Cons: needs enough disk bandwidth and balanced partitioning.

MapReduce / distributed approach:- Mapper: emit (userID, 1) or local combiners to pre-aggregate per mapper.- Shuffle groups keys to reducers; Reducer sums counts per userID and emits (userID, count).- Final step: either a reducer computes global top-k, or perform a second MapReduce job where mappers emit top-k from each reducer and a single aggregator reduces to final top-k.- Pros: scales horizontally, fault-tolerant, exact counts. Cons: shuffle heavy (network IO), latency depends on cluster size/config.

Streaming / approximate algorithms:1) Count-Min Sketch (CMS)- Probabilistic, sub-linear memory. For each ID, update d hash rows; estimate = min(row estimates).- Guarantees: overestimation bounded by epsilon*N with probability 1-delta.- Pros: constant memory, fast updates, mergeable sketches. Cons: biased-high counts (no false negatives), retrieving actual heavy-hitter IDs requires an auxiliary candidate set (CMS alone doesn’t list keys).2) Space-Saving (Misra-Gries / Frequent algorithm)- Maintains m counters for top candidates; on new ID, increment if present, else replace min counter or increment with eviction.- Guarantees: items with frequency > N/(m+1) will be tracked; error bounded by total decrements.- Pros: directly returns candidate heavy hitters, good practical accuracy. Cons: uses O(m) memory; infrequent items may be missed.3) Hybrid: use Space-Saving to track candidate IDs and CMS to estimate counts more accurately for candidates.

Accuracy, memory, IO trade-offs:- Exact methods (external sort, hash-partition, MapReduce): require O(#distinct) disk or shuffle IO, memory scales with per-partition distinct keys; provide deterministic accuracy but higher IO & latency.- Approximate streaming: memory O(1) or O(m) independent of distinct keys; low IO and single-pass streaming suitable for real-time; accuracy controlled by sketch parameters (epsilon, delta, m). Risk: approximation error, possible missed borderline heavy hitters.- Practical guidance: - If you need exact top-k and can afford batch processing: use distributed MapReduce or partitioned single-machine external counting. - If near-real-time and bounded memory: use Space-Saving (for candidates) ± CMS for counts, and periodically validate top candidates with exact batch counts (adaptive verification). - Tune parameters: set partitions P so each fits memory; set CMS width w≈e/ε, depth d≈ln(1/δ); set Space-Saving m so error budget ≤ acceptable threshold.

Monitoring & validation:- Periodically run an expensive exact job on sampled data or on stored candidate set to estimate actual error rates and recalibrate sketch sizes or partitioning.

HardTechnical

34 practiced

Implement wildcard_match(text, pattern) in Python where pattern supports '?' (single-character) and '*' (matches any sequence of characters). Optimize for large text inputs; discuss dynamic programming versus two-pointer greedy techniques and their time/space trade-offs.

Sample Answer

To solve wildcard matching efficiently for large texts, you can use either DP (clear correctness) or a two-pointer greedy approach (linear time, constant space). I'll present the optimized two-pointer greedy solution (O(n + m) time, O(1) space) and then compare it to DP.

Approach (greedy two-pointer):- Walk through text (i) and pattern (j).- Advance on match or '?'.- On '*', record star position and text index; try to match zero chars first.- If mismatch later, backtrack to last '*' and consume one more character from text.- If pattern finishes, ensure remaining pattern chars are all '*'.

python

def wildcard_match(text: str, pattern: str) -> bool:
    i = j = 0
    star_j = -1      # last '*' index in pattern
    star_i = -1      # text index corresponding to chars matched by that '*'
    n, m = len(text), len(pattern)
    
    while i < n:
        if j < m and (pattern[j] == '?' or pattern[j] == text[i]):
            i += 1
            j += 1
        elif j < m and pattern[j] == '*':
            star_j = j
            star_i = i
            j += 1  # try matching zero chars first
        elif star_j != -1:
            # backtrack: let '*' absorb one more char
            star_i += 1
            i = star_i
            j = star_j + 1
        else:
            return False
    # consume trailing '*' in pattern
    while j < m and pattern[j] == '*':
        j += 1
    return j == m

Key points:- Greedy handles large texts with O(n + m) time and O(1) extra space.- DP (classic boolean table) is O(n*m) time and O(n*m) space; can be reduced to O(m) space with rolling array but still O(n*m) time.- Use DP when you need formal proof of correctness for complex extensions (e.g., character classes, limited repeats), or when patterns include constraints making greedy incorrect.- Edge cases: empty pattern/text, pattern of all '*', patterns with consecutive '*' (greedy handles them), very large inputs (prefer greedy).

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.