Arrays and Hash Map Operations Questions

Covers algorithmic patterns that use arrays together with hash based maps or dictionaries to achieve efficient lookup and counting. Topics include frequency counting, duplicate detection, two sum and k sum variants, sliding window with counts, index mapping, grouping by keys, and using hash maps to reduce time complexity from quadratic to linear. Emphasize insertion deletion and lookup costs, collision and memory considerations, trade offs between using hash maps versus sorting or two pointer techniques, and typical interview problem families that rely on combining arrays with associative containers.

MediumTechnical

61 practiced

Given two arrays of records where the second is known to be a subset of the first by record key, implement an efficient Python function that returns for each element of the second array its original index in the first array. Describe behaviour when duplicates exist and propose a streaming or Spark-based approach for very large datasets.

Sample Answer

Approach: build a hashmap from key → list of original indices for the first array (to handle duplicates), then iterate the second array and pop an index for each record’s key. This is O(n + m) time and O(n) extra space.

python

from collections import defaultdict, deque
from typing import List, Dict, Any, Optional

def map_subset_indices(all_records: List[Dict[str, Any]],
                       subset_records: List[Dict[str, Any]],
                       key_field: str) -> List[Optional[int]]:
    """
    Returns list of indices into all_records for each element in subset_records.
    If a key from subset_records is missing, returns None for that position.
    Handles duplicates by assigning indices in encounter order.
    """
    positions = defaultdict(deque)  # key -> deque of indices
    for i, rec in enumerate(all_records):
        positions[rec[key_field]].append(i)

    result = []
    for rec in subset_records:
        k = rec[key_field]
        if positions[k]:
            result.append(positions[k].popleft())  # assign next available original index
        else:
            result.append(None)  # should not happen if subset guarantee holds
    return result

Key points:- Using deque ensures O(1) pop from left, preserving original-order assignment for duplicates.- Time complexity: O(n + m) where n = len(all_records), m = len(subset_records).- Space complexity: O(n) for the hashmap.

Behavior with duplicates:- If keys repeat in all_records and subset_records contains fewer/more repeats, this implementation assigns indices in first-appearance order. If subset has more occurrences than available in all_records, we return None (or raise an error) depending on desired strictness.

Streaming / Spark for very large datasets:- Streaming: build a compact external index (e.g., RocksDB or Redis) keyed by record key mapping to a queue of positions; as you stream subset records, pop positions atomically. If the first dataset is too large to pre-index in memory, write key→list-of-offsets to persistent store during initial scan.- Spark (batch): load both datasets as DataFrames, keep original index by adding monotonically_increasing_id() to all_records, then join subset_records to all_records on key and collect the id. For duplicates, use a join with an order column and window function (row_number over partition by key) on both datasets then join on (key, row_number) to get stable one-to-one matching.- Consider partitioning by key to keep operations local and scalable; use broadcast join only if subset is small.

MediumTechnical

43 practiced

Implement in Python an efficient grouping function that takes a list of (key, value) tuples and returns a dictionary mapping each key to the list of its values. Discuss how to scale this grouping when the dataset is too large to fit in memory and how to stream results or use external aggregation.

Sample Answer

Approach: Use a hash map (dict) to accumulate lists per key in one pass. For large datasets, stream and shard by key (hash partition) to external storage or use distributed engines (Spark), or use disk-backed key-value stores to avoid memory blowup.

python

from collections import defaultdict
from typing import Iterable, Tuple, Dict, List

def group_pairs(pairs: Iterable[Tuple[str, object]]) -> Dict[str, List[object]]:
    """
    Group (key, value) tuples into a dict: key -> [values].
    Works for any iterable (list, generator) and uses O(n) time, O(k + n) memory
    where k = number of distinct keys.
    """
    groups = defaultdict(list)
    for k, v in pairs:
        groups[k].append(v)
    return dict(groups)

Key concepts:- Uses hash-based accumulation for O(1) amortized insert per pair.- Keeps lists per key; memory = sum of all values stored + dict overhead.

Time/Space:- Time: O(n)- Space: O(n) worst-case (all values kept), O(k) metadata

