Python Data Structures and Algorithms Questions

Core Python data structure and algorithm knowledge used for manipulating collections and solving common data processing problems. Candidates should know built in types such as lists, dictionaries, sets, and tuples and their performance characteristics; be able to implement and reason about searching, sorting, counting, deduplication, and frequency analysis tasks; and choose appropriate algorithms and data structures for time and space efficiency. Familiarity with Python standard library utilities such as collections.Counter, defaultdict, deque, and heapq is expected, as is writing Pythonic, clear code that handles edge cases. Questions may include algorithmic trade offs, complexity analysis, and applying these techniques to practical data manipulation problems where custom logic is required beyond what pandas or NumPy provide.

HardTechnical

21 practiced

Write Python code to compute MinHash signatures for a list of tokenized documents and then use LSH (banding) to generate candidate pairs for high Jaccard similarity. Provide functions to compute k MinHash values per document and to bucket signatures into bands. Explain parameter choices (k and bands) and trade-offs between false positives and false negatives.

Sample Answer

Approach: Use multiple independent hash functions to compute k MinHash values per document (approximate set permutation via random linear hashes mod a large prime). Then split each k-length signature into b bands of r rows (k = b * r). For each band, hash the band tuple to a bucket; documents that share a bucket in any band are candidate pairs.

python

import random
from collections import defaultdict
from itertools import combinations

# generate hash functions: h(x) = (a*x + b) % prime
def make_hashes(k, max_shingle_id, seed=42):
    random.seed(seed)
    prime = 2**31 - 1
    hashes = []
    for _ in range(k):
        a = random.randint(1, prime-1)
        b = random.randint(0, prime-1)
        hashes.append((a, b, prime))
    return hashes

def minhash_signature(tokens, hashes):
    # tokens: iterable of integer token ids
    sig = []
    for a, b, p in hashes:
        min_hash = min(((a * t + b) % p) for t in tokens) if tokens else p
        sig.append(min_hash)
    return sig

def lsh_banding(signatures, bands):
    # signatures: dict doc_id -> list(signature)
    # bands: number of bands b; rows r = k//b
    k = len(next(iter(signatures.values())))
    assert k % bands == 0
    r = k // bands
    buckets = [defaultdict(list) for _ in range(bands)]
    for doc_id, sig in signatures.items():
        for i in range(bands):
            start = i * r
            band_tuple = tuple(sig[start:start + r])
            buckets[i][hash(band_tuple)].append(doc_id)
    candidates = set()
    for band in buckets:
        for bucket_docs in band.values():
            if len(bucket_docs) > 1:
                for a, b in combinations(sorted(bucket_docs), 2):
                    candidates.add((a, b))
    return candidates

Key concepts:- k controls estimator variance: larger k -> lower variance, better Jaccard estimates.- Banding: probability two docs become candidate ≈ 1 - (1 - s^r)^b where s is true Jaccard; choose (b,r) to create a threshold at s ≈ (1/b)^(1/r).

Trade-offs:- More bands (smaller r) -> higher false positives (easier to match), fewer false negatives.- Fewer bands (larger r) -> fewer false positives, more false negatives.- Increasing k reduces noise but increases compute & storage.

Complexity:- Signature computation: O(k * |tokens|) per doc.- Banding bucketing: O(k * N) time and O(N * k) space.Edge cases:- Empty documents, duplicates in tokens (treat as set), need consistent token hashing (map strings -> ints).

HardTechnical

18 practiced

Design and implement in Python an approximate distinct-count estimator using HyperLogLog to count unique user IDs in a stream. Explain register width/precision, how to hash inputs into registers, merge sketches across shards, and expected error characteristics versus exact counting.

Sample Answer

Approach: use HyperLogLog (HLL) with precision p (number of index bits) → m = 2^p registers. Hash each user ID to a 64-bit value, use the first p bits as register index and the remaining bits to compute the position of the leftmost 1 (rho) which estimates the cardinality contribution. Merge by taking per-register max. Expected relative error ≈ 1.04 / sqrt(m).

