Arrays, Strings & Hashing Questions

Solve problems involving array manipulation, string operations, and hash tables. Common topics include two-pointer techniques, sliding windows, prefix sums, and hash map usage. Practice problems on LeetCode with difficulty 'easy' to 'medium.' Focus on understanding why these data structures are used and what their trade-offs are.

HardSystem Design

32 practiced

Design a system to detect duplicate or near-duplicate images arriving as a high-volume stream. Discuss hashing strategies (perceptual hash, pHash), indexing, false positives/negatives, storage, and how you would scale to 1M images/day with near-duplicate tolerance.

Sample Answer

Requirements & constraints:- Ingest 1M images/day (~11.6/sec average, peak higher), detect exact and near-duplicates (resized, recompressed, small crops), low latency for blocking uploads, scalable, low FP/FN rates, budget-constrained.

High-level architecture:- Ingest → preprocessing service (normalize, resize) → feature extractor → index/lookup → decision service → storage + feedback loop.- Use Kafka for buffering, autoscaled workers for feature extraction, Redis for hot-cache, S3/GCS for blobs, and a distributed metadata store (Cassandra/Postgres) for results.

Hashing & feature extraction:- Use perceptual hashes: pHash (DCT-based) as primary 64- or 128-bit fingerprint; complement with dHash or color-hash for robustness to different transforms. For stronger similarity, compute compact CNN embeddings (e.g., 128-D vector from a pretrained model) and quantize via product quantization (PQ) to save space.

Indexing & search:- For binary pHashes: use Hamming-distance tolerant index. Shard by hash-prefix and store bitvectors; use multi-probe LSH or BK-tree per shard to retrieve candidates within Hamming radius (e.g., ≤5 for 64-bit).- For embeddings: approximate nearest neighbor (ANN) with Faiss (IVF-PQ + HNSW) to get top-k near matches efficiently.- Pre-filter with a Bloom filter for exact-hash quick-rejects to avoid unnecessary ANN queries.

False positives / negatives:- FP: perceptual hash collisions or coarse thresholds; mitigate by multi-stage verification — candidate match → higher-fidelity compare (SSIM or pixel-wise after alignment) or compare CNN embeddings.- FN: overly strict threshold or transformations not captured; mitigate by combining multiple hash types and learned embeddings, and periodically tuning thresholds with labeled dataset.- Provide a human-review queue for borderline cases and continuous feedback to update thresholds and models.

Storage & metadata:- Store image blobs in object store. Store fingerprints, embeddings, timestamps, owner, and indexing pointers in a scalable DB. Maintain retention/TTL for ephemeral use-cases.

Scaling to 1M/day:- Throughput: autoscale extractor workers; batch hash/embedding computations on GPUs for CNNs; use asynchronous processing for non-blocking ingestion.- Partition indices by hash-prefix or by time (daily shards) and replicate for read scaling.- Use Faiss on dedicated ANN nodes; horizontally scale HNSW/IVF tables and keep in-memory indexes for recent/high-traffic data.- Use cache (Redis) for hot lookups and Bloom filters for fast negatives.- Monitor metrics (latency, recall/precision, index size). Rebalance shards with consistent hashing.

Trade-offs:- pHash is cheap and interpretable but less robust than learned embeddings. CNN+ANN increases accuracy but costs CPU/GPU and more complex indexing.- Tighter thresholds reduce FP but increase FN; multi-stage pipelines balance cost vs accuracy.

Operational notes:- Automate offline evaluation pipelines to compute ROC curves and pick thresholds per class of content.- Provide privacy controls (hash-only storage, encrypt blobs).- Design for gradual rollout: start with pHash + Bloom + BK-tree, measure, then add CNN embeddings and ANN when needed.

HardTechnical

39 practiced

Implement Rabin-Karp rolling-hash substring search to find all occurrences of a pattern in a text. Handle hashing, mod arithmetic, wide alphabets, and collision handling. Describe how to choose base and modulus and how to reduce false positives.