Edge cases:- Empty input, None keys, heterogeneous value types — handled naturally.- Extremely high-cardinality keys may still cause memory issues.

Scaling strategies:- Stream results: yield incremental batches per key (e.g., flush groups when large).- External aggregation: hash-partition input to multiple files/objects by key % N, then process each partition independently (fits memory).- Use distributed frameworks: Spark/PySpark groupByKey/aggregateByKey or Hadoop MapReduce (mapper emits key, reducer groups).- Disk-backed stores: RocksDB, LMDB, Redis (with eviction/TTL) or use SQLite to append and query.- Online aggregation: maintain aggregates (counts, sums) instead of full lists when possible.

Example: simple partition-to-file approach — write pairs to shard files by hash(key), then group each shard separately to keep peak memory bounded.

MediumTechnical

65 practiced

Given a string s and a pattern p, implement in Python a function that returns starting indices of p's anagrams in s. Use sliding-window and hash maps to maintain character counts and achieve O(n) time. Explain an optimization to avoid full map comparisons on each shift.

Sample Answer

To find all start indices of p's anagrams in s in O(n) time, use a sliding window of size len(p) and maintain character counts for the pattern and the current window. Instead of comparing full maps every shift (O(k) per shift), track how many characters currently match the required count — increment/decrement a single matched counter when a character's count reaches (or leaves) the target. When matched == number_of_unique_chars_in_p, the window is an anagram.

python

from collections import defaultdict

def find_anagrams(s: str, p: str):
    """
    Return starting indices of p's anagrams in s.
    O(n) time, O(k) space where k = unique chars in p.
    """
    if len(p) > len(s):
        return []

    need = defaultdict(int)
    for ch in p:
        need[ch] += 1

    window = defaultdict(int)
    required = len(need)          # number of distinct chars to match
    matched = 0                   # how many distinct chars currently match required count
    res = []
    left = 0
    for right, ch in enumerate(s):
        # add char at right
        window[ch] += 1
        if window[ch] == need.get(ch, 0):
            matched += 1
        # if it exceeded requirement, and previously matched, adjust
        if window[ch] == need.get(ch, 0) + 1:
            matched -= 1

        # shrink window to size len(p)
        if right - left + 1 > len(p):
            out = s[left]
            if window[out] == need.get(out, 0):
                matched -= 1
            window[out] -= 1
            if window[out] == need.get(out, 0):
                matched += 1
            left += 1

        # record result when all distinct chars matched
        if right - left + 1 == len(p) and matched == required:
            res.append(left)

    return res

Key points:- We only update matched when a character's count transitions to/from the required count — avoiding full-map equality checks each shift.- Time: O(n). Space: O(k) where k is number of distinct chars in p.Edge cases:- len(p) > len(s); repeating characters in p; characters in s not present in p (handled by need.get).

HardTechnical

41 practiced

A production service shows performance degradation due to repeated hash collisions in a custom partitioning function. Describe how you would detect pathological collision cases, mitigate them (for example using different hash functions, salted hashing, rebalancing), and design monitoring and alerts to detect recurrence or malicious inputs.

Sample Answer

Situation: A production data pipeline using a custom partitioning function began showing big tail latencies and hot partitions — downstream jobs and storage nodes were overloaded due to repeated hash collisions on certain keys.

Detection (how I'd prove it's pathological):- Collect partition metrics: per-partition count, processing time, queue length, CPU, GC, I/O. Visualize histograms and time-series; look for extreme skew (one or few partitions >> median).- Sample keys mapped to hot partitions and compute key frequency distribution, key entropy, and chi-square goodness-of-fit against uniform expectation.- Inspect raw inputs for adversarial or low-entropy patterns (long prefixes, similar suffixes).- Compare current hash outputs distribution (use modulo bucket) vs. random baseline (simulate with known good hash).- Use streaming sketches (Count-Min, HyperLogLog) to detect heavy hitters in real time.

Mitigation (immediate + long-term):Immediate- Add on-the-fly salting: derive a per-job random seed appended/prepended before hashing to break deterministic collision patterns while rolling out a permanent fix.- Fallback sharding: route oversized keys to a “large-key” path (e.g., dedicated processing pool or range-sharded store).- Rate-limit or backpressure specific key sources if a malicious flood is identified.

