MediumTechnical

37 practiced

Describe algorithms for approximate distinct counting in a stream at low memory (e.g., HyperLogLog vs linear counting). For each method, explain error bounds, mergeability across shards, and when you'd prefer one over the other.

HardTechnical

37 practiced

Implement a simple PageRank power-iteration in Python for a directed graph represented as adjacency lists. Handle dangling nodes and accept parameters: damping factor and convergence tolerance. Discuss convergence guarantees and runtime per iteration.

Sample Answer

To compute PageRank with power iteration we treat the web as a Markov chain: build a column-stochastic transition matrix P where for a node with out-links we distribute probability uniformly to its neighbors; for dangling nodes use the teleport distribution (uniform or personalization). The power iteration repeatedly multiplies the rank vector by the damped transition until L1 change < tol.

python

import math

def pagerank(adj, damping=0.85, tol=1e-6, max_iter=100):
    """
    adj: dict(node -> list(neighbor_nodes)) adjacency list for directed graph
    damping: teleport probability (typically 0.85)
    tol: L1 convergence tolerance
    returns: dict(node -> pagerank score)
    """
    nodes = list(adj.keys() | {v for nbrs in adj.values() for v in nbrs})
    n = len(nodes)
    idx = {v:i for i,v in enumerate(nodes)}
    # build out-degree and neighbor index lists
    out_deg = [0]*n
    nbrs_idx = [[] for _ in range(n)]
    for u, nbrs in adj.items():
        iu = idx[u]
        out_deg[iu] = len(nbrs)
        for v in nbrs:
            nbrs_idx[iu].append(idx[v])
    # initial uniform vector
    r = [1.0/n]*n
    teleport = (1.0 - damping)/n
    for it in range(max_iter):
        new_r = [0.0]*n
        dangling_sum = 0.0
        for i in range(n):
            if out_deg[i] == 0:
                dangling_sum += r[i]
            else:
                share = r[i]/out_deg[i]
                for j in nbrs_idx[i]:
                    new_r[j] += damping * share
        # distribute dangling mass and teleportation
        add = damping * dangling_sum / n + teleport
        new_r = [val + add for val in new_r]
        # check convergence (L1)
        diff = sum(abs(new_r[i]-r[i]) for i in range(n))
        r = new_r
        if diff < tol:
            break
    return {nodes[i]: r[i] for i in range(n)}

Key points:- Dangling nodes: their rank is redistributed uniformly (equivalent to linking to all nodes) to keep P stochastic.- Teleport term avoids reducibility/periodicity and guarantees a unique stationary distribution (by Perron–Frobenius for positive stochastic matrices).- Convergence: power iteration converges geometrically to the dominant eigenvector of the Google matrix; rate governed by spectral gap (1 - |lambda2|). Teleportation (damping<1) ensures gap >0 so convergence is guaranteed.- Per-iteration runtime: O(n + m) where n = |V|, m = |E| (sparse adjacency); memory O(n + m).- Alternatives: use sparse linear algebra solvers, personalized PageRank (non-uniform teleport), or accelerated methods (Arnoldi, extrapolation) for faster convergence on very large graphs.

Edge cases: empty graph, isolated nodes, very small damping (close to 0) which speeds convergence but reduces link signal.

MediumTechnical

39 practiced

Explain Count-Min Sketch: structure, how to estimate frequency, how to choose width and depth given desired error and confidence, and limitations (overestimation, no deletions without variants). Describe a real-world scenario where you'd use it for log analytics.

Sample Answer

Count–Min Sketch (CMS) is a compact, probabilistic data structure for approximate frequency counts over a stream. It uses a 2D array of counters with d rows and w columns and d pairwise-independent hash functions. Each arriving item x is hashed by each h_i producing column j = h_i(x); the counter in row i, column j is incremented.

Estimating frequency:- Query(x): return min_{i=1..d} counter[i, h_i(x)].- Reason: collisions only add positive noise, so the minimum across independent hashes reduces overcount from unrelated items. CMS never underestimates (only overestimates) by construction.

Choosing width and depth:- For additive error ε (i.e., estimate ≤ true_count + ε·N where N is total stream length) and failure probability δ: - w = ceil(e / ε) - d = ceil(ln(1/δ))- Memory ≈ w × d counters. These formulas give provable bounds: with probability ≥ 1−δ the error is ≤ εN.

Limitations:- Overestimation bias due to collisions; heavy skew reduces impact but very heavy tails can still collide.- No native deletions — counts only increase. Workarounds: use Count–Min with conservative updates (decrement carefully) or use Count Sketch (uses signed hashes) to allow unbiased estimates and deletions.- Hash quality matters; adversarial inputs can break guarantees.- Only answers point queries and can find heavy hitters with extra logic.

