Algorithms and Data Structures Questions

Comprehensive understanding of core data structures such as arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs, and fundamental algorithms including sorting, searching, traversal, string manipulation, and graph algorithms. Ability to analyze and compare time and space complexity using asymptotic notation such as Big O, Big Theta, and Big Omega, and to reason about trade offs between different approaches. Skills include selecting the most appropriate data structure for a problem, designing efficient algorithms, applying algorithmic paradigms such as divide and conquer, dynamic programming, greedy methods, and graph search, and implementing correct and robust code for common interview problems. At more senior levels, this also covers optimizing for large scale through considerations of memory layout, caching, amortized analysis, parallelism and concurrency where applicable, and profiling and tuning for performance in realistic systems.

HardSystem Design

75 practiced

Design an adaptive sampling algorithm for distributed tracing that keeps storage bounded while preserving good coverage for high-error or high-latency requests. Describe data structures to identify candidate traces for increased sampling, feedback loops from offline analysis, and how to maintain per-service budgets while reacting to anomalies.

Sample Answer

Requirements and constraints:- Bounded global storage (trace budget per time window)- High recall for error/latency-related traces and emerging anomalies- Per-service fairness (budgets) and low overhead- Feedback from offline analysis to improve sampling decisions

High-level architecture:- Frontline sampler per service (lightweight) → Central controller (stream processor + model store) → Long-term storage / offline analyzer → Feedback loop back to controllers

Core components and data structures:1. Local sampler (in-proc): - Fixed-rate baseline sampling (e.g., 1%) - Lightweight heuristic filters: always-sample on HTTP 5xx, high latency > P95 threshold, user-config flags. - Local priority queue of candidate trace heads (ring buffer) storing metadata: trace_id, service, span_count, error_flag, latency_estimate, score, timestamp.2. Central aggregator/controller: - Stream ingests candidate metadata (not full spans) into an in-memory sliding window (time-decayed counters) keyed by service, endpoint, and error-type. - Per-key reservoirs (reservoir sampling) to keep representative trace_ids for escalation. - Global budget manager: transforms global storage budget into per-service budgets using SLO-weighted allocation and recent traffic volume.3. Offline analyzer: - Batch job runs ML/heuristic detection of hot endpoints and parent-child anomaly patterns, outputs rules/models (anomaly signatures, dynamic thresholds).

Adaptive algorithm / feedback:- Scoring function for candidates: score = w1*error_flag + w2*normalized_latency + w3*anomaly_score + w4*risk(SLO_violation)- Local sampler sends metadata for top-K scored traces to controller; controller decides to promote (request full trace) based on per-service budget and global budget headroom.- Reservoir sampling ensures diversity within high-scoring groups; sliding-window counts prevent short-term spikes from starving others.- Offline analysis periodically (e.g., hourly) updates weights, thresholds, and per-endpoint boost rules. New rules pushed to services as config; controller applies temporary priority boosts when offline model flags an emerging pattern.

Per-service budgets and anomaly reaction:- Budget allocation = base_min + traffic_share * remaining_budget + SLO_weight * extra_budget; enforce hard cap and soft cap.- On anomaly detection (controller spike in error rate for a service/endpoint), open a temporary “investigation window”: increase that service’s sampling cap (borrowed from global headroom or via emergency throttling of low-priority traffic). Use circuit-breaker-like limits to avoid budget exhaustion.- Rebalance every minute with decay so temporary boosts fade automatically.

Consistency, overhead, and trade-offs:- Keep only lightweight metadata in stream to minimize bandwidth; full traces fetched on demand.- Trade-offs: small propagation delay for controller decisions vs lower overhead; reservoir/resampling adds complexity but improves representativeness.- Failure modes: controller outage → fall back to local heuristic-only sampling and conservative rate limit; persistent anomalies risk budget starvation — mitigated by SLO-weighted minimum guarantees.

Metrics to monitor:- Fraction of errors captured, P95 latency capture rate, budget utilization, false positives from offline model, time-to-detect new anomaly.

This design balances bounded storage and coverage by combining fast local rules, centralized prioritization with reservoir diversity, and continuous feedback from offline analysis to adapt to evolving failure patterns.

HardTechnical

79 practiced

Given a hot path that iterates over an array of struct objects, propose algorithmic and memory-layout optimizations (struct-of-arrays vs array-of-structs, prefetching, alignment, padding) to improve CPU cache utilization and reduce latency. Provide pseudocode and describe which runtime metrics you would collect to verify improvements as an SRE.

Sample Answer