Permanent- Replace weak custom hash with a robust, fast non-cryptographic hash with good avalanche (xxHash64, MurmurHash3, SipHash for adversarial resistance). For untrusted inputs use SipHash or HMAC-based salted hashing.- Use consistent hashing with virtual nodes to reduce impact of single bad buckets and ease rebalancing.- Implement two-level partitioning: first coarse hash to group, second dynamic bucketing inside group (adaptive load-aware buckets).- Consider key-splitting/aggregation: shard very hot logical keys across sub-keys (key@shard) and re-aggregate downstream.

Design monitoring & alerts:- Metrics to emit: per-partition request/row rate, latency percentiles, partition-size ratio (max/median), skew score (e.g., Gini or entropy), heavy-hitter list (top-N keys with counts).- Dashboards: heatmap of partition usage over time, heavy-hitter trends, hash distribution uniformity.- Alerts: - High skew alert: if max_partition_size / median_partition_size > threshold (e.g., >10) for 5m. - New heavy hitter alert: sudden key count growth rate > X sigma vs baseline. - Low entropy alert: hash output entropy drops below threshold. - Security alert: many unique keys mapping to one partition OR repeated similar inputs → trigger for possible adversarial input.- Automated responses: when threshold breached, automatically enable salted hashing, divert hot keys to fallback pool, and trigger CI/CD rollback if new partitioning code deployment coincides.

Validation & testing:- Add unit/integration tests that run known adversarial patterns to ensure chosen hash resists collisions.- Chaos tests: inject high-skew synthetic keys in staging to verify autoscaling and fallback behavior.- Periodic audits: run offline distribution checks and re-evaluate hash choice.

Trade-offs & reasoning:- Non-cryptographic hashes (xxHash) are fastest but not safe against crafted inputs — use SipHash/HMAC when inputs are untrusted.- Salting breaks reproducibility — ensure salt is logged/propagated where idempotency matters.- Consistent hashing increases complexity but simplifies rebalancing and reduces blast radius.

This approach detects pathological cases quickly, provides immediate mitigations to restore availability, implements robust long-term fixes, and establishes monitoring/alerts to catch recurrence or malicious inputs.

MediumTechnical

36 practiced

Write a Python function that determines whether an array contains a continuous subarray of length at least two whose sum is divisible by k. Use prefix sums modulo k and a hash map to achieve O(n) time and explain why modulo arithmetic works for this problem.

Sample Answer

Approach: use prefix sums modulo k and a hashmap that records the earliest index where each modulo appeared. If the same modulo value appears again at index j and earlier at i, the subarray (i+1..j) has sum divisible by k. Store index of first occurrence so subarray length >= 2 can be checked.

python

def check_subarray_sum(nums, k):
    """
    Return True if nums has a continuous subarray of length >=2 whose sum is divisible by k.
    O(n) time, O(min(n,k)) space.
    """
    if k == 0:
        # need subarray of length >=2 with sum == 0
        for i in range(len(nums)-1):
            if nums[i] == 0 and nums[i+1] == 0:
                return True
        return False

    seen = {0: -1}  # modulo -> earliest index (prefix before start)
    prefix = 0

    for i, v in enumerate(nums):
        prefix = (prefix + v) % k
        if prefix in seen:
            if i - seen[prefix] >= 2:
                return True
        else:
            seen[prefix] = i  # record earliest index only
    return False

Why modulo works: If sum[0..j] % k == sum[0..i] % k, then their difference sum[i+1..j] is divisible by k (because (A - B) % k == 0). By tracking mod values we detect such pairs in one pass.

Complexity: Time O(n), Space O(min(n,k)) (at most k distinct mod values). Edge cases: k == 0 handled separately; negative numbers OK with Python's modulo; ensure subarray length >=2 by storing earliest index. Alternative: sliding window doesn't apply due to negative/variable values — prefix-mod is correct general method.

Unlock Full Question Bank

Get access to hundreds of Arrays and Hash Map Operations interview questions and detailed answers.

Join thousands of developers preparing for their dream job.