Real-world log-analytics scenario (Data Scientist use case):- Problem: keep top-k most frequent error messages or IP addresses in high-volume web server logs (hundreds of millions of events) with strict memory limits and real-time dashboards.- Use CMS to maintain approximate counts for each error code/IP. Choose ε = 0.001 (0.1% additive error) and δ = 0.01; w ≈ e/0.001 ≈ 2718, d ≈ 5. Memory: w×d counters (e.g., 2718×5 ≈ 13.6k 4-byte ints ≈ 54KB) — tiny compared to storing all keys.- Query candidates from a small candidate set (observed keys or using a heavy-hitter algorithm combined with CMS) to populate dashboards and trigger alerts when counts exceed thresholds. This provides near-real-time insight while keeping resource usage low.

Why a Data Scientist would choose CMS:- Fast updates and queries (O(d)), tiny memory footprint, and straightforward error bounds let you instrument production streams for monitoring, feature extraction (approximate frequency features), and alerting without full aggregation or costly state stores.

MediumTechnical

45 practiced

Implement an LRU cache in Python with O(1) get and put operations supporting a max capacity. Provide the class interface (get, put) and ensure correct eviction ordering. Discuss thread-safety concerns briefly.

Sample Answer

To implement an LRU cache with O(1) get/put, use a hash map for O(1) key lookup and a doubly linked list to track usage order (most-recent at head, least-recent at tail). On get/put you move accessed node to head. When capacity exceeded, remove tail node and its map entry.

python

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # key -> Node
        # dummy head/tail for simpler inserts/removals
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next, nxt.prev = nxt, prev

    def _add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int):
        node = self.map.get(key)
        if not node:
            return -1
        # move to head (most recently used)
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int):
        node = self.map.get(key)
        if node:
            node.val = value
            self._remove(node)
            self._add_to_head(node)
            return
        if len(self.map) >= self.capacity:
            # evict LRU (tail.prev)
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        new_node = Node(key, value)
        self.map[key] = new_node
        self._add_to_head(new_node)

Key points:- O(1) get/put via hashmap + doubly-linked list.- Space: O(capacity).- Edge cases: capacity <= 0 (should be handled by raising or no-op), updating existing key, storing None values.Thread-safety:- Current implementation is not thread-safe. For concurrent access, protect public methods with a lock (threading.Lock) or use higher-level concurrent structures. For heavy concurrent reads, consider read/write locks or sharded caches to reduce contention.

HardSystem Design

35 practiced

You are joining an events table with a user_profile table and observe extreme skew on a few hot user_ids causing slow stragglers. Propose algorithmic and engineering remedies (salting, replicated small-side, skew-aware partitioning) and explain trade-offs in network I/O and correctness.

Sample Answer

Requirements & constraints:- Large events table (very large, partitioned by event time), smaller user_profile table (much smaller but skewed on a few hot user_ids).- Join events.user_id = user_profile.user_id; current join suffers from extreme key skew causing stragglers.- Need correctness (no duplicates/missing rows), reasonable network I/O, and scalable ETL.

High-level options and trade-offs:

1) Salting on the hot keys (duplicate small-side rows with salt values; add matching salt to events)- How: For N salts, rewrite events for hot user_ids to include salt in key (e.g., user_id||salt) and replicate corresponding profile rows N times with salts.- Pros: Balances load evenly across reducers/partitions; simple to implement in Spark/MapReduce.- Cons: Increased network I/O and storage by ~N× for hot keys; must detect hot keys and manage salt count. Correctness: must ensure deterministic salt assignment so every event matches exactly one profile copy.

2) Replicated small-side broadcast for hot keys (partial broadcast)- How: Identify hot user_ids and broadcast just those profile records to all workers; regular broadcast for small profile set if feasible.- Pros: Eliminates shuffle for hot keys, minimal extra network if number of hot keys small; correctness straightforward.- Cons: Memory pressure on executors; if hot set grows, broadcast becomes expensive. Network I/O shifts from shuffle to broadcast (usually cheaper if tiny).

3) Skew-aware partitioning (range/hash + custom partitioner)- How: Use a custom partitioner that routes hot keys to many partitions (e.g., split hot user_id by hash of event_id) or pre-aggregate events for hot users before join.- Pros: Minimal duplication; keeps network I/O closer to optimal. Pre-aggregation reduces join size.- Cons: More complex logic; may require two-phase processing and careful ordering to preserve join semantics.

Recommended hybrid strategy (practical for a Data Scientist working with Spark):- Detect hot keys via sampling / metrics (e.g., >99.9 percentile).- For very hot keys (top K small): broadcast their profiles to all executors.- For moderately hot keys: apply salting with moderate N (tuned to executor count).- For remaining keys: normal hash-partitioned join.- Additionally, consider pre-aggregating events for hot users if downstream only needs aggregates (avoid full join).

Correctness notes:- Salting must be bijective between salted events and replicated profiles to avoid duplicates or misses.- Maintain idempotency and deterministic salt assignment; document transformation in ETL lineage.- When pre-aggregating, ensure the aggregation semantic matches downstream needs.

Performance considerations:- Monitor network shuffle bytes, executor memory, and task skew metrics; tune salt N and broadcast thresholds iteratively.- Use adaptive query execution (if available) to change plans at runtime.

Data-Centric Algorithmic Problem Solving Questions

Sample Answer

Sample Answer

Sample Answer

Sample Answer

Sample Answer

Unlock Full Question Bank