Whiteboard and Chromebook Coding Proficiency Questions

Coding interview readiness focusing on solving algorithmic problems on a whiteboard or in a minimal IDE/terminal environment (e.g., Chromebook). Emphasis is on problem-solving approach, data structures and algorithms, time and space complexity analysis, correct and efficient implementation under constraints, and effective communication of thought process during interviews.

HardTechnical

72 practiced

Design and implement in Python a combined Bloom filter for deduplication and Count-Min Sketch for approximate counts to operate on a high-throughput stream with limited RAM. Write code to add items, check membership with possible false positives, and query estimated counts. Explain tuning parameters (bit-array size, num_hashes, width, depth) and accuracy trade-offs for a whiteboard/Chromebook interview.

Sample Answer

We can combine a Bloom filter (for fast dedup/membership with false positives) and a Count–Min Sketch (CMS) (for approximate frequency counts with overestimation) into one class that shares independent hash functions. Approach: use multiple independent hash functions (via murmurhash + salts) to set/check bits for Bloom and to index/update counters for CMS. Tune parameters based on desired false positive rate (Bloom) and error/confidence (CMS).

python

import mmh3
from math import log, ceil
from array import array

class BloomCMS:
    def __init__(self, expected_n, bloom_fp=0.01, cms_epsilon=0.001, cms_delta=0.01):
        # Bloom params: m bits, k hashes
        m = int(- (expected_n * log(bloom_fp)) / (log(2)**2))
        k = int(max(1, round((m/expected_n) * log(2))))
        self.m, self.k = m, k
        self.bloom = array('B', [0]) * m  # byte array for simplicity
        
        # CMS params: width w, depth d
        w = int(ceil(2 / cms_epsilon))
        d = int(ceil(-log(cms_delta)))
        self.w, self.d = w, d
        self.cms = [array('I', [0]) * w for _ in range(d)]
        # salts for hash functions
        self.salts = [i*0x9e3779b1 for i in range(max(k, d))]
    
    def _hashes(self, item, count):
        b = item.encode('utf-8')
        for i in range(count):
            yield mmh3.hash(b, self.salts[i]) & 0x7fffffff
    
    def add(self, item):
        # Bloom set bits
        for h in self._hashes(item, self.k):
            self.bloom[h % self.m] = 1
        # CMS increment
        for i, h in enumerate(self._hashes(item, self.d)):
            self.cms[i][h % self.w] += 1
    
    def might_exist(self, item):
        return all(self.bloom[h % self.m] for h in self._hashes(item, self.k))
    
    def estimate_count(self, item):
        return min(self.cms[i][h % self.w] for i, h in enumerate(self._hashes(item, self.d)))

Key points and tuning:- Bloom: m (bits) grows linearly with expected_n and inversely with desired fp. k ≈ (m/n) ln2 balances insertion/check cost vs fp.- CMS: width w = e/ε gives additive error ≤ ε * total_count with probability 1; depth d = ln(1/δ) reduces probability of large error.Trade-offs:- Memory vs accuracy: larger m/w/d reduces false positives and count error but consumes RAM.- Bloom has false positives but no false negatives. CMS overestimates counts; heavy hitters bias others via collisions.- Hash independence: use distinct salts; in practice non-cryptographic fast hashes suffice.Complexities:- Add: O(k + d) hash ops; Query membership O(k); estimate O(d). Memory O(m + w*d).Edge cases: expected_n misestimate (underprovision increases fp); integer overflow in counters (use larger type); choose salts deterministically for reproducibility.

MediumTechnical

54 practiced

Given an undirected, unweighted graph represented as an adjacency list, implement BFS in Python that returns the shortest path (list of node ids) from source to target. Show how to reconstruct the path using parent pointers and discuss memory/time complexity suitable for up to 1e5 nodes on a Chromebook or whiteboard.

Sample Answer

To find the shortest path in an unweighted undirected graph, use BFS from source and record each node's parent when discovered. Once target is found (or BFS finishes), reconstruct the path by following parent pointers back to source.

Approach:1. Standard BFS with queue (collections.deque).2. Maintain parent dict/array: parent[v] = u when u discovers v.3. Early exit when target found to save work.4. Reconstruct path by walking parents from target to source, then reverse.

python

from collections import deque

def bfs_shortest_path(adj, source, target):
    """
    adj: dict or list where adj[u] yields neighbors of u
    source, target: node ids (assume hashable for dict keys or ints for list indices)
    Returns: list of nodes from source to target inclusive, or [] if no path.
    """
    if source == target:
        return [source]

    q = deque([source])
    parent = {source: None}  # use dict; for 0..n-1 use list of size n for less overhead

    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in parent:       # not visited
                parent[v] = u
                if v == target:
                    # reconstruct path
                    path = [v]
                    while parent[path[-1]] is not None:
                        path.append(parent[path[-1]])
                    return list(reversed(path))
                q.append(v)
    return []  # target not reachable

