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.

HardTechnical

59 practiced

Implement MinHash for estimating Jaccard similarity between documents constructed from k-shingles (substrings of length k). Provide functions to compute shingles, generate multiple hash signatures, and estimate similarity. Discuss how many permutations (signature size) are needed to achieve a given variance in estimate and how MinHash is used in large-scale near-duplicate detection.

Sample Answer

To estimate Jaccard similarity of documents using k-shingles, use MinHash: convert each doc to a set of k-length shingles, apply multiple independent hash functions (or random permutations simulated via parameterized hash family) and record the minimum hash per function as the signature. Similarity ≈ fraction of matching signature entries.

Approach:1. Shingle documents into k-grams.2. Build m MinHash functions (e.g., universal family: (a*x + b) mod PRIME).3. For each hash func, compute min hash over shingles -> signature vector length m.4. Estimate Jaccard by fraction of equal positions between two signatures.

Code (Python):

python

import random
from hashlib import sha1

def k_shingles(s, k):
    return {s[i:i+k] for i in range(len(s)-k+1)} if len(s)>=k else {s}

PRIME = (1<<61) - 1

def make_hash_funcs(m, max_shingle_id):
    rng = random.Random(42)
    funcs = []
    for _ in range(m):
        a = rng.randint(1, PRIME-1)
        b = rng.randint(0, PRIME-1)
        funcs.append((a,b))
    return funcs

def hash_shingle(x):
    # stable integer hash from string
    return int(sha1(x.encode('utf8')).hexdigest(),16) & ((1<<61)-1)

def minhash_signature(shingles, funcs):
    sig = []
    hashed = [hash_shingle(s) for s in shingles]
    for a,b in funcs:
        minv = min(((a*h + b) % PRIME) for h in hashed)
        sig.append(minv)
    return sig

def minhash_jaccard(sig1, sig2):
    assert len(sig1)==len(sig2)
    return sum(1 for a,b in zip(sig1,sig2) if a==b)/len(sig1)

Key concepts:- MinHash unbiasedly estimates Jaccard: P[min hashes equal] = J(A,B).- Use strong hash for shingle->int; simulate permutations with (a*x+b) mod prime.

Variance & signature size:- For signature length m, estimator is mean of m Bernoulli trials with p = J. Var = p(1-p)/m. To target standard error σ, choose m ≈ p(1-p)/σ^2. Worst-case p=0.5 maximizes variance => m ≈ 0.25/σ^2.

Large-scale near-duplicate detection:- Combine MinHash with LSH (banding): split m-length signature into b bands of r rows (m= b*r). For each band hash, place into buckets; candidate pairs that share any band are likely similar. Tune b,r to trade recall/precision for threshold t ≈ (1/b)^(1/r).- Use streaming/minimal storage: keep compact signatures, compare only candidate pairs; parallelize hash functions and bucket building.

Edge cases & best practices:- Choose k per language/type (e.g., k=5-10 for text). Normalize text (lowercase, remove punctuation) before shingling.- Ensure hash functions independent; use large prime and 64-bit arithmetic to reduce collisions.- For very large corpora store signatures in binary (e.g., 32/64-bit ints) and use blocking.

EasyTechnical

44 practiced

You have a list of integer feature indices representing nonzero positions in a sparse feature vector. Given an array nums and an integer target, implement a Python function that returns indices of two numbers such that they add up to target. Assume exactly one solution exists and you cannot use the same element twice. Provide time and space complexity and mention how this applies to matching features in embedding spaces.

Sample Answer

To solve this, use a hash map to store value→index while scanning nums once. For each number x at index i, check if target-x exists in the map; if so return its index and i. This is O(n) time and O(n) space, ideal for sparse feature index lists where you need fast pair matching.

python

def two_sum(nums, target):
    """
    Return indices [i, j] such that nums[i] + nums[j] == target.
    Assumes exactly one solution and i != j.
    """
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    raise ValueError("No solution")  # defensive; problem states one exists

# Example:
# nums = [2, 7, 11, 15], target = 9 -> returns [0, 1]

Key points:- Time complexity: O(n) single pass.- Space complexity: O(n) for the hash map.- Edge cases: duplicates handled (store first index), negative numbers, empty array, indices distinct.

Application to embedding/feature matching:- When matching sparse nonzero feature indices (or small integer IDs) from two vectors, this approach quickly finds pairs that combine to a target similarity or hashed bucket. In practice, you'd adapt values to scores (e.g., dot-product contributions) and use hashing to accumulate or lookup complements for efficient sparse matching without materializing dense vectors.

EasyTechnical

43 practiced

