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

19 practiced

Implement a sliding_window_median(nums: List[int], k: int) -> List[float] in Python that returns the median for each sliding window of size k over nums. The solution must handle deletions when elements slide out efficiently (use two heaps with delayed-deletion) and achieve O(n log n) overall time. Provide code and explain handling of duplicates.

Sample Answer

Approach: Use two heaps (max-heap for lower half, min-heap for upper half) plus "delayed deletion" hash maps that record elements to be removed when they reach the heap top. Maintain size invariants so len(maxheap) == len(minheap) or maxheap has one extra when k is odd. Rebalance after insert/delete, and prune top of heaps using the delayed maps. This yields O(n log n).

python

import heapq
from typing import List
from collections import defaultdict

def sliding_window_median(nums: List[int], k: int) -> List[float]:
    # maxheap as negatives, minheap as positives
    small, large = [], []
    delayed_small, delayed_large = defaultdict(int), defaultdict(int)
    small_size = large_size = 0

    def prune(heap, delayed):
        # remove elements marked for deletion from top
        while heap:
            val = -heap[0] if heap is small else heap[0]
            if delayed[val] > 0:
                heapq.heappop(heap)
                delayed[val] -= 1
            else:
                break

    def rebalance():
        nonlocal small_size, large_size
        # balance sizes: small can have at most one extra
        if small_size > large_size + 1:
            val = -heapq.heappop(small)
            small_size -= 1
            heapq.heappush(large, val)
            large_size += 1
            prune(small, delayed_small)
        elif small_size < large_size:
            val = heapq.heappop(large)
            large_size -= 1
            heapq.heappush(small, -val)
            small_size += 1
            prune(large, delayed_large)

    def add(num):
        nonlocal small_size, large_size
        if not small or num <= -small[0]:
            heapq.heappush(small, -num); small_size += 1
        else:
            heapq.heappush(large, num); large_size += 1
        rebalance()

    def remove(num):
        nonlocal small_size, large_size
        # lazy delete: mark and adjust logical sizes
        if small and num <= -small[0]:
            delayed_small[num] += 1
            small_size -= 1
            if small_size < 0: small_size = 0
            if -small[0] == num:
                prune(small, delayed_small)
        else:
            delayed_large[num] += 1
            large_size -= 1
            if large_size < 0: large_size = 0
            if large and large[0] == num:
                prune(large, delayed_large)
        rebalance()

    res = []
    for i, num in enumerate(nums):
        add(num)
        if i >= k:
            remove(nums[i - k])
        if i >= k - 1:
            prune(small, delayed_small); prune(large, delayed_large)
            if k % 2 == 1:
                res.append(float(-small[0]))
            else:
                res.append(( -small[0] + large[0] ) / 2.0)
    return res

Key points:- Duplicates: delayed maps count occurrences to delete; a value stays in heap until it reaches top, so duplicates are handled correctly.- Time: O(n log n) because each add/remove is O(log n) and prune pops each element at most once.- Space: O(k) for heaps and maps.- Edge cases: k==0 (invalid), k==1 (medians are numbers), large k > len(nums).

EasyTechnical

16 practiced

Describe the differences between list.sort() and the built-in sorted() function in Python. Explain the role and performance cost of the key function and the fact that Timsort is stable. Give a concrete example: sort a list of (score, id) tuples by score descending then id ascending, showing both approaches.

Sample Answer

list.sort() is an in-place method that mutates the list and returns None; sorted() is a built-in that returns a new sorted list and works on any iterable. Both accept the same arguments: key, reverse, and both use Python’s Timsort (stable, O(n log n) worst-case, O(n) best-case for nearly-sorted data).

Key function: key(item) maps each element to a comparison key. Using key is faster than supplying a custom cmp because keys are computed once per element (decorate–sort–undecorate). However, the key function has a cost: it runs once per element, so an expensive key increases total time by O(n * cost_of_key). If you need multiple sort criteria, prefer a single key that returns a tuple rather than multiple sorts—though stability can also let you sort by secondary key first.

Stability: Timsort is stable, meaning equal keys preserve original order. That enables multi-pass sorts: sort by secondary key first, then primary key.

Example: sort list of (score, id) tuples by score descending, then id ascending.

Using sorted() with key (preferred, single pass):

python

data = [(90, 5), (95, 2), (90, 3), (95, 1)]
# key: (-score, id) => score desc, id asc
sorted_data = sorted(data, key=lambda x: (-x[0], x[1]))
# [(95,1), (95,2), (90,3), (90,5)]

Using in-place multi-pass leveraging stability:

python

data = [(90, 5), (95, 2), (90, 3), (95, 1)]
# secondary: id ascending
data.sort(key=lambda x: x[1])
# primary: score descending
data.sort(key=lambda x: x[0], reverse=True)
# result: [(95,1), (95,2), (90,3), (90,5)]

Complexity: O(n log n) comparisons; key adds O(n) key-compute cost. Use tuple keys for clarity and performance.

EasyTechnical

18 practiced

Compare the average and worst-case time and space complexities of Python's built-in data structures (list, tuple, dict, set) for common operations: indexing, append/appendleft, pop, insert, delete, membership test, and iteration. Give concrete examples of when, in an AI data-processing pipeline (e.g., feature lookup, batched sampling, streaming logs), you would prefer one structure over another and why.

Sample Answer

Summary of average / worst-case complexities (n = number of elements). “Amortized” means occasional resizes can spike cost.

List (Python list - dynamic array)- Indexing (lst[i]): average O(1), worst O(1)- Append (lst.append): average O(1) amortized, worst O(n) on resize- Append left: not supported efficiently (appendleft O(n) if using insert(0, x))- Pop end (lst.pop()): average O(1), worst O(1)- Pop front (lst.pop(0))/insert at front or middle: average O(n), worst O(n)- Insert/delete at arbitrary index: average O(n), worst O(n)- Membership (x in lst): average O(n), worst O(n)- Iteration: O(n)- Space per element: O(1) but contiguous C-array overhead; lists have extra overall capacity (wasted space for amortized growth)

Tuple (immutable sequence)- Indexing: O(1)- Append/insert/pop/delete: not supported (must create new tuple) — creating new tuple is O(n)- Membership: O(n)- Iteration: O(n)- Use when fixed-size, small immutable records or keys (lower overhead than list for small sizes)

Dict (hash table)- Indexing / lookup by key (d[k]): average O(1), worst O(n) (pathological hash collisions or adversarial hashes)- Insert (d[k]=v): average O(1), worst O(n)- Delete (del d[k]): average O(1), worst O(n)- Membership (k in d): average O(1), worst O(n)- Iteration over keys/values/items: O(n)- Space: higher per-entry overhead (hash table, pointers); memory grows to keep load factor low

Set (hash set)- Lookup/add/remove: average O(1), worst O(n) (same hash collision caveat)- Membership (x in s): average O(1)- Iteration: O(n)- Use for dedup, fast membership, set ops (union/intersection) which are typically O(n) or O(min(n,m))

When to prefer which in AI data-processing pipelines (concrete examples & why)- Feature lookup / lookup table for embeddings / metadata: dict. Example: mapping feature_id → embedding file path or metadata. Dict gives O(1) average lookup; keys can be strings/ints. Use dict to avoid linear scans.- Large read-heavy, indexable collections of numeric data (batches of indices, sampled IDs): list or numpy.ndarray. Example: batched sampling of indices for training minibatches — storing indices in a list gives O(1) indexing and cheap iteration; for numeric-heavy workloads prefer numpy arrays for memory & vectorized ops.- Deduping feature IDs or log messages before downstream processing: set. Example: dedupe user IDs seen in a window to avoid duplicate processing; set provides O(1) membership and add.- Streaming logs with sliding window (append and pop-left): collections.deque (not in scope but important). Example: maintain last 1000 events for a rolling feature — deque.append and deque.popleft are O(1).- Immutable record keys passed between processes: tuple. Example: fixed schema feature tuples used as keys in dicts or cache keys — immutable and hashable, small overhead.- Memory-sensitive caches of many small items: consider dict vs list trade-off. Dicts are fast but memory-heavy; if you only need ordered sequence with frequent iteration and index access, list (or array) is more memory-efficient.- Bulk deletion or membership-heavy filters: use set intersection/ comprehension. Example: filter dataset to examples matching any label in allowed_labels_set — using a set for allowed_labels makes checks O(1) per example.

Practical notes- Worst-case O(n) for dict/set is rare in CPython because it uses randomized hashing and resizing; still avoid holding adversarial untrusted keys without hashing safeguards.- For very large numeric data, use specialized structures (numpy, arrays, memory-mapped files) for lower memory and faster vectorized ops.- Use deque for queue semantics; use list for stack (append/pop) and indexed access; use dict for keyed lookup; use set for membership/dedup.

HardTechnical

21 practiced