Key points:- Use a dict for sparse or non-contiguous node ids; use a list/array for contiguous 0..n-1 ids to reduce memory and speed up membership checks.- Early exit upon discovering target avoids full traversal when unnecessary.

Complexity:- Time: O(N + M) where N nodes and M edges (each edge considered once per direction).- Space: O(N) for visited/parent + O(min(N, frontier)) for queue. For N up to 1e5 this is feasible on a Chromebook (parents ~ few MBs if using list of ints; dict uses more but still acceptable).

Edge cases:- source == target- source or target not in graph- disconnected graph- very large degree nodes — still linear overall

Practical memory tips for 1e5 nodes:- If node ids are 0..n-1, use a list of ints (initialized to -1) for parent and a deque; that reduces overhead vs dict.- If memory tight, store parent as array('i') or numpy.int32 to shrink footprint.

HardTechnical

72 practiced

Design and implement a streaming approximation to AUC-ROC that uses fixed memory, for example by bucketing scores into quantiles or histogram bins. Provide Python code that updates bucket counts for incoming (score, label) pairs, computes an approximate ROC curve and area under the curve, and analyze approximation error and runtime for whiteboard/Chromebook presentation.

Sample Answer

Approach: maintain B fixed buckets over score range [0,1] (or adaptively via observed min/max). For each incoming (score, label) increment pos/neg counts in the corresponding bucket. To compute approximate ROC/AUC, treat each bucket as a tied-score group: sweep thresholds from high to low, accumulate TPR/FPR using bucket counts and compute area via trapezoids. Updates are O(1), memory O(B). Error arises from grouping many scores into one bucket; AUC error scales with bucket width and the magnitude of class-mixing within buckets (roughly O(1/B) under smooth score distributions).

Python implementation:

python

import math
from typing import List, Tuple

class StreamingAUC:
    def __init__(self, B: int = 100, lo: float = 0.0, hi: float = 1.0):
        self.B = B
        self.lo = lo
        self.hi = hi
        self.pos = [0] * B
        self.neg = [0] * B
        self.total_pos = 0
        self.total_neg = 0
        self.bin_width = (hi - lo) / B

    def _bin_index(self, score: float) -> int:
        if score <= self.lo: return 0
        if score >= self.hi: return self.B - 1
        return int((score - self.lo) / self.bin_width)

    def update(self, score: float, label: int):
        # label: 1 for positive, 0 for negative
        i = self._bin_index(score)
        if label:
            self.pos[i] += 1
            self.total_pos += 1
        else:
            self.neg[i] += 1
            self.total_neg += 1

    def approximate_roc_auc(self) -> Tuple[List[Tuple[float,float]], float]:
        # build thresholds from high to low bins
        cum_pos = 0
        cum_neg = 0
        points = []  # (FPR, TPR)
        # sweep from highest score bin to lowest
        for i in reversed(range(self.B)):
            cum_pos += self.pos[i]
            cum_neg += self.neg[i]
            tpr = cum_pos / self.total_pos if self.total_pos else 0.0
            fpr = cum_neg / self.total_neg if self.total_neg else 0.0
            points.append((fpr, tpr))
        # ensure (0,0) and (1,1) endpoints
        points = [(0.0,0.0)] + list(reversed(points)) + [(1.0,1.0)]
        # trapezoidal AUC
        auc = 0.0
        for k in range(1, len(points)):
            x0,y0 = points[k-1]
            x1,y1 = points[k]
            auc += (x1 - x0) * (y0 + y1) / 2.0
        return points, auc

Key points and reasoning:- Bins aggregate tied scores; approximated ROC treats each bin as one threshold — this reduces memory to O(B).- Update cost O(1) per sample; computing AUC or full ROC requires O(B) to sweep bins.- Error analysis: if score distribution and label-conditional CDFs are Lipschitz, discretization error in AUC ≤ C*(hi-lo)/B for some C dependent on class-separation slope. In worst case (adversarial packing of positives/negatives near boundaries) error can be larger but bounded by 0.5 (trivial). With uniform binning, doubling B roughly halves the discretization component of error.- Practical improvements: use adaptive binning (quantile bins via streaming sketches like t-digest or GK) to concentrate bins where score density or label-change is high, reducing error for same B. Another alternative is to maintain online pairwise ranking estimators (O(1) biased estimators) or use reservoir sampling + exact AUC on sample.- Edge cases: no positives/negatives, extreme scores outside initial range (handle by clamping or dynamic rescaling), highly skewed classes (use class-weighted diagnostics).- Runtime: update O(1), compute AUC O(B). Memory: O(B). Trade-offs: larger B -> better accuracy, more compute for reporting.

HardSystem Design

69 practiced

Sketch and implement pseudocode in Python for a parameter server that supports asynchronous SGD updates from workers. Provide APIs for pull and push, show how to perform atomic updates or versioned updates, add a simple bounded staleness mechanism, and discuss communication compression techniques like quantization or sparsification for whiteboard/Chromebook explanation.

Sample Answer

