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

37 practiced

Given a large corpus of tokenized sentences, design an algorithm to efficiently find all near-duplicate sentences where 'near' is defined by Jaccard similarity over shingles > T. Explain shingling, minhashing, and hashing choices; detail data structures and complexity to scale to hundreds of millions of sentences.

Sample Answer

Requirements & constraints:- Input: hundreds of millions of tokenized sentences (each as a list of tokens).- Output: pairs (or clusters) of sentences whose Jaccard similarity over k-shingles > T (threshold).- Non-functional: memory limited, near-linear time, distributed, incremental updates.

High-level approach:1. Shingle each sentence into k-token contiguous shingles (k=3..5 typical).2. Represent each sentence as a set of shingle IDs (hashed).3. Use MinHash to compute a compact signature per sentence (m hash functions → signature length m).4. Use LSH (banding) on signatures to generate candidate pairs.5. Verify candidates by computing exact Jaccard on shingle sets.

Shingling:- Choose k to balance sensitivity vs. noise (k small -> more false positives; k large -> miss paraphrases). For sentences, k=3 is common.- Canonicalize tokens (lowercase, strip punctuation, normalize numbers).- Hash each shingle to 64-bit using a non-cryptographic fast hash (e.g., xxHash64) to reduce memory.

MinHash:- Use m around 128–256 to achieve good estimation; pick m based on desired error: std ≈ 1/sqrt(m).- Implement MinHash via random linear hash functions modulo a large prime: h_i(x) = (a_i * x + b_i) mod P then take min per function.- Store signatures as uint32/uint64 arrays; consider using 8-bit quantized sketches if memory-critical (with accuracy trade-off).

LSH (banding):- Split m into b bands of r rows (m = b*r). Choose b and r so that the S-curve places threshold near T (probability that similar >T become candidates high, otherwise low).- For each band, hash the band tuple to a bucket using a strong 64-bit hash; insert (bucket -> sentenceID) into distributed key-value store (e.g., RocksDB, Cassandra, or Redis clusters).- Candidate generation: for each bucket, emit all pairs of IDs (or connect via posting lists). To scale, avoid O(n^2) by limiting extremely large buckets (cap or use second-stage filtering).

Data structures & storage:- Shingle sets: transient; avoid storing full sets for all sentences. Instead store compact bitsets or sorted arrays on disk. For verification, fetch shingle hashes on-demand (or precompute Bloom filters for cheap approximate Jaccard lower/upper bounds).- Signatures: store in key-value store keyed by sentenceID (compressed).- LSH index: bucket -> list of sentenceIDs stored in distributed store, sharded by bucket hash.- Use MapReduce/Spark or Flink for bulk processing; use stream processors for incremental indexing.

Complexity:- Shingling: O(total_tokens).- MinHash signature compute: O(m * avg_shingles_per_sentence) — embarrassingly parallel by sentence.- LSH insertion: O(b) per sentence.- Candidate pairs: dependent on bucket sizes; expected near-linear if thresholds tuned; worst-case quadratic if buckets large.

Practical optimizations:- Use 64-bit hashes and vectorized/minibatched operations for speed.- Pre-filter by sentence length or token overlap to reduce trivial candidates.- Cap bucket sizes and use reservoir sampling to avoid hotspot explosion (common stop-phrases).- Use TF-IDF weighting + weighted MinHash if want importance.- For final verification, use sorted arrays and two-pointer Jaccard intersection to compute exact similarity efficiently.

Trade-offs:- Larger m reduces false positives but increases compute & storage.- LSH tuning (b,r) trades recall vs candidate volume.- Storing full shingle sets speeds verification but increases storage; Bloom filters reduce I/O at cost of false positives.

Evaluation & monitoring:- Sample recall/precision vs ground truth; tune k, m, (b,r).- Monitor bucket distributions, latency, and storage hot-spots.- Provide incremental re-index and aging policies.

This pipeline is production-friendly: embarrassingly parallel signature computation, distributed LSH buckets, on-demand verification, with tunable accuracy/cost knobs for scaling to hundreds of millions of sentences.

EasyTechnical

31 practiced

Given an array of integers representing class labels in a dataset, implement a Python function to find the majority element (the element that appears more than ⌊n/2⌋ times). Try to do it in O(n) time and O(1) space. Explain Boyer-Moore Voting Algorithm and when you would use it vs. a hash-counting approach in ML data validation.

Sample Answer

To find the majority element in O(n) time and O(1) space we can use the Boyer–Moore Voting Algorithm. It scans once to pick a candidate by canceling out different elements, then (optionally) you can verify the candidate by counting occurrences.

Approach: single pass to get candidate, optional second pass to verify.

python

def majority_element(nums):
    """
    Boyer-Moore Voting: returns the element that appears > floor(n/2) times.
    Assumes such an element exists. If not guaranteed, verify in a second pass.
    """
    # Phase 1: find candidate
    candidate = None
    count = 0
    for x in nums:
        if count == 0:
            candidate, count = x, 1
        elif x == candidate:
            count += 1
        else:
            count -= 1

    # Optional Phase 2: verify candidate (use if majority not guaranteed)
    # if nums.count(candidate) > len(nums)//2:
    #     return candidate
    # raise ValueError("No majority element")

    return candidate

Key points:- The algorithm cancels paired distinct elements so a true majority remains.- Time: O(n); Space: O(1).- Edge cases: empty list (handle separately), when majority not guaranteed run verification.

When to use Boyer–Moore vs hash-counting in ML data validation:- Use Boyer–Moore when memory is constrained, datasets are large or streamed, and you only need a single majority label (guaranteed or you will verify later).- Use hash-counting (collections.Counter) when you need counts for many labels, want simplicity, or must detect multiple frequent labels and exact frequencies — common in exploratory validation and reporting.