python

import hashlib
import math
from struct import unpack

class HyperLogLog:
    def __init__(self, p=14):
        """
        p: precision (number of index bits). m = 2^p registers.
        Typical p between 4..16; p=14 => m=16384, error ~1.04/sqrt(16384)=0.0081 (~0.8%)
        """
        assert 4 <= p <= 16
        self.p = p
        self.m = 1 << p
        self.reg = [0] * self.m

    def _hash64(self, value):
        h = hashlib.sha256(value.encode('utf8')).digest()
        # take first 8 bytes as unsigned 64-bit integer big-endian
        return unpack(">Q", h[:8])[0]

    def _rho(self, w, max_bits):
        # position of first 1-bit starting at MSB in max_bits bits +1
        # if w==0 return max_bits+1
        if w == 0:
            return max_bits + 1
        leading = (w.bit_length() - 1) ^ (max_bits - 1)  # trick: compute leading zeros
        return leading + 1

    def add(self, item):
        x = self._hash64(str(item))
        idx = x >> (64 - self.p)                    # top p bits
        w = x & ((1 << (64 - self.p)) - 1)          # remaining bits
        rank = self._rho(w, 64 - self.p)
        if rank > self.reg[idx]:
            self.reg[idx] = rank

    def merge(self, other):
        assert self.p == other.p
        for i in range(self.m):
            if other.reg[i] > self.reg[i]:
                self.reg[i] = other.reg[i]

    def count(self):
        m = self.m
        # bias-correction constant alpha_m
        if m == 16:
            alpha = 0.673
        elif m == 32:
            alpha = 0.697
        elif m == 64:
            alpha = 0.709
        else:
            alpha = 0.7213 / (1 + 1.079 / m)

        inv_sum = 0.0
        zeros = 0
        for v in self.reg:
            inv_sum += 2.0 ** (-v)
            if v == 0:
                zeros += 1

        E = alpha * m * m / inv_sum

        # small-range correction (linear counting)
        if E <= 2.5 * m and zeros != 0:
            return m * math.log(m / zeros)
        # large-range correction (rare with 64-bit hashing)
        if E > (1 << 32) / 30.0:
            return - (1 << 64) * math.log(1 - E / (1 << 64))
        return E

Key design notes:- Precision p controls memory and error: m = 2^p registers, each register stores small integers. Error ≈ 1.04/√m. Doubling m (p+1) reduces error by √2 and doubles memory.- Register width: theoretical max rho <= (64-p)+1 so 6-12 bits suffice; in Python we use ints but in production use minimal bytes.- Hashing: use a 64-bit uniform hash (SHA-256 truncated or xxhash/CityHash for speed). Uniformity is essential.- Merging: idempotent across shards by elementwise max of registers — enables distributed counting.- Accuracy: HLL is probabilistic — small bias corrections are applied (alpha_m), use linear counting when many zeros. For exact counts use sets but cost O(n) memory; HLL is O(m) memory and O(1) per element.- Edge cases: poor hash => bias; very small cardinalities prefer exact counting; choose p to trade memory vs error.

MediumTechnical

23 practiced

Implement a RunningMedian class in Python that supports add(num) and get_median() using two heaps (max-heap for lower half, min-heap for upper half) so that each insertion is O(log n) and retrieving the median is O(1). Provide code and explain handling even/odd counts and negative numbers.

Sample Answer

Approach: Use two heaps — a max-heap for the lower half and a min-heap for the upper half. In Python heapq implements a min-heap, so store negated values in the max-heap. Keep sizes balanced so their sizes differ by at most 1. Insertion is O(log n); reading median is O(1).

python

import heapq