Sample Answer

To implement Rabin–Karp robustly:1) use a rolling polynomial hash with large random base and a large prime modulus (e.g., near 2^61-1 or two moduli) to reduce collisions;2) on hash match verify by direct string compare to eliminate false positives.

Approach: compute pattern hash and initial window hash; update rolling hash in O(1) using precomputed base^m; on hash equality, verify.

python

import random

# 64-bit safe multiplication mod (2^61-1) using Python ints
MOD = (1 << 61) - 1

def modmul(a, b):
    # multiply a*b mod MOD using reduce trick for Mersenne prime
    x = a * b
    x = (x >> 61) + (x & MOD)
    if x >= MOD: x -= MOD
    return x

def rabin_karp_all(text, pat):
    n, m = len(text), len(pat)
    if m == 0: return list(range(n+1))
    base = random.randrange(256, MOD-1)
    pow_m = 1
    for _ in range(m): pow_m = modmul(pow_m, base)
    # initial hashes
    h_t = 0
    h_p = 0
    for i in range(m):
        h_t = modmul(h_t, base) + ord(text[i])
        h_t %= MOD
        h_p = modmul(h_p, base) + ord(pat[i])
        h_p %= MOD
    res = []
    for i in range(n - m + 1):
        if h_t == h_p:
            if text[i:i+m] == pat: res.append(i)  # verification
        if i + m < n:
            # remove leading char and add next
            left = modmul(ord(text[i]), pow_m)
            h_t = (h_t + MOD - left) % MOD
            h_t = modmul(h_t, base)
            h_t = (h_t + ord(text[i+m])) % MOD
    return res

Key points:- Base: random in [alphabet..MOD) reduces adversarial collisions.- Modulus: use big prime (2^61-1) for speed and low collision probability; for absolute safety use two independent hashes.- Verify matches by direct comparison to remove false positives.Time: O(n+m) average; Space: O(1) besides output. Edge cases: empty pattern, very large alphabets (works since we map chars to ints), adversarial inputs—use randomized base or double hashing.

HardTechnical

32 practiced

Given an array where every element appears three times except for one element which appears exactly once, find that single element in O(n) time and O(1) extra space. Example: [2,2,3,2] -> 3. Implement using bitwise operations and explain the logic.

Sample Answer

We can count bits modulo 3. For each of the 32 bit positions, count how many numbers have that bit set; the count % 3 gives the bit of the unique number. Doing this with constant extra space uses fixed-size counters (two integers tracking bits seen once and twice) and bitwise logic.

python

def single_number(nums):
    """
    Find the element that appears once while others appear three times.
    Uses bitwise counting with O(1) extra space and O(n) time.
    """
    ones = 0   # bits seen 1 time modulo 3
    twos = 0   # bits seen 2 times modulo 3

    for x in nums:
        # add x to twos if bit is set in ones and in x
        twos |= ones & x
        # toggle bits in ones for x
        ones ^= x
        # common bits in ones and twos are those seen 3 times -> clear them
        common = ones & twos
        ones &= ~common
        twos &= ~common

    return ones  # ones holds the bits seen exactly once

Key points:- ones and twos form a finite-state machine per bit cycling through 0 -> 1 -> 2 -> 0 as numbers repeat.- After processing all numbers, bits with count % 3 == 1 remain in ones.Time: O(n). Space: O(1) (only a few integers).Edge cases:- Negative numbers: Python ints are unbounded; this algorithm still works because bitwise ops act on two's complement semantics when interpreting fixed-width, but in Python it correctly yields the integer result (works for typical constraints). If required, mask to 32 bits and convert to signed. Alternative: per-bit counting with 32-length loop.

MediumTechnical

40 practiced

Design encode and decode functions for a list of strings so that the encoded string can be transmitted and decoded back to the original list unambiguously. Discuss delimiter-escaping and length-prefix strategies and implement a robust solution in any language.

Sample Answer