To optimize a hot loop over an array of structs, focus on cache locality, branch predictability, and reducing wasted memory traffic.

Approach summary:- Convert Array-of-Structs (AoS) to Struct-of-Arrays (SoA) when the loop touches only some fields — this makes accesses contiguous and cache-friendly.- Align and pack arrays to cache-line boundaries (typically 64B). Avoid false sharing by padding per-thread write areas.- Use software prefetching for long strides or predictable future indices.- Minimize working set size: compact types, remove unused fields, use smaller integer widths where safe.- Consider blocking/chunking to keep working set in L1/L2.

Pseudocode (SoA + prefetch + chunking):

python

# assume N elements, process in chunks of CHUNK
for base in range(0, N, CHUNK):
    end = min(N, base + CHUNK)
    for i in range(base, end):
        prefetch(addr_of(value_array[i + PREFETCH_DIST]))
        # operate only on needed arrays (contiguous memory)
        v = value_array[i]
        w = weight_array[i]
        result_array[i] = compute(v, w)

Why: contiguous arrays allow hardware prefetchers to stream; chunking keeps reuse in cache; prefetch hides memory latency for predictable access.

Runtime metrics to verify (as SRE):- CPU cycles, CPI (cycles per instruction)- Cache hit/miss rates: L1/L2/L3 miss rates and bandwidth- Memory bandwidth utilization and DRAM reads- Instructions retired and branch-misprediction rate- Latency P95/P99 of the processed operation- Throughput (ops/sec) and CPU utilization- Perf samples or flamegraphs to confirm reduced memory stalls

Tools: perf/pmu, Intel VTune, Linux perf stat, BPF/tracepoints, hardware counters, and bench harness comparing AoS vs SoA with representative data. Validate improvements: lower L3 misses, reduced CPI, lower P99 latency, increased throughput.

HardTechnical

138 practiced

Implement (conceptually or code sketch) the Aho-Corasick automaton to search for thousands of patterns simultaneously in a stream of log text. Explain building the trie with failure links, how matching proceeds, and why this approach is advantageous for multi-pattern detection in intrusion detection or log-alerting pipelines.

Sample Answer

To detect thousands of patterns in streaming logs efficiently, Aho–Corasick builds a trie of patterns plus failure links so each incoming character advances the automaton in O(1) amortized time and emits all matches at that position.

Approach summary:1. Build trie: insert each pattern; mark terminal nodes with pattern IDs.2. Build failure links with BFS: for each node, failure points to the longest proper suffix node reachable in the trie; propagate output links so you can emit matches via failure chain without extra traversal.3. Streaming match: maintain current node; for each incoming char c, follow child if exists, otherwise follow failure links until root or a child found; then emit any patterns in node.output.

Python sketch:

python

from collections import deque, defaultdict

class Node:
    def __init__(self):
        self.next = {}         # char -> Node
        self.fail = None       # failure link
        self.output = []       # list of pattern ids

def build_automaton(patterns):
    root = Node()
    for i,p in enumerate(patterns):
        node = root
        for ch in p:
            node = node.next.setdefault(ch, Node())
        node.output.append((i, p))
    # build failures
    q = deque()
    for ch, n in root.next.items():
        n.fail = root
        q.append(n)
    while q:
        cur = q.popleft()
        for ch, child in cur.next.items():
            q.append(child)
            f = cur.fail
            while f and ch not in f.next:
                f = f.fail
            child.fail = f.next[ch] if f and ch in f.next else root
            child.output += child.fail.output
    return root

def stream_search(root, stream):
    node = root
    for idx, ch in enumerate(stream):
        while node and ch not in node.next:
            node = node.fail
        node = node.next[ch] if node and ch in node.next else root
        for (pid, pat) in node.output:
            yield (idx - len(pat) + 1, pid, pat)

Key concepts:- Trie compresses shared prefixes; failure links avoid backtracking and let a single pass find all pattern occurrences including overlapping ones.- Outputs are aggregated on nodes to emit multiple matches in O(number of matches) time.

Complexity:- Build: O(sum length of patterns).- Matching: O(L + M) where L = length of stream, M = total matches (amortized O(L)).- Space: O(sum length of patterns * alphabet factor). For large alphabets or pattern sets, memory is the main constraint.

SRE considerations / advantages:- Throughput: single-pass, deterministic performance good for high-rate logs; avoids costly per-pattern regex scans.- Streaming-friendly: automaton state is small and serializable—can resume across rotated logs or distributed workers.- Low latency alerting: immediate multi-pattern detection with minimal CPU spikes.- Scales: combine with sharding (by log source or prefix hashing) and memory optimizations (packed tries, DAWG, or byte-level transitions).- Robust to overlaps and supports counts, rate-limiting alerts, and contextual aggregation.

