Technical Fundamentals Check Questions

Checklist for core technical fundamentals expected of technical roles: algorithms and data structures, time and space complexity analysis (Big-O/Theta/Omega), basic applied mathematics and probability (e.g. Bayes' theorem), cryptography basics (symmetric vs asymmetric, common use cases), and core systems concepts. Used to evaluate whether a candidate can reason about fundamental technical problems and apply foundational techniques, calibrated to the depth appropriate for the candidate's role (e.g. hands-on implementation for engineering roles, conceptual fluency for technical non-coding roles).

MediumTechnical

59 practiced

Explain the memory hierarchy from CPU registers, caches (L1/L2/L3), main memory, to disk. Describe why cache locality (temporal and spatial locality) matters for ML workloads such as mini-batch training and embedding lookups, and give an example optimization that improves cache behavior.

Sample Answer

CPU memory is organized in a hierarchy ordered by speed and size: the fastest/smallest are CPU registers (per-core, single-cycle), then multiple levels of on-chip caches (L1: ~32–64KB, per-core, lowest latency; L2: ~256KB–1MB, per-core or per-cluster; L3: several MBs, shared across cores), then main memory (DRAM, tens of ns latency), and finally persistent storage (SSD/HDD, µs–ms latency). Moving data up this chain is much slower as you go down, so keeping hot data in caches/registers is critical.

Cache locality explains why: temporal locality means if you access X now you’re likely to access X again soon (benefits re-use in cache). Spatial locality means accesses near X (adjacent addresses) are likely soon (benefits because caches fetch whole cache lines, typically 64B).

Why this matters for ML:- Mini-batch training: matrix/tensor operations (GEMM, convolutions) perform many repeated accesses to the same weights/activations; good temporal locality means weights stay in cache across inner loops. Spatial locality matters if tensors are stored contiguously so vectorized loads fetch useful neighboring values.- Embedding lookups: lookups are random and sparse across large tables (poor spatial/temporal locality). Cold random accesses cause many DRAM misses and stall CPUs/GPUs.

Concrete optimization example — tiled (blocked) GEMM / embedding caching:- For dense ops: use cache blocking (tile matrices into sub-blocks sized to fit L1/L2). Process blocks so inner loops reuse data in registers/L1; this reduces DRAM traffic and improves vectorization.- For embeddings: implement an embedding cache + locality-aware batching. Group examples so lookups reuse a small working set (temporal locality) and tile embedding table rows contiguously in memory. Use an LRU cache in fast memory (e.g., on-device DRAM or GPU cache) and prefetch popular indices asynchronously. Measurable effect: reduce cache miss rate, lower per-batch latency, and increase throughput.

Key takeaway: structure data and compute to maximize reuse within small, fast memory (registers/L1/L2) and avoid random large-memory accesses; blockers, prefetching, and caching strategies are practical ways to do that in ML systems.

MediumTechnical

49 practiced

Given a sorted array that may contain duplicates, implement in Python functions find_first(nums, target) and find_last(nums, target) that each run in O(log n) time and return indices of the first and last occurrence of 'target' or -1 if not found. Provide example: nums=[1,2,2,3], target=2 -> first=1, last=2.

Sample Answer

To find the first and last occurrence in O(log n) we use modified binary search that, on finding target, continues searching the left (for first) or right (for last) half to pin down the boundary.

python

def find_first(nums, target):
    lo, hi = 0, len(nums) - 1
    ans = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        elif nums[mid] > target:
            hi = mid - 1
        else:
            ans = mid        # found target, keep looking left
            hi = mid - 1
    return ans

def find_last(nums, target):
    lo, hi = 0, len(nums) - 1
    ans = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < target:
            lo = mid + 1
        elif nums[mid] > target:
            hi = mid - 1
        else:
            ans = mid        # found target, keep looking right
            lo = mid + 1
    return ans

# Example
nums = [1,2,2,3]
print(find_first(nums, 2))  # 1
print(find_last(nums, 2))   # 2

Key points:- Each function is O(log n) time, O(1) extra space.- We record ans when target found and move boundary to continue searching that side.Edge cases:- Empty array -> returns -1- All elements equal to target -> first = 0, last = len-1- Target not present -> returns -1

Alternative: single function returning both boundaries by running these two searches or use bisect from Python stdlib (bisect_left/right) to derive indices.

EasyTechnical

44 practiced

Explain the difference between processes and threads. In CPython, what is the Global Interpreter Lock (GIL)? Describe how the GIL affects CPU-bound versus I/O-bound ML workloads and when you should use multiprocessing instead of multithreading.

HardTechnical

60 practiced

Implement a Union-Find (disjoint set union) data structure in Python with path compression and union by rank. Extend it to track the size of each component and to support rollback (undo last union) for offline dynamic connectivity. Explain time complexity guarantees.

Sample Answer

Approach summary:- Use union-by-rank and path compression, but record every parent/rank/size change on a stack so we can undo (rollback) to a previous state. Each union pushes a marker and the changed entries; rollback pops until marker and restores old values.- Note trade-off: path compression gives near-constant find but may record many changes; for heavy rollback use, prefer union-by-rank without path compression (guaranteed O(log n) finds). Below implementation supports both (path compression by default, can disable).

python

class RollbackDSU:
    def __init__(self, n, compress=True):
        self.n = n
        self.parent = list(range(n))
        self.rank = [0]*n
        self.size = [1]*n
        self.changes = []  # stack of tuples (attr, index, old_value)
        self.markers = []  # positions for union operations
        self.compress = compress

    def find(self, x):
        if self.parent[x] == x:
            return x
        if not self.compress:
            # no path compression: easier to rollback, O(log n) with union-by-rank
            return self.find(self.parent[x])
        # path compression with logging
        root = self.find(self.parent[x])
        if self.parent[x] != root:
            self.changes.append(('parent', x, self.parent[x]))
            self.parent[x] = root
        return root

    def union(self, a, b):
        a = self.find(a); b = self.find(b)
        # marker to group changes for this union
        self.markers.append(len(self.changes))
        if a == b:
            # record a no-op marker by pushing a special marker length unchanged
            return False
        # union by rank
        if self.rank[a] < self.rank[b]:
            a, b = b, a
        # attach b under a; record changes
        self.changes.append(('parent', b, self.parent[b]))
        self.parent[b] = a

        self.changes.append(('size', a, self.size[a]))
        self.size[a] += self.size[b]

        if self.rank[a] == self.rank[b]:
            self.changes.append(('rank', a, self.rank[a]))
            self.rank[a] += 1
        return True

    def snapshot(self):
        # return current change-stack length as a handle for rollback
        return len(self.changes)

    def rollback_to(self, snapshot_len):
        # undo until we reach snapshot_len
        while len(self.changes) > snapshot_len:
            typ, idx, old = self.changes.pop()
            if typ == 'parent':
                self.parent[idx] = old
            elif typ == 'rank':
                self.rank[idx] = old
            elif typ == 'size':
                self.size[idx] = old

    def component_size(self, x):
        return self.size[self.find(x)]

Key points and reasoning:- Every mutation (parent, rank, size) is logged so rollback restores exact previous state.- snapshot() returns a point to rollback to; union pushes changes; rollback_to restores.

Time complexity guarantees:- With path compression + union by rank: amortized inverse-Ackermann α(n) per find/union (very close to O(1)). However, because we log every parent change, a single find with path compression may produce O(depth) logged changes — rollback cost grows accordingly.- If compress=False (no path compression) and union-by-rank: find is O(log n) worst-case, union O(1), rollback O(1) per change (each union makes O(1) changes). This is the common choice for offline dynamic connectivity because it bounds amount of work to rollback.- Rollback_to cost is linear in number of logged changes undone; if you rollback per union, amortized cost is O(α(n)) with compression or O(1) without compression.

Edge cases:- Repeated unions of same component are no-ops (we don't log changes).- Ensure snapshot/rollback boundaries are managed by caller (e.g., divide-and-conquer offline dynamic connectivity).

Trade-offs:- Use compress=True for fastest queries if rollbacks are rare.- Use compress=False for many rollbacks (predictable cost and simpler guarantees).

HardTechnical

51 practiced

Given a weighted directed acyclic graph (DAG) with up to 1,000,000 nodes and sparse edges, describe an algorithm to compute the longest path from a source node s. Discuss time and memory complexity, how to process the graph in streaming or external-memory fashion if necessary, and trade-offs for parallelization.

Sample Answer

Approach (high level):- For a DAG the longest path from source s can be computed by dynamic programming on a topological order: relax outgoing edges in topo order keeping dist[v] = max distance from s to v. This is O(V+E) time and O(V) memory for distances.

Algorithm:1. Compute topological order reachable from s (do DFS/BFS-based Kahn starting from s to avoid visiting unreachable nodes).2. Initialize dist[s]=0, others = -inf.3. Process nodes in topo order: for each edge u->v with weight w, if dist[u] + w > dist[v] update dist[v] and optionally predecessor for path reconstruction.

Time & memory:- Time: O(V_reach + E_reach). With 1e6 nodes and sparse edges (E = O(V)), linear-time is practical.- Memory: O(V) for dist and in-degree / adjacency for reachable subgraph. If edges stored externally, memory depends on how adjacency is accessed.

Streaming / external-memory strategies:- Store graph on disk sorted by source node (CSR-like on disk). Produce topo order via external-memory Kahn's algorithm: maintain in-degree counts on disk or compressed; a queue of zero in-degree nodes can be streamed. Process nodes in batches that fit in memory: read adjacency lists for batch, apply relaxations, write updates to disk or to a key-value store for dist.- Alternatively, perform multi-pass Bellman-like relaxations bounded by DAG depth (but topo DP is single-pass if order known). Use memory-mapped files or RocksDB/LMDB to hold dist and predecessors when V too large.

Parallelization trade-offs:- Partition graph (by node id or METIS) and process in parallel respecting partial order. Use level-synchronous processing: process all nodes with same topological level in parallel (no cross-level dependencies). This gives good parallelism when many independent nodes exist.- Challenges: load imbalance, communication overhead for cross-partition edges, and ensuring global topo ordering or level barriers. Use asynchronous relaxations with eventual consistency (e.g., Bulk Synchronous Parallel) for speed but add complexity.- For ML pipelines: prefer deterministic single-pass topo DP for reproducibility; use parallel level-based passes on large clusters only when throughput demands it and when you handle checkpointing and correctness validation.

Edge cases:- Negative weights okay in DAG since no cycles; if unreachable nodes remain -inf.- If graph not DAG, detect cycle during topo step.

Unlock Full Question Bank

Get access to hundreds of Technical Fundamentals Check interview questions and detailed answers.

Join thousands of developers preparing for their dream job.