MediumTechnical

44 practiced

Given a sorted array of integers (ascending), find two numbers such that they add up to a specific target number. Return the pair of values (not indices). Implement in Python using O(n) time and O(1) extra space via the two-pointer technique. Example: [1,2,3,4,6], target=6 -> (2,4).

Sample Answer

Approach:Use the two-pointer technique because the array is sorted. Initialize left at start and right at end; move pointers inward depending on the sum compared to target. This yields O(n) time and O(1) extra space and returns the pair of values.

python

def two_sum_sorted(nums, target):
    """
    Find two numbers in a sorted ascending list that add up to target.
    Returns a tuple (a, b) if found, else None.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return (nums[left], nums[right])
        elif s < target:
            left += 1
        else:
            right -= 1
    return None

# Example
# print(two_sum_sorted([1,2,3,4,6], 6))  # -> (2, 4)

Key points:- Because input is sorted, no extra data structures are needed.- Move left forward when sum is too small (need larger value), move right backward when sum is too large (need smaller value).

Time complexity: O(n) — each element visited at most once.Space complexity: O(1) extra space.

Edge cases:- Empty or length < 2 -> return None- Negative numbers and duplicates are handled naturally- If multiple pairs exist, this returns the first found by pointer movement

Alternative:- If array were unsorted, use a hash map for O(n) time and O(n) space; or sort first (O(n log n)) then apply two-pointer.

EasyTechnical

37 practiced

Implement a function in Python that checks whether a given string is a palindrome, considering only alphanumeric characters and ignoring cases. Example: 'A man, a plan, a canal: Panama' -> True. Explain complexity and how you'd handle large Unicode inputs encountered in production text preprocessing.

Sample Answer

Approach: use a two-pointer scan over the original string, skipping non-alphanumeric characters, comparing characters case-insensitively. For robust Unicode handling use .casefold() and optionally Unicode normalization (NFKC) to collapse compatibility characters.

python

def is_palindrome(s: str) -> bool:
    """
    Check palindrome ignoring non-alphanumeric chars and case.
    Uses Unicode-aware .isalpha/.isalnum and .casefold for casing.
    """
    # Normalize to NFKC to handle compatibility characters (optional but recommended)
    import unicodedata
    s = unicodedata.normalize("NFKC", s)

    left, right = 0, len(s) - 1
    while left < right:
        # advance left to next alnum
        while left < right and not s[left].isalnum():
            left += 1
        # advance right to prev alnum
        while left < right and not s[right].isalnum():
            right -= 1

        if left >= right:
            break

        if s[left].casefold() != s[right].casefold():
            return False
        left += 1
        right -= 1
    return True

Key points:- Time complexity: O(n) single pass.- Space complexity: O(1) extra (in-place pointers). Normalization creates a new string; drop it for strict O(1).- Edge cases: empty string -> True, strings of length 1 -> True, multi-byte Unicode characters handled by .isalnum/.casefold.

Production notes for large Unicode corpora:- Use unicodedata.normalize + .casefold for consistent comparisons.- If memory is constrained, avoid creating normalized copy: iterate with an iterator that yields normalized segments or use mmap/streaming to process chunks, but be careful at chunk boundaries (carry overlap).- For very large texts, pre-cleaning with streaming pipelines (e.g., generator that yields codepoints after normalization) preserves low memory usage.

MediumTechnical

36 practiced

You have an event stream of (user_id, timestamp) ordered by time. Implement a Python function that returns all user_ids that have more than k events within any sliding window of size T seconds. Provide an approach using hash maps + deque per user to keep O(number of events) amortized time and explain memory considerations in production.

Sample Answer

Approach: Maintain for each user a deque of recent event timestamps (only those within T seconds of current event). On each new event, push timestamp to user's deque, pop left while deque[0] < timestamp - T, then if len(deque) > k emit user_id (or record). This is amortized O(1) per event because each timestamp is added and removed once.

python

from collections import defaultdict, deque

def detect_high_rate_users(events, T, k):
    """
    events: iterable of (user_id, timestamp) ordered by timestamp (ascending)
    T: window size in seconds (int/float)
    k: threshold (int) — return users with more than k events in any T-second window
    Returns: set of user_ids that exceeded threshold at least once
    """
    user_queues = defaultdict(deque)  # user_id -> deque of timestamps
    offenders = set()

    for user_id, ts in events:
        q = user_queues[user_id]
        q.append(ts)
        # remove timestamps older than window
        cutoff = ts - T
        while q and q[0] <= cutoff:
            q.popleft()
        if len(q) > k:
            offenders.add(user_id)
            # optional: clear or compact deque to save memory if we won't check this user further
            # user_queues.pop(user_id, None)
    return offenders

Key points:- Each timestamp enqueued/dequeued once → O(n) total work (amortized O(1) per event).- Space: sum of sizes of all deques = number of events within last T seconds across all users. In worst-case bursty traffic that can be large.

Production memory considerations:- Use time-based eviction (periodic compaction) and remove deques for inactive users.- Limit per-user deque size with a cap; use approximate counters (count-min sketch, sliding count windows, or leaky-bucket) if exactness isn't required.- Shard state by user hash across workers; persist state in bounded state stores (Redis, RocksDB, or stream processing stateful backends like Flink/Beam) for fault tolerance and memory safety.- Monitor memory, set backpressure, and consider sampling or downstream alerts instead of storing all timestamps when scale is extreme.

Edge cases:- Out-of-order timestamps: requires buffering or watermarking.- Very high-cardinality users: use caps/approximation as above.

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.