Requirements:- API: pull(keys, version_hint) and push(gradients, worker_id, version)- Asynchronous SGD with optional bounded staleness (max_delay)- Atomic or versioned updates to avoid lost updates- Compression: quantization & sparsification options

High-level design:- Parameter server holds parameters dict, a per-key version, and a global logical clock.- Workers pull parameters with version; they compute gradients and push (grad, base_version).- Server applies push iff (global_clock - base_version) <= max_delay (staleness bound) or uses versioned merge.- Use locks per-key for atomic apply or use compare-and-swap on versions.

Python pseudocode (simplified):

python

import threading
from collections import defaultdict

class ParamServer:
    def __init__(self, params, max_delay=5, compress=None):
        self.params = params              # {key: np.array}
        self.versions = defaultdict(int)  # {key: int}
        self.lock = defaultdict(threading.Lock)
        self.global_clock = 0
        self.max_delay = max_delay
        self.compress = compress          # 'quantize' or 'sparsify' or None

    def pull(self, keys):
        # Return params and their versions (snapshot)
        snapshot = {}
        for k in keys:
            with self.lock[k]:
                snapshot[k] = (self.params[k].copy(), self.versions[k])
        return snapshot

    def push(self, grads, base_versions, worker_id=None):
        # grads: {key: grad_array}, base_versions: {key: int}
        self.global_clock += 1
        for k, g in grads.items():
            # optional decompression
            if self.compress == 'quantize':
                g = dequantize(g)
            elif self.compress == 'sparsify':
                g = densify(g)

            # bounded staleness check
            if self.global_clock - base_versions.get(k, 0) > self.max_delay:
                continue  # drop or treat specially

            # atomic update per key
            with self.lock[k]:
                # versioned update (compare-and-apply)
                if base_versions.get(k, 0) <= self.versions[k]:
                    # apply SGD: theta -= lr * grad
                    self.params[k] -= lr_schedule() * g
                    self.versions[k] += 1

Key points and trade-offs:- Atomicity: per-key locks are simple and fine-grained; for throughput, use sharded locks or lock-free CAS on versioned sharded memory.- Versioned updates let you detect out-of-order or duplicate pushes; you can reject or re-scale stale grads.- Bounded staleness: max_delay trades model convergence vs throughput; small values approximate synchronous SGD, large values increase asynchrony.- Compression: - Quantization (e.g., 8-bit, 1-bit SGD): reduce bandwidth; need stochastic rounding and error-feedback to avoid bias. - Sparsification: send top-k gradients or thresholding; keep residuals (error compensation) on workers.- Additional optimizations: gradient accumulation, batching, consistent hashing for sharding, TLS/auth for secure comms, monitoring of worker lag and adaptive staleness.

This design is suitable for a whiteboard or Chromebook explanation: show snapshot pull, push with version checks, bounded staleness gate, and mention compression + error-feedback to preserve convergence.

MediumTechnical

111 practiced

Implement longest_nonrepeat_substring(s) in Python to return the length of the longest substring without repeating characters. Achieve O(n) time using sliding-window and a last-seen index map. Provide examples and discuss edge cases such as Unicode and very long inputs on a Chromebook.

Sample Answer

To solve this in O(n) time, use a sliding window [i, j) and a hashmap that stores the last index where each character was seen. When a repeating character is encountered inside the window, advance the left pointer i to last_seen[c] + 1 to ensure no duplicates. Track max length as you expand the right pointer.

python

def longest_nonrepeat_substring(s: str) -> int:
    """
    Return length of longest substring without repeating characters.
    O(n) time, O(min(n, |charset|)) space.
    """
    last_seen = {}        # char -> last index
    i = 0                 # left of window
    max_len = 0
    for j, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= i:
            # move left past previous occurrence to maintain no-repeat
            i = last_seen[ch] + 1
        last_seen[ch] = j
        max_len = max(max_len, j - i + 1)
    return max_len

Key points:- Uses indices to avoid slicing/copies; in-place O(1) per char work.- Handles Unicode correctly because Python strings are sequences of codepoints.- Space complexity typically O(min(n, charset_size)) — e.g., up to number of distinct characters seen.

Examples:- "" -> 0- "abcabcbb" -> 3 ("abc")- "bbbbb" -> 1- "pwwkew" -> 3 ("wke")- "a😊b😊c" -> 3 ("b😊c")

Edge cases & practical notes:- Empty string returns 0.- Very long inputs on low-memory devices (e.g., Chromebook): algorithm is already streaming-friendly (one pass). If input is too large to fit in memory, process as a stream and maintain a sliding structure; however, last_seen may still grow with distinct characters—consider bounding charset (e.g., byte-level) or evicting seldom-used entries if approximate answers are acceptable.- If you need byte-level behavior or faster indexing for ASCII, consider working on bytes(s, 'utf-8') keeping in mind multi-byte characters.

Unlock Full Question Bank

Get access to hundreds of Whiteboard and Chromebook Coding Proficiency interview questions and detailed answers.

Join thousands of developers preparing for their dream job.