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.

HardSystem Design

16 practiced

Design a distributed LRU caching strategy for a fleet of Python data-processing workers where each worker has a local in-memory cache and Redis is available as a shared store. Explain consistency models (eventual vs strong), eviction coordination, cache-aside vs write-through, warm-up/rehydration, and how to minimize cross-worker cache misses and network overhead.

Sample Answer

Requirements & constraints:- Each Python worker has a small local LRU in-memory cache (hot items).- Redis is a shared larger cache (single source of truth for cached objects).- Low latency, high throughput, tolerate occasional staleness, minimize cross-worker misses and network overhead.

High-level architecture:Workers -> local LRU cache -> Redis (clustered, with TTLs) -> backing datastore (DB/FS) for cold fetches.

Consistency models:- Eventual consistency (default): workers serve from local cache; updates write to Redis then background invalidate/notify others (faster, lower latency, higher throughput). Acceptable when slight staleness is tolerable.- Strong consistency (optional): use Redis as authoritative store and perform synchronous invalidation/compare-and-set (CAS) or use Redis transactions and blocking reads on invalidation—adds latency and complexity; use only for critical keys.

Caching strategy:- Cache-aside for reads/writes (recommended for data pipelines): worker checks local LRU -> Redis -> DB. On miss, fetch from DB, write Redis, populate local cache.- Write-through for writes that must be durable in Redis immediately (use sparingly because of higher write latency).

Eviction coordination & LRU behavior:- Local caches use approximate LRU with size limits. Redis uses its own eviction policy (volatile-lru / allkeys-lru) and TTLs per key.- Coordination: rely on Redis as authoritative capacity manager—local caches only store subset. To avoid stampede on eviction, set slightly shorter TTLs in local caches than Redis TTL and use randomized backoff for refetch.

Invalidation / Notification:- Use Redis Pub/Sub or Redis Keyspace Notifications to broadcast invalidations. When a worker updates or evicts a key in Redis, publish an invalidation message; workers subscribe and remove/refresh local entries.- For high throughput, batch invalidations or use lightweight versioning (incrementing version numbers stored with value). Workers check version on access and refresh if stale.

Warm-up / rehydration:- On worker start, prefetch top-N hot keys (based on Redis LFU counters or external popularity metrics) into local cache. Lazy warm-up for others.- Use background async rehydration threads to prefetch during idle time.

Minimizing cross-worker misses & network overhead:- Favor cache-aside with local first + Redis; use local TTL << Redis TTL to reduce refills.- Maintain popularity statistics (Redis HLL or LFU) to proactively replicate hot keys to workers during warm-up.- Use batching and pipelining for Redis calls; compress large values.- Implement negative caching for frequent misses.

Trade-offs:- Eventual consistency yields lower latency but possible stale reads; strong consistency increases latency and reduces availability.- Pub/Sub invalidation adds network traffic but reduces stale reads; for extreme scale, use versioning and probabilistic invalidation to reduce noise.

Operational notes:- Monitor hit rates (local and Redis), invalidation lag, and network usage. Tune local cache sizes, TTLs, and prefetch thresholds.- Design metrics and dashboards; add circuit-breakers and backpressure on Redis to avoid overload during storms.

MediumTechnical

22 practiced

You need to generate combinations of 10 features taken 3 at a time for feature engineering but some feature pairs are invalid. Implement a Python generator using itertools.combinations that prunes invalid combinations early and stops after N valid combinations. Provide code and explain how pruning reduces work and memory use.

Sample Answer

Approach: generate combinations in a nested way so you can check pairwise validity early. Instead of generating all C(10,3)=120 triples and then filtering, iterate pairs first and skip any invalid pair — this prunes the expensive inner loop. Use a generator that yields up to N valid combinations.

python

from itertools import combinations