You must compute pairwise cosine similarities between 100,000 sparse vectors where each vector has on average 100 non-zero entries. Propose an end-to-end Python implementation plan to minimize compute and memory: data representation, inverted index to find candidate pairs, blocking/sharding strategy, use of scipy.sparse or C-extensions, and estimate operations and memory. Describe how you'd parallelize across machines or cores and reduce IO.

Sample Answer

Approach summary- Represent vectors in CSR sparse format (scipy.sparse.csr_matrix) with float32 data and uint32 indices to minimize memory.- Build an inverted index mapping feature -> sorted array of docIDs (numpy uint32) and optionally weights.- Use inverted-index join to emit candidate pairs only for vectors that share at least one feature; apply frequency-based pruning (ignore very-frequent features) and min-overlap or TF-IDF weighting to reduce candidates.- Compute cosine similarity as dot(u,v) / (||u||*||v||) using sparse dot on candidates; compute norms once.

Code sketch (core parts)

python

import numpy as np
from scipy.sparse import csr_matrix
from collections import defaultdict
import math
from numba import njit

# Example: build CSR from (rows, cols, vals)
def build_csr(rows, cols, vals, n_rows, n_cols):
    return csr_matrix((np.array(vals, dtype=np.float32),
                       (np.array(rows, np.int32), np.array(cols, np.int32))),
                      shape=(n_rows, n_cols)).tocsr()

# Build inverted index: feature -> numpy array of docIDs
def build_inverted(csr):
    inv = {}
    for feat in range(csr.shape[1]):
        start = csr.indptr[feat] if False else None  # inefficient per-col access avoided below
    # efficient way: iterate rows
    postings = defaultdict(list)
    for doc in range(csr.shape[0]):
        start, end = csr.indptr[doc], csr.indptr[doc+1]
        for idx in csr.indices[start:end]:
            postings[int(idx)].append(doc)
    for f, lst in postings.items():
        inv[f] = np.array(lst, dtype=np.uint32)
    return inv

Candidate generation and similarity compute- For each feature f, iterate postings P = inv[f]. For each pair (i,j) in P (combinatorial) accumulate partial dot product in a hash map or use blocked pair-accumulators per shard. To avoid O(|P|^2) explosion, skip features with |P| > threshold (e.g., 1000) or apply TF-IDF and keep top-k features per doc.- Use uint64 key (i<<32 | j) or sorted pair to index accumulator stored in memory-mapped file if large. After accumulating, divide by precomputed norms to get cosine.

Parallelization & sharding- Shard by feature ranges (term-sharding): assign disjoint feature ID ranges to workers; each worker processes its features' postings and writes partial accumulators per pair to per-worker disk (binary). This avoids cross-worker locking.- Reduce phase: merge per-worker partials (sum dot contributions) and compute final similarity only for pairs exceeding threshold.- Alternatively shard by doc blocks: partition docs into B blocks; process block_i x block_j pairs (only j>=i). Each worker loads only the CSR rows for the two blocks (memory-local), computes similarities using sparse-sparse dot (fast when using small blocks), and writes results. Choose block size so CSR slice fits in memory (e.g., 10k docs per block -> CSR rows ~10k*100 nnz=1M entries per block).- Use multiprocessing for multi-core; use Dask or Spark for multi-machine with the same block partitioning.

Performance & memory estimates (100k vectors, avg 100 nnz)- total nonzeros ~ 10M.- CSR storage: indices (10M * 4B) + data (10M * 4B) + indptr (100001 * 4B) ≈ 80 MB.- Inverted postings (same 10M docIDs as uint32): ~40 MB plus dict overhead; store as contiguous arrays to be ~40–80 MB.- Norms: 100k * 4B ≈ 0.4 MB.- Worst-case candidate pairs (naive) = 100k*(100k-1)/2 ≈ 5e9 (impossible). Inverted-index with pruning: expected candidates ≈ sum_f C(|P_f|,2) but with average |P_f| small and frequent-term pruning, practical candidate count typically <<1e8.- Compute: each nonzero contributes to |P_f|-1 pair accumulations. With average posting length m_avg = total_nonzeros / n_features. If n_features large enough that m_avg ~ few, ops ≈ O(total_nonzeros * m_avg). Choose thresholds to keep m_avg small.

Optimizations- Use float32 and uint32 to halve memory.- Pre-filter tokens present in >T docs (stop features) or use IDF-based weighting; keep top-k features per doc by weight.- Use memory-mapped arrays (numpy.memmap) for accumulators to avoid holding huge dicts in RAM.- Implement accumulator updates in C via numba njit or a small C extension for the inner loop over posting pairs to accelerate (tight loops over arrays).- For block doc-block approach, use sparse matrix multiplication with blocks: S_block = A_block * A_block.T using sparse BLAS (scipy.sparse has sparse-sparse multiplication but can be slow); better to compute using efficient dot over dense blocks of projected features (if block density acceptable) or use pybind11 C++ for accumulation.

IO reduction- Keep CSR and inverted index in shared memory or memory-mapped binary files to avoid serialization overhead.- Workers write compressed binary partial results, then an efficient binary merge.- Use batching and streaming: process features/blocks in chunks that fit L2/L3 cache to reduce page faults.

Complexity summary- Preprocessing: O(total_nonzeros) to build structures.- Candidate generation: O(sum_f |P_f|^2) worst-case; mitigated by pruning. Practical: O(total_nonzeros * avg_posting_len).- Similarity computation cost proportional to number of emitted candidate pairs (target << 5e9).

Why this design- CSR + inverted index minimize memory vs dense or full similarity matrix.- Blocking avoids materializing full pair space; sharding enables easy parallelism and low cross-node communication (MapReduce pattern).- C-optimized inner loops and memmap reduce CPU/IO overhead.

Edge cases- Extremely frequent tokens: prune or weight-down.- Very skewed document lengths: normalize and cap top features.- If exact all-pairs needed and candidates still huge, consider locality-sensitive hashing (LSH) to approximate top similarities.

HardTechnical

21 practiced

Design and implement (or provide detailed pseudocode with Python I/O patterns) an external sort utility to sort a file that is larger than RAM. Explain chunking strategy, in-memory sort for chunks, writing temporary files, and a k-way merge using heapq.merge. Discuss choices for chunk size, temp file management, and I/O buffering to minimize disk seeks.

Sample Answer

To implement an external sort in Python for files larger than RAM, split the work: (1) chunk the input into memory-sized sorted runs written to temporary files, (2) perform a k-way merge of runs using heapq.merge streaming to output.

Approach and choices:- Chunk size: choose based on available memory minus overhead (e.g., allow 60–70% of free RAM). Use a target number of lines or bytes; prefer bytes for mixed-length lines. Example: 100MB per chunk.- In-memory sort: read chunk, sort with Timsort (Python's list.sort()).- Temp files: use tempfile.NamedTemporaryFile(delete=False, mode='w+b') or write compressed runs (gzip/lz4) if I/O bound; ensure atomic renames if needed.- I/O buffering: use buffered reads (open with buffering=) and iterate line-by-line to avoid large allocations. Use newline-delimited records.- Merge: open all run files in read mode, wrap as iterators, and use heapq.merge(*iters) which lazily merges sorted iterables with O(n log k) total comparisons but O(1) extra memory.- Limit k by file-descriptor limits; if many runs, do multi-pass merge (merge in groups).

Example implementation (streaming, line-based, numeric or lexicographic sort):

python

import os, tempfile, heapq

def create_sorted_runs(in_path, chunk_bytes=100_000_000):
    runs = []
    with open(in_path, 'rb') as f:
        while True:
            buf = f.read(chunk_bytes)
            if not buf:
                break
            # Ensure we don't split a line; read until newline
            if buf and buf[-1] != ord('\n'):
                rest = f.readline()
                buf += rest
            lines = buf.splitlines()
            lines.sort()
            tf = tempfile.NamedTemporaryFile(delete=False, mode='wb')
            tf.write(b'\n'.join(lines) + b'\n')
            tf.close()
            runs.append(tf.name)
    return runs

def merge_runs(runs, out_path):
    files = [open(r, 'rb') for r in runs]
    try:
        iterators = (map(bytes.rstrip, f) for f in files)  # strip trailing newlines
        with open(out_path, 'wb') as out:
            for line in heapq.merge(*iterators):
                out.write(line + b'\n')
    finally:
        for f in files:
            f.close()
        for r in runs:
            os.remove(r)

# Example usage:
# runs = create_sorted_runs('big_input.txt', chunk_bytes=100_000_000)
# merge_runs(runs, 'big_output.txt')

Key considerations:- Use binary mode to avoid decoding overhead; decode only when necessary.- If records are complex (JSON), parse during in-memory sort and serialize on write.- Tune chunk_bytes for throughput: larger chunks reduce number of runs (fewer merges) but increase memory pressure and GC.- Use OS-level I/O hints (posix_fadvise if available) and large OS buffer sizes; prefer sequential reads/writes to minimize seeks.- For huge numbers of runs, perform hierarchical merging (merge 100 at a time) to respect file-descriptor limits and reduce heap size.

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.