Approach- Two common strategies: delimiter-escaping (escape the delimiter inside strings) and length-prefix (prefix each string with its length). Delimiter-escaping is simple but error-prone (must pick an escape char and handle nested escapes). Length-prefix is unambiguous and robust, especially with arbitrary binary/Unicode data. I'll implement length-prefix using UTF-8 bytes and a fixed separator ':' between the decimal length and the payload.

Implementation (Python)

python

def encode(strs):
    """
    Encode a list[str] -> bytes using length-prefix: <len>:<bytes><len>:<bytes>...
    Length is number of bytes of the UTF-8 encoding.
    """
    parts = []
    for s in strs:
        b = s.encode('utf-8')
        parts.append(str(len(b)).encode('ascii') + b':' + b)
    return b''.join(parts)

def decode(data):
    """
    Decode bytes produced by encode back to list[str].
    """
    i = 0
    out = []
    n = len(data)
    while i < n:
        # read length field (decimal) until ':'
        j = i
        while j < n and data[j] != 58:  # ord(':') == 58
            j += 1
        if j == n:
            raise ValueError("Invalid encoding: missing ':' after length")
        length = int(data[i:j].decode('ascii'))
        j += 1  # skip ':'
        if j + length > n:
            raise ValueError("Invalid encoding: not enough bytes for string")
        chunk = data[j:j+length]
        out.append(chunk.decode('utf-8'))
        i = j + length
    return out

Key points / reasoning- We encode strings to UTF-8 bytes and prefix each with the byte-length; this avoids ambiguity with multibyte Unicode.- Using a separator ':' after the length makes parsing simple; the length tells exactly how many bytes to read next.- Works for empty strings (encoded as "0:") and arbitrary bytes (if you start with bytes, skip UTF-8 decode/encode).

Time & Space- Time: O(total_bytes) to encode/decode- Space: O(total_bytes) output plus O(1) extra overhead

Edge cases- Malformed input (missing ':' or truncated payload) — decoder raises errors.- Very large strings — length field grows, but decimal length scales logarithmically.- If you need purely text (no bytes) you can base64 payloads, but that adds 33% overhead.

Alternatives- Delimiter-escaping (choose delimiter and escape char) — simpler but trickier for correctness.- Fixed-width length field (e.g., 4 or 8 bytes binary) — faster/parsing simpler when you can fix max length.

HardTechnical

31 practiced

Given an unsorted array of integers, find the length of the longest sequence of consecutive integers. Achieve expected O(n) time and O(n) space. Example: [100,4,200,1,3,2] -> 4 for sequence [1,2,3,4]. Implement and explain avoidance of repeated work.

Sample Answer

Approach: Use a hash set of all numbers for O(1) membership checks. For each number, start expanding only if it's the beginning of a sequence (num-1 not in set) — this avoids repeated work because every sequence is expanded exactly once.

python

def longest_consecutive(nums):
    """
    Returns length of longest consecutive sequence in nums.
    O(n) expected time, O(n) space.
    """
    if not nums:
        return 0

    s = set(nums)
    best = 0

    for num in s:  # iterate set to avoid duplicate values
        # only start expanding at sequence starts
        if num - 1 not in s:
            length = 1
            curr = num + 1
            while curr in s:
                length += 1
                curr += 1
            best = max(best, length)

    return best

Key points:- Building the set: O(n) time and O(n) space.- By checking "num-1 not in set" we ensure each consecutive sequence is traversed once (avoid repeated expansion from interior elements).- Iterating the set rather than the original list avoids reprocessing duplicates.

Time complexity: O(n) expected (each value checked a constant number of times). Space complexity: O(n).

Edge cases:- Empty list -> 0- All duplicates -> 1 if any value present- Negative numbers and large ranges handled by the set membership checks.

Unlock Full Question Bank

Get access to hundreds of Arrays, Strings & Hashing interview questions and detailed answers.

Join thousands of developers preparing for their dream job.