def valid_triplets(features, invalid_pairs, max_results):
    """
    features: iterable of feature names (len 10)
    invalid_pairs: set of frozenset({a,b}) representing invalid feature pairs
    max_results: stop after yielding this many valid triplets
    """
    count = 0
    features = list(features)
    n = len(features)
    # iterate first two elements as pairs (ordered by index to avoid duplicates)
    for i in range(n):
        a = features[i]
        for j in range(i+1, n):
            b = features[j]
            if frozenset((a,b)) in invalid_pairs:
                # prune: no third feature will make (a,b,*) valid
                continue
            # only now consider third elements
            for k in range(j+1, n):
                c = features[k]
                # check remaining pair constraints: (a,c) and (b,c)
                if frozenset((a,c)) in invalid_pairs or frozenset((b,c)) in invalid_pairs:
                    continue
                yield (a,b,c)
                count += 1
                if count >= max_results:
                    return

Why this prunes and saves memory/work:- Early pair check avoids the inner loop for all k when a pair is invalid; if many pairs are invalid, you skip many potential thirds.- Generator yields results lazily, so memory stays O(1) (only current triple), unlike building a filtered list.Complexity:- Worst-case still O(n^3) checks (n=10 small), but effective runtime reduces proportional to fraction of pruned pairs.Edge cases:- max_results <= 0 → yields nothing- invalid_pairs must use frozenset for unordered pairs- features should have unique identifiers.

MediumTechnical

17 practiced

Explain Python's built-in sorted() stability and the properties of Timsort. In a pipeline where you need to sort records by (primary_key, timestamp) and maintain stability, describe an efficient approach that minimizes memory overhead and respects ordering. When is it better to sort once with a composite key vs multiple stable sorts?

Sample Answer

Python's sorted() (and list.sort()) is stable: equal-key elements keep their original relative order. That property comes from Timsort, Python’s sorting algorithm: it’s stable, adaptive (detects and exploits existing ordered runs), performs well on partially-sorted data (best-case O(n)), and worst-case O(n log n). Timsort merges runs using a small auxiliary stack and temporary buffers; in practice extra memory is modest, but some temporary space is used during merges.

For sorting records by (primary_key, timestamp) while preserving stability and minimizing memory:

- Preferred simple approach: sort once with a composite key: sorted(records, key=lambda r: (r['primary'], r['timestamp'])). This is a single stable O(n log n) pass, minimal overhead (few tuple allocations or use key functions which Python optimizes). It keeps deterministic ordering and is fastest/simple for in-memory data when you can compute both keys cheaply.

- Alternative using stability (useful when keys are expensive or you want to avoid creating composite keys): perform two stable sorts — first sort by timestamp, then stable-sort by primary_key: 1. records.sort(key=lambda r: r['timestamp']) # stable 2. records.sort(key=lambda r: r['primary']) # stable; ties keep timestamp order This uses two passes but avoids allocating tuples for each element and is handy when you already have data roughly partitioned or when the secondary key is simpler.

When to choose which:- Use one composite-key sort when keys are cheap, dataset fits memory, and you want a single pass (simpler and usually faster).- Use multiple stable sorts when key computation is expensive, when you want to reuse an earlier sort (e.g., timestamp already sorted), or when you can perform an in-place stable sort per partition/group (reduces peak memory and can be parallelized). For very large datasets beyond memory, use external/merge sort (e.g., streaming + chunk-sort + merge, or a distributed sort like Spark’s sortWithinPartitions) to minimize memory.

EasyTechnical

29 practiced

Compare Python list, tuple, set, and frozenset focusing on mutability, hashability, typical memory footprint, and iteration/lookup speed. For a data-engineering pipeline that stores record keys or partition keys, explain when you would choose a tuple vs a list and when a frozenset or set is the right choice.

Sample Answer

Mutability & hashability- list: mutable, unhashable. You can append/modify; cannot be used as dict key or set member.- tuple: immutable, hashable if all elements are hashable. Good for fixed ordered keys.- set: mutable, unhashable; unordered collection of unique hashable elements; supports add/remove.- frozenset: immutable, hashable (if elements hashable); can be used as dict key or set member.

Typical memory footprint- list and tuple store references to objects. Tuples have smaller overhead per element than lists because they’re fixed-size (no over-allocation), so tuples are slightly more memory-efficient.- list over-allocates capacity to allow fast appends, so uses more memory.- set/frozenset store hash buckets; overhead is higher per element than lists/tuples (roughly 2–4x), but avoid duplicates.

Iteration / lookup speed- Iteration: tuple ≈ list (tuples marginally faster due to immutability); sets iterate in arbitrary order, similar or slightly slower depending on hash distribution.- Lookup: lists/tuples O(n) for membership checks; set/frozenset O(1) average for membership due to hashing.- Using tuples as dict keys: dict lookup O(1) with tuple hashing cost once.

When to choose tuple vs list (data-engineering)- Use tuple when the record/partition key is fixed-length and represents a logical immutable composite key (e.g., (date, country, source)). Benefits: can be hashed, safer as immutable key, slightly smaller memory.- Use list when you need to build/modify the collection in-place (accumulating values) or order and mutability matter.

When to choose frozenset vs set- Use set when you need to add/remove membership dynamically (e.g., incremental deduplication, building a bloom-free lookup of seen IDs during processing).- Use frozenset when you need an immutable set as a key (e.g., grouping by an unordered set of attributes) or to ensure no accidental mutation when sharing across threads/tasks; frozenset can be used as a dict key or stored in other sets.

Practical examples- Partition key for shuffle/dict key: use tuple -> dict[tuple,...] or write tuple to parquet partition columns.- Unique group of tags as a key: use frozenset if tag order is irrelevant and you need to key a dict or cache.- Streaming dedupe: use set for seen IDs during job lifetime.

Trade-offs- If memory is critical at very large scale, prefer tuple over list for fixed-size keys and avoid storing duplicate objects (interning, using integers/strings). For massive membership sets, consider probabilistic structures (Bloom filter) instead of large Python sets.

MediumTechnical

17 practiced

Implement a lightweight Count-Min Sketch class in Python with methods add(item) and estimate(item) to approximate frequency counts using a w x d array of counters. Explain the error bounds (epsilon, delta) and how to choose width and depth given a memory budget for an online streaming job.

Sample Answer

To implement a Count-Min Sketch (CMS) we use d pairwise-independent hash functions and a w × d table of nonnegative counters. add(item) increments counters in each row; estimate(item) returns the minimum of the d counters for that item's hashed columns.

python

import mmh3  # murmurhash3; install via pip if needed
from array import array

class CountMinSketch:
    def __init__(self, width, depth, seed=0):
        self.w = width
        self.d = depth
        self.seed = seed
        self.table = [array('Q', [0])*width for _ in range(depth)]
        # above line creates lists; better init per row:
        self.table = [array('Q', [0]*width) for _ in range(depth)]
        self.seeds = [seed + i*0x9e3779b1 for i in range(depth)]

    def add(self, item, count=1):
        s = str(item)
        for i in range(self.d):
            idx = mmh3.hash(s, self.seeds[i]) % self.w
            self.table[i][idx] += count

    def estimate(self, item):
        s = str(item)
        mins = []
        for i in range(self.d):
            idx = mmh3.hash(s, self.seeds[i]) % self.w
            mins.append(self.table[i][idx])
        return min(mins)

Key concepts:- Error guarantee: with width w = ceil(e/epsilon) and depth d = ceil(ln(1/delta)), estimate ≥ true count and with probability ≥ 1-delta error ≤ epsilon * total_count.- Space: O(w*d) counters. Choosing w and d under memory budget M (bytes): let counter_size bytes (e.g., 8 for uint64). Then w*d <= M / counter_size. Solve d = ceil(ln(1/delta)); set w = floor((M / counter_size) / d) to get epsilon ≈ e/w.- Time: add/estimate O(d) per operation.- Edge cases: hash collisions, very large counts (use saturating or big integers), choose counter size to avoid overflow.- Alternatives: Use conservative update to reduce overcounting; use 32-bit counters if memory constrained and acceptable risk.

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.