Implement a function to compute the maximum sum of any contiguous subarray with fixed length k in an integer array. Use Python and O(n) time. Explain how sliding window optimization reduces redundant computation compared to naive approach, and mention use cases in moving-average feature computation.

Sample Answer

To solve this, use a sliding-window: compute the sum of the first k elements, then for each step remove the element leaving the window and add the entering element — O(1) per step so overall O(n).

python

def max_sum_subarray_k(nums, k):
    """
    Return max sum of any contiguous subarray of length k.
    Raises ValueError if k <= 0 or k > len(nums).
    """
    n = len(nums)
    if k <= 0 or k > n:
        raise ValueError("k must be between 1 and len(nums)")
    # initial window sum
    window_sum = sum(nums[:k])
    max_sum = window_sum
    # slide the window
    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]  # add new, remove old
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

Key points:- Sliding window avoids recomputing the sum of k elements at each position (naive would sum k elements per position → O(n*k)). Sliding window updates in O(1) per shift → O(n).- Time complexity: O(n). Space complexity: O(1).- Edge cases: k equals n, all negatives (works), k invalid (handled).

Use cases for AI Engineers:- Computing moving averages as features (e.g., rolling mean of time-series signals, smoothing sensor data, or windowed aggregations for feature engineering in streaming pipelines). Sliding-window enables real-time, low-latency updates without reprocessing full windows.

EasyTechnical

36 practiced

As an AI Engineer you often manipulate flattened tensors stored as 1D arrays. Implement a Python function that reverses an integer array in-place (O(1) extra space) and returns the array. Do not use built-in reverse functions or slicing. Example: input = [1, 2, 3, 4], output = [4, 3, 2, 1]. Explain time and space complexity and how this pattern helps when reshaping tensor data on GPU memory.

Sample Answer

To reverse an integer array in-place, swap elements symmetrically from the ends toward the center using two pointers. This uses O(1) extra space and O(n) time.

python

def reverse_in_place(arr):
    """
    Reverse a list of integers in-place and return it.
    Does not use built-in reverse or slicing.
    """
    left, right = 0, len(arr) - 1
    while left < right:
        # swap arr[left] and arr[right]
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# Example
# input: [1,2,3,4] -> output: [4,3,2,1]

Key points:- Approach: two-pointer symmetric swaps; simple and cache-friendly.- Time complexity: O(n) — each element is moved at most once.- Space complexity: O(1) — constant extra variables only.- Edge cases: empty list, single-element list, lists with duplicates — all handled.

Why this matters for AI Engineers:- Flattened tensors on GPU are contiguous in memory; reversing in-place avoids extra buffer allocations and costly device-to-host transfers.- In-place operations reduce memory pressure on GPU, improving throughput and allowing larger batches or models.- The two-pointer pattern is branch-minimal and maps well to vectorized kernels when parallelized for large tensors.

MediumTechnical

30 practiced

Longest Palindromic Substring: Implement a Python function that returns the longest palindromic substring of a given string. Use the expand-around-center approach for simplicity (O(n^2) time) and discuss the Manacher algorithm for O(n) time as a follow-up. Mention NLP use-cases where palindrome detection might matter.

Sample Answer

To solve this, expand around each possible center (character or between characters) and grow while characters match. This is O(n^2) time, O(1) extra space and simple to implement.

python

def longest_palindrome(s: str) -> str:
    """
    Return the longest palindromic substring using expand-around-center.
    Time: O(n^2), Space: O(1) (ignoring output).
    """
    if not s:
        return ""
    start = 0
    end = 0  # inclusive indices of best palindrome

    def expand(left: int, right: int) -> (int, int):
        # expand while characters match, return inclusive bounds
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(len(s)):
        # odd length (center at i)
        l1, r1 = expand(i, i)
        if r1 - l1 > end - start:
            start, end = l1, r1
        # even length (center between i and i+1)
        l2, r2 = expand(i, i + 1)
        if r2 - l2 > end - start:
            start, end = l2, r2

    return s[start:end + 1]

Key points:- We check 2n centers (n odd, n even) and expand, giving O(n^2) worst-case (e.g., all same chars).- Space is O(1) aside from returned substring.- Edge cases: empty string, single char, all-equal characters, unicode combining characters (be careful with grapheme clusters).

Follow-up (Manacher's algorithm):- Manacher achieves O(n) by transforming string (e.g., inserting separators) and using previously computed palindrome radii to skip expansions. It's more complex to implement but recommended when n is large and worst-case quadratic is unacceptable.

NLP use-cases:- Palindrome detection is rarely central, but can matter for data cleaning (detecting palindromic tokens/noise), stylistic analysis in literary NLP, author attribution (use of palindromic patterns), or anomaly detection in generated text. It can also be a simple feature in text classification or playful interfaces (palindrome suggestions).

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.