Core Data Structures Questions

Fundamental built-in data structures used in everyday programming and coding interviews: arrays/lists, strings, and hash maps (dictionaries). For array-like sequences, cover indexing, slicing or sub-ranging, iteration, common mutation operations (appending, inserting, removing elements), common algorithms such as sorting and reversing, and the memory and performance implications of each. For strings, cover indexing, slicing or substring extraction, common operations such as splitting, joining, trimming, and replacing, and general approaches to string manipulation and pattern processing. For hash maps and dictionaries, cover key value semantics, insertion and lookup, iteration patterns, safe access idioms (defaults, existence checks), and using hash tables for counting and grouping. Candidates should know the time complexity of common operations in plain terms (constant time, linear time, quadratic time) and be able to choose the appropriate structure for a problem and reason about space and performance tradeoffs. Practice should include implementation level manipulation exercises and classic interview problems such as two sum and frequency counting, written clearly in whatever language the candidate is most comfortable with (a specific language may be used for concrete code examples without the underlying concept being tied to it).

EasyTechnical

57 practiced

Write a Python function remove_in_place(lst, predicate) that removes all items from lst for which predicate(item) returns True. The function must modify the input list in place, preserve the original order of remaining elements, and use O(1) extra space (no allocating another list of size n). Provide code and explain time complexity.

Sample Answer

To solve this in-place with O(1) extra space while preserving order, use a read/write pointer (two-pointer). Walk the list once; when predicate(item) is False, write it to the next write position. After loop, truncate the list to the write length using del to mutate same list object.

python

def remove_in_place(lst, predicate):
    """
    Removes items from lst for which predicate(item) is True.
    Modifies lst in-place, preserves order, uses O(1) extra space.
    """
    write = 0  # next index to keep an element
    for read in range(len(lst)):
        item = lst[read]
        if not predicate(item):
            # keep item by moving it to 'write' position if needed
            if write != read:
                lst[write] = item
            write += 1
    # remove the tail elements beyond 'write'
    if write < len(lst):
        del lst[write:]

Key points:- Single pass over the list; stable (order preserved).- Uses constant extra memory (only indices and one local var).- For large lists this avoids allocating another list, useful in SRE scripts that run on constrained agents.

Time complexity: O(n) where n = len(lst). Space complexity: O(1) auxiliary.

Edge cases:- Empty list (no-op).- All items removed -> list becomes empty.- No items removed -> list unchanged object and contents unchanged.

MediumTechnical

86 practiced

You have a list of service records: [{"name": "svc1", "latency": 123}, ...]. Implement a stable sort in Python to order services by descending latency. Explain how Python's Timsort preserves stability and why that might matter when sorting by multiple keys (e.g., latency then name). Discuss time complexity and in-place vs returning a new list.

Sample Answer

To stably sort service records by descending latency in Python, use the list.sort() method with a key and reverse=True (in-place, stable), or sorted() to return a new list. Stability ensures that records with equal latency preserve their original relative order — important when you want to then sort by a secondary key or keep insertion order.

Approach:1. Use key=lambda r: r["latency"] and reverse=True.2. If you need to sort by latency then name, do a single sort with a tuple key or perform successive stable sorts (secondary first, primary last).

Code (in-place):

python

services = [
    {"name": "svc1", "latency": 123},
    {"name": "svc2", "latency": 200},
    {"name": "svc3", "latency": 123},
]

# In-place stable sort by descending latency
services.sort(key=lambda r: r["latency"], reverse=True)

Code (return new list) and multi-key:

python

# Return a new list, primary: latency desc, secondary: name asc
sorted_services = sorted(services, key=lambda r: (-r["latency"], r["name"]))
# or using successive stable sorts:
services.sort(key=lambda r: r["name"])                # secondary (asc)
services.sort(key=lambda r: r["latency"], reverse=True)  # primary (desc)

Why Timsort stability matters:- Python's Timsort is stable: equal-key elements maintain input order. This makes successive sorts reliable for multi-key ordering without extra memory for indices.- Stability preserves deterministic ordering across runs (helps logs, reproducible alerts).

Complexity:- Time: O(n log n) worst-case; Timsort is adaptive and can approach O(n) on partially ordered data.- Space: list.sort() is in-place (O(1) additional list refs, but O(n) temporary stack/arrays in worst case); sorted() returns a new list (O(n) additional).