Edge cases & trade-offs:- Very large pattern sets require trie compression (double-array trie, radix trie), or offloading to specialized engines (hyperscan) for performance.- Unicode -> normalize or byte-encode before insertion to keep alphabet small.- Dynamic updates: rebuild or use incremental insertion with careful failure-link maintenance; for frequent updates, batch rebuilds may be simpler.

This approach gives SREs a high-throughput, low-latency engine for intrusion detection and alerting in log pipelines while keeping predictable CPU and memory behavior.

MediumTechnical

84 practiced

Implement an LRU cache class in Python with methods get(key) and put(key, value). Requirements: both operations O(1), fixed capacity, evict least-recently-used item when full. Provide a usage example and explain the two data structures you used and why they achieve O(1) complexity.

Sample Answer

To implement an LRU cache with O(1) get and put, use a hashmap for O(1) key lookups and a doubly-linked list to maintain usage order (most-recently-used at head, least at tail) so you can move nodes and evict tail in O(1).

python

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

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}  # key -> Node
        # dummy head/tail to avoid edge checks
        self.head, self.tail = Node(0, 0), Node(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        # unlink node
        p, n = node.prev, node.next
        p.next, n.prev = n, p

    def _add_to_head(self, node):
        # insert right after head
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        # mark as recently used
        self._remove(node)
        self._add_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._remove(node)
            self._add_to_head(node)
            return
        if len(self.map) >= self.cap:
            # 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)

Usage example:

python

c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
c.get(1)    # returns 1, now 2 is LRU
c.put(3, 3) # evicts key 2
c.get(2)    # returns -1

Why O(1):- Hashmap provides O(1) access to nodes by key.- Doubly-linked list allows O(1) removal and insertion given the node reference (no traversal), enabling constant-time updates of usage order and eviction.Edge cases: capacity 0 (could raise or no-op), updating existing keys, and ensuring dummy head/tail prevents null checks.

HardTechnical

77 practiced

Implement Tarjan's algorithm in Python to compute strongly connected components (SCCs) of a directed graph and return SCCs that contain more than one node (i.e., cycles). Explain the role of index and lowlink values, the recursion stack, and the time/space complexity. Describe how this helps detect cyclic service dependencies.

Sample Answer

To compute SCCs and return only those with >1 node, use Tarjan's algorithm: DFS assigns each node an index (discovery order) and a lowlink (lowest index reachable via DFS tree + back edges). Nodes are pushed on a stack while in the current recursion frame; when a node's lowlink == its index it is the root of an SCC — pop until that node to form the SCC.

python

def tarjan_scc(graph):
    """
    graph: dict[node] -> list[neighbor]
    returns: list of SCCs (each a list) where len>1
    """
    index = 0
    indices = {}     # node -> index
    lowlink = {}     # node -> lowlink
    onstack = set()
    stack = []
    sccs = []

    def dfs(v):
        nonlocal index
        indices[v] = index
        lowlink[v] = index
        index += 1
        stack.append(v)
        onstack.add(v)

        for w in graph.get(v, []):
            if w not in indices:
                dfs(w)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif w in onstack:
                lowlink[v] = min(lowlink[v], indices[w])

        if lowlink[v] == indices[v]:
            comp = []
            while True:
                w = stack.pop()
                onstack.remove(w)
                comp.append(w)
                if w == v:
                    break
            if len(comp) > 1:
                sccs.append(comp)

    for node in graph:
        if node not in indices:
            dfs(node)
    return sccs

Key concepts:- index: discovery timestamp; lowlink: smallest index reachable from node (including back edges).- Recursion stack / onstack ensures we collect nodes belonging to the current SCC and avoids mixing components.- Time: O(V + E) — each node/edge visited once. Space: O(V) for indices, lowlink, stack.

SRE use-case:- Model services as nodes and call/dependency edges. Tarjan finds multi-node SCCs = cyclic dependencies (service A -> B -> C -> A). Detecting these helps identify tight coupling, cascading failure risk, or deployment ordering problems; use results to break cycles (circuit breakers, refactor, or add async boundaries). Edge cases: isolated nodes, self-loops (if you want self-cycle include nodes with self-edge), missing nodes referenced only as targets — ensure graph includes all nodes.

Unlock Full Question Bank

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

Join thousands of developers preparing for their dream job.