class RunningMedian:
    def __init__(self):
        # max_heap stores negatives of the lower half
        self.max_heap = []  # max-heap via negatives
        # min_heap stores the upper half normally
        self.min_heap = []

    def add(self, num: float) -> None:
        # Push into appropriate heap
        if not self.max_heap or num <= -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)

        # Rebalance: ensure sizes differ by at most 1
        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap) + 1:
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def get_median(self) -> float:
        if not self.max_heap and not self.min_heap:
            raise IndexError("No elements")
        if len(self.max_heap) > len(self.min_heap):
            return float(-self.max_heap[0])
        if len(self.min_heap) > len(self.max_heap):
            return float(self.min_heap[0])
        # even count: average of tops
        return (-self.max_heap[0] + self.min_heap[0]) / 2.0

Key points:- Negative numbers work naturally because negation preserves ordering; e.g., -(-5) = 5.- For odd total count, the larger heap's top is the median.- For even count, median is average of both heap tops (return float).Complexity: add — O(log n); get_median — O(1). Edge cases: empty structure (raise error), duplicates, large floats. This pattern is widely used in streaming/online ML preprocessing (e.g., robust statistics, rolling metrics).

EasyTechnical

22 practiced

Explain the main Python built-in collection types (list, tuple, set, dict) and their typical use-cases in machine-learning data pipelines. For each type, state average-case time complexity for indexing/access, insertion, deletion, membership test, and key hashing where applicable. Mention mutability/immutability, order-preservation guarantees across modern Python versions, and when you'd prefer one over another in production feature-engineering code.

Sample Answer

Brief summary- list: mutable, ordered sequence. Good for ordered collections, minibatches, pipelines where you append/process examples.- tuple: immutable, ordered. Good for fixed records, keys in dicts, and safe immutability (e.g., caching, hashing).- set: mutable, unordered collection of unique items. Good for deduplication, fast membership tests, vocabulary building.- dict: mutable, mapping key→value, insertion-ordered (Python 3.7+). Primary choice for feature maps, lookup tables, and feature-store rows.

Average-case time complexities (Python built-ins, average-case):- list - indexing/access by index: O(1) - insertion: append amortized O(1); insert at arbitrary position O(n) - deletion: pop() from end amortized O(1); pop(0) or remove at arbitrary pos O(n) - membership (x in list): O(n) - hashing: lists are unhashable- tuple - indexing/access: O(1) - insertion/deletion: not supported (immutable) — must create a new tuple: O(n) - membership: O(n) - hashing: tuple is hashable if all elements are hashable — hash computation O(k) where k = tuple length- set - indexing: not applicable (no order/index) - insertion: O(1) average - deletion: O(1) average - membership (x in set): O(1) average - hashing: elements must be hashable; set operations rely on element hashes O(1) average- dict - key access/getitem: O(1) average - insertion (set key): O(1) average - deletion (del key): O(1) average - membership test for keys (key in dict): O(1) average - hashing: keys must be hashable; dict performance relies on key hash O(1) average

Order-preservation (modern Python)- list: preserves insertion order.- tuple: preserves order (sequence).- dict: insertion-ordered since CPython 3.7 (language spec guarantees it).- set: does not guarantee insertion-order semantics; iteration order can appear stable per run but should be treated as unordered.

When to prefer each in ML production feature-engineering- list: use for ordered pipelines, buffering examples, building minibatches, and where you need positional operations. For numeric arrays prefer numpy arrays or pandas Series/DataFrame for vectorized ops and memory efficiency.- tuple: use for fixed-size records (e.g., (user_id, timestamp)) that need to be keys in caches/dicts or when immutability reduces accidental mutation bugs in concurrent code.- set: use for de-duplicating tokens, fast membership (stopword lookup), building candidate feature sets, or removing duplicates from streaming data. Use frozenset if you need a hashable set (e.g., as dict key).- dict: use for feature maps (feature_name → value), aggregations, lookups (e.g., id→embedding index). For very large, dense numeric features prefer arrays/memory-mapped structures; for high-cardinality mapping, consider specialized key-value stores.

Practical tips- Favor immutability (tuples, frozenset) when using objects as dict keys or for thread-safety.- Prefer dict/set for membership-heavy operations; lists are fine for small sequences.- Convert to appropriate specialized structures (numpy/pandas, arrays, or external stores) when scaling for performance and memory in production.

HardTechnical

34 practiced

You need to deduplicate a collection of very large text blobs (each >1MB) stored on disk. Propose and implement in Python a memory- and I/O-efficient approach that minimizes loading full blobs into memory, uses fingerprinting to avoid false positives, and performs a two-pass verification when needed. Provide code sketches and justify design choices.

Sample Answer

Approach (high level):- 1st pass: compute cheap, fast fingerprints without loading whole blob — use file size + sample-based fast hash (xxhash64) over a few fixed positions (start, middle, end) to quickly group likely duplicates.- 2nd pass: for groups with matching cheap fingerprints, compute a full cryptographic hash (SHA-256) by streaming the file in chunks (e.g., 4MB) to avoid loading >1MB fully.- 3rd (only if needed): if SHA-256 also matches (extremely rare collision), do a final streaming byte-by-byte comparison between two files to guarantee equality.This minimizes I/O and memory and avoids false positives.

Code sketch (python):

python

import os, hashlib
import xxhash

CHUNK = 4 * 1024 * 1024  # 4MB
SAMPLES = [0, 65536, -65536]  # offsets: start, 64KB, 64KB from end

def sample_hash(path):
    size = os.path.getsize(path)
    h = xxhash.xxh64()
    h.update(str(size).encode())
    with open(path, 'rb') as f:
        for off in SAMPLES:
            if off >= 0:
                f.seek(min(off, max(size-1,0)))
            else:
                f.seek(max(size + off, 0))
            chunk = f.read(8192)  # small read
            h.update(chunk)
    return h.intdigest()

def full_sha256(path):
    sha = hashlib.sha256()
    with open(path, 'rb') as f:
        while True:
            b = f.read(CHUNK)
            if not b: break
            sha.update(b)
    return sha.hexdigest()

def bytes_equal(a, b):
    with open(a,'rb') as fa, open(b,'rb') as fb:
        while True:
            ba = fa.read(CHUNK)
            bb = fb.read(CHUNK)
            if not ba and not bb: return True
            if ba != bb: return False

def deduplicate(paths):
    # 1. cheap fingerprinting
    cheap = {}
    for p in paths:
        k = sample_hash(p)
        cheap.setdefault((os.path.getsize(p), k), []).append(p)

    uniques = []
    for group in cheap.values():
        if len(group) == 1:
            uniques.append(group[0]); continue
        # 2. full hash for group members
        by_full = {}
        for p in group:
            h = full_sha256(p)
            by_full.setdefault(h, []).append(p)
        # 3. final verification if multiple same sha
        for h, members in by_full.items():
            rep = members[0]
            uniques.append(rep)
            for other in members[1:]:
                if not bytes_equal(rep, other):
                    uniques.append(other)  # different despite sha (extremely rare)
    return uniques

Key design choices & justification:- Sample-based xxhash64 + size: extremely fast, small reads, groups likely duplicates while keeping FP low.- SHA-256 streaming: cryptographically strong, computed incrementally to avoid memory pressure.- Final streaming byte-compare: absolute equality guarantee if hashes collide.- Chunked I/O (4MB): balances syscalls and memory; adjust to environment.Complexity:- I/O: in best case (few collisions), reads only samples + full reads for actual duplicates; worst-case you stream every file once O(total_bytes).- Memory: O(1) per file (streaming buffers); metadata maps sized by number of files.Edge cases:- Very small files (handles via min offsets), permission errors (catch exceptions in production), concurrent file changes (use file locks or snapshot).

Unlock Full Question Bank

Get access to hundreds of Python Data Structures and Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.