Edge cases:- Missing latency keys (KeyError) — handle with r.get("latency", 0)- Non-numeric latencies — validate or convert- Very large lists — consider memory for sorted() and stability guarantees (Timsort holds).

EasyTechnical

48 practiced

Explain how slicing works for lists in Python (syntax: lst[start:stop:step]). Describe behavior with negative indices and steps, whether slicing returns a view or a new list, and the time and memory complexity of creating a slice of length k from a list of length n. For SRE tasks, when might copying via slicing be a dangerous choice and what alternatives exist?

Sample Answer

Slicing syntax lst[start:stop:step] returns a new list containing elements from index start up to but not including stop, stepping by step. Omitting start/stop uses list bounds; negative indices count from the end (-1 is last element). A negative step reverses direction: lst[5:1:-1] walks from index 5 down to index 2. Example:

python

lst = [0,1,2,3,4,5]
sub = lst[1:5:2]   # [1,3]
rev = lst[::-1]    # reversed copy [5,4,3,2,1,0]

Important semantics:- Slicing always produces a new list (a shallow copy). It does not return a view; ids differ and mutating the slice won’t change the original list except for shared mutable elements inside.- Time complexity to create a slice of length k from a list of length n is O(k) (iteration and element copies); memory is O(k) additional. Computing slice bounds and skipping is O(1) aside from element copy work.

SRE considerations:- Copies via slicing can be dangerous on large lists or high-frequency code paths: extra memory allocation can increase RAM pressure, GC pauses, OOM risk, or increased latency during incidents.- Alternatives: iterate without copying (for x in itertools.islice(lst, start, stop, step)), use generator expressions, process in-place, or use data structures that support views (numpy arrays or memoryview for bytes/bytearray) when zero-copy semantics are required.

HardSystem Design

48 practiced

Design a streaming top-k system for SRE: you need to keep top-100 most frequent error messages across many services in near-real-time with limited memory. Describe trade-offs between exact counting (hash map + min-heap) and approximate methods (Count-Min Sketch, Space-Saving algorithm). Include error bounds, memory estimates, and when each approach is appropriate.

Sample Answer

Requirements & constraints:- Maintain top-100 most frequent error messages across many services in near-real-time.- High cardinality (millions of distinct messages), limited memory, low update & query latency, occasional merge across shards.

High-level options overview1) Exact counting (hash map for counts + min-heap of size K=100)2) Approximate streaming sketches: Count–Min Sketch (CMS)3) Space‑Saving / Misra–Gries (a.k.a. frequent algorithm)

Exact counting- Design: global or sharded hashmap {message -> count} + min-heap of size 100 to retrieve top-K (or maintain priority structure keyed by count).- Guarantees: exact counts; exact top-K.- Memory: store entry per distinct message. If 10M distinct messages, assume 50 bytes key pointer + message deduping / intern pool + 8 byte count ≈ ~600MB–1GB (depending on string storage). Min-heap negligible.- Trade-offs: precise but scales poorly with cardinality; GC/alloc overhead; network cost to merge shards if distributed.- When: small cardinality, memory available, correctness for alerts required.

Count–Min Sketch (CMS)- Design: d x w array of counters, multiple hash functions; estimate count = min over d hash rows.- Error bounds: with width w = ceil(e/ε) and depth d = ceil(ln(1/δ)), the overestimate error ≤ ε * total_updates with probability 1−δ.- Memory estimate: counters (32-bit): w*d*4 bytes. Example: ε=0.001 (0.1% of traffic), δ=0.01 -> w≈2718, d≈5 → ~54k counters → ~216KB. For ε=1e-4 → ~2.16MB.- Trade-offs: very memory efficient, mergeable (add arrays), but only overestimates; cannot directly produce exact top-K without extra structure; needs heavy-hitter extraction heuristic (scan candidate set).- When: extremely high cardinality, tight memory, approximate thresholds ok, merge across datacenters.

Space‑Saving / Misra–Gries- Design: maintain at most M counters (M≫K, typically a few thousand). On new item: if present increment; else if space free add; else decrement all (or replace minimum with count+1).- Guarantees: every reported count ĉ satisfies true count c ≥ ĉ − N/M, where N is total updates. For heavy hitters, any item with true frequency > N/(M+1) will be in structure.- Memory: M entries storing key+count. Choose M = 10K => if avg key pointer+string ref 50 bytes + 8 byte count ~ 580KB. For M=1000 ~58KB (plus string pool).- Trade-offs: provides explicit candidate keys (good for top-K), bounded error additive N/M, deterministic, easy to merge (take union with careful combining). Better for top-K extraction than plain CMS.- When: want explicit candidate list, bounded additive error, small memory but need real keys.

Comparison summary & recommended SRE strategy- If alerts must fire on exact counts and cardinality is manageable: exact hashmap + min-heap.- If memory is tight and acceptable to have probabilistic overestimates for thresholds: CMS for global frequency estimates; but pair CMS with a small Space‑Saving for candidate extraction.- If goal is top-K with small bounded additive error and fast extraction: Space‑Saving with M = 10–50×K (e.g., M=5k–10k) is a good balance.- For production: use sharded collectors (per host/service) running Space‑Saving (M ~ 2000–10000) to keep candidates, periodically merge summaries centrally (merge cost O(M)). For accurate alert thresholds, validate candidates by querying exact counts in a sampling window or materialize exact counts for top candidates.Operational notes- Choose counter width (32 vs 64 bit) based on total update rate.- Consider evict policies & string interning to reduce memory.- Monitor sketch error by injecting known synthetic keys; surface uncertainty in alert UI (e.g., “±ε*N”).- For SLA-critical alerts prefer hybrid: Space‑Saving for top-K + exact counts for top candidates.

MediumTechnical

60 practiced

Design a configuration loader that merges defaults (immutable), user configuration, and environment overrides. Describe how you'd implement precedence (env > user > defaults), how to access missing keys safely, and how to handle nested dictionaries. Provide a Python sketch using ChainMap or a recursive merge and discuss pros/cons.

Sample Answer

Requirements:- Precedence: env > user > defaults (defaults immutable)- Safe access for missing keys (no KeyError)- Support nested dictionaries (deep overrides)- Easy to reload/validate, suitable for SRE workflows

Design summary:- Keep defaults as an immutable dict (frozenset of tuples or simply treat as read-only).- Load user config (file) and environment vars (flattened keys like SERVICE__DB__HOST).- Two options: ChainMap for non-destructive overlay (shallow) or recursive deep-merge to produce a merged dict.

Implementation sketch — ChainMap (shallow lookups, fast, no copies):

python

from collections import ChainMap
import os
import json

defaults = {"db": {"host": "127.0.0.1", "port": 5432}, "debug": False}
user = json.load(open("config.json"))  # may be nested dict
env = {}  # flatten env vars like DB__HOST=...
for k, v in os.environ.items():
    if "__" in k:
        # map DB__HOST -> ('db','host')
        env[k.lower()] = v

# For shallow/flat keys:
cm = ChainMap(env, user, defaults)

def get(key, default=None):
    return cm.get(key, default)

Recursive merge (recommended for nested dicts; produces single resolved dict):

python

def deep_merge(a, b):
    # returns new dict: b overrides a
    out = dict(a)
    for k, v in b.items():
        if k in out and isinstance(out[k], dict) and isinstance(v, dict):
            out[k] = deep_merge(out[k], v)
        else:
            out[k] = v
    return out

merged = deep_merge(defaults, user)
merged = deep_merge(merged, env_nested)  # env_nested parsed into nested dict
def safe_get(path, default=None):
    cur = merged
    for p in path.split("."):
        if not isinstance(cur, dict) or p not in cur:
            return default
        cur = cur[p]
    return cur

Pros/Cons:- ChainMap: lightweight, no copy, simple reload, but shallow (nested dicts in user won't override subkeys in defaults reliably).- Deep merge: correct semantics for nested structures, produces independent merged state (good for validation), but requires copying and careful handling of lists/typing.Edge cases:- Type mismatch (dict vs scalar) — decide override wins and document.- Secrets: avoid storing sensitive env values in logs.- Validation: run schema validation (pydantic/jsonschema) after merge.

I recommend recursive merge + schema validation for SRE use — clear semantics, safe lookups, and easy to audit.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.