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

68 practiced

Implement efficient top-k and nucleus (top-p) sampling for autoregressive generation in Python pseudocode. Given a list of token log-probabilities, show how to apply temperature scaling, compute top-k truncation or the smallest prefix whose cumulative probability >= p (nucleus), and sample from the resulting truncated distribution in a numerically-stable way.

Sample Answer

Approach: apply temperature scaling to logits (log-probs), convert to stable probabilities using log-sum-exp, then perform either top-k truncation or top-p (nucleus) truncation by sorting descending and selecting smallest set whose cumulative probability >= p. Finally sample from truncated distribution in a numerically-stable way.

python

import math, random
from typing import List, Tuple

def softmax_from_logits(logits: List[float]) -> List[float]:
    # numerically stable softmax
    m = max(logits)
    exps = [math.exp(x - m) for x in logits]
    s = sum(exps)
    return [e / s for e in exps]

def top_k_indices(probs: List[float], k: int) -> List[int]:
    if k <= 0: return []
    return sorted(range(len(probs)), key=lambda i: probs[i], reverse=True)[:k]

def top_p_indices(probs: List[float], p: float) -> List[int]:
    # returns smallest prefix of sorted-by-prob indices with cumulative >= p
    idx = sorted(range(len(probs)), key=lambda i: probs[i], reverse=True)
    cum = 0.0
    out = []
    for i in idx:
        out.append(i)
        cum += probs[i]
        if cum >= p:
            break
    return out

def sample_from_truncated(logits: List[float],
                          temperature: float = 1.0,
                          k: int = None,
                          p: float = None) -> int:
    # logits are log-probabilities (unnormalized)
    if temperature <= 0:
        raise ValueError("temperature must be > 0")
    # temperature scaling: divide logits by temperature
    scaled = [x / temperature for x in logits]
    # convert to probs stably
    probs = softmax_from_logits(scaled)
    # choose truncation
    if k is not None:
        keep = set(top_k_indices(probs, k))
    elif p is not None:
        keep = set(top_p_indices(probs, p))
    else:
        keep = set(range(len(probs)))
    # Build truncated logits (log-probs), set others to -inf
    trunc_logits = [scaled[i] if i in keep else -1e30 for i in range(len(probs))]
    trunc_probs = softmax_from_logits(trunc_logits)  # renormalizes over kept
    # sample
    r = random.random()
    cum = 0.0
    for i, prob in enumerate(trunc_probs):
        cum += prob
        if r < cum:
            return i
    return len(trunc_probs) - 1

Key points:- Use logits and temperature scaling before softmax to avoid precision loss.- top-k selects highest-k tokens; top-p selects minimal set whose cumulative probability ≥ p (sorted by probability).- After truncation, re-normalize by applying softmax to masked logits (mask with large negative).- Complexity: O(n log n) due to sorting; O(n) memory. For large vocab, use partial selection (heap/select) to get top-k in O(n + k log n). Edge cases: p ≤ 0 or p > 1, k > vocab size, identical probs, very small temperature (near-deterministic).

MediumTechnical

54 practiced

Implement serialize(root) and deserialize(data) functions for a binary tree in Python using preorder traversal. The serialized format should be a printable string (e.g., comma-separated with null markers like '#'). Provide code suitable for a whiteboard, explain correctness, and discuss handling of edge cases like empty trees.

Sample Answer

Approach: Use preorder traversal (root, left, right). For serialize, output node values separated by commas and use a null marker '#' for None. For deserialize, read tokens in order and rebuild the tree recursively: when token is '#', return None; otherwise create node and recursively set left and right.

python

# Python implementation using preorder with '#' as null marker

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def serialize(root):
    """Return a comma-separated string representing preorder traversal with '#' for nulls."""
    parts = []
    def dfs(node):
        if node is None:
            parts.append('#')
            return
        parts.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ','.join(parts)

def deserialize(data):
    """Reconstruct tree from preorder string produced by serialize."""
    if not data:
        return None
    tokens = iter(data.split(','))
    def build():
        try:
            t = next(tokens)
        except StopIteration:
            return None
        if t == '#':
            return None
        node = TreeNode(int(t))  # cast as needed (int/float/str)
        node.left = build()
        node.right = build()
        return node
    return build()

Why this is correct:- Preorder with null markers encodes both structure and values uniquely. During deserialize, reading tokens in the same order reconstructs the exact recursion shape because each node consumes exactly its value and the full encodings of its left and right subtrees.

Complexity:- Time: O(n) to serialize and O(n) to deserialize where n is number of nodes (including null markers processed).- Space: O(n) for the output string and recursion stack up to O(h) where h is tree height.

Edge cases:- Empty tree -> serialize returns "#" and deserialize("#") -> None.- Single-node tree, skewed trees, or trees with negative/zero values handled fine.- If node values may contain commas or '#', choose a different escaping or use length-prefix encoding. For large depths, recursion may need conversion to iterative approach to avoid stack overflow.

HardTechnical

53 practiced

Provide Python-like pseudocode to implement blocked/tiled matrix multiplication C = A x B that improves cache locality. Explain why blocking helps on CPU/Chromebook architectures, how tile size affects reuse, and how to choose tile sizes relative to L1/L2 cache to maximize performance.

Sample Answer

To improve cache locality for C = A x B, use blocked (tiled) matrix multiplication: partition matrices into small tiles that fit in cache so each tile is reused multiple times before eviction.

``python

def blocked_matmul(A, B, N, block):
    # A, B, C are N x N (row-major). block is tile size (b).
    C = [[0.0]*N for _ in range(N)]
    for ii in range(0, N, block):
        for jj in range(0, N, block):
            for kk in range(0, N, block):
                i_max = min(ii+block, N)
                j_max = min(jj+block, N)
                k_max = min(kk+block, N)
                # Multiply tile A[ii:i_max, kk:k_max] by B[kk:k_max, jj:j_max]
                for i in range(ii, i_max):
                    Ai = A[i]
                    Ci = C[i]
                    for k in range(kk, k_max):
                        a_ik = Ai[k]            # loaded once per inner loop
                        Bk = B[k]
                        for j in range(jj, j_max):
                            Ci[j] += a_ik * Bk[j]
    return C

Why blocking helps:- Blocking keeps small submatrices (tiles) of A and B in fast caches (L1/L2) so elements are reused for many inner multiplications, dramatically reducing traffic to main memory and improving effective bandwidth and latency.- On CPU/Chromebook architectures with limited cache sizes and modest memory bandwidth, reducing cache misses yields large speedups.

Tile size and reuse:- Tile size b influences temporal reuse: each element loaded into cache is used O(b) times (or b^2 depending on loop order) before eviction.- Too small b underutilizes vector units / prefetchers; too large b causes cache thrashing.

Choosing tile sizes:- Estimate usable cache per tile: for row-major and the above triply-nested tiling, you need to hold one A tile (b*b), one B tile (b*b), and one C tile (b*b) in cache simultaneously → ~3*b^2 elements.- Convert to bytes (double = 8 bytes): bytes ≈ 3*b^2*8.- Target using a fraction of cache (e.g., 50–75% of L1 or maybe L2 if L1 too small). Example: L1 = 32 KB → usable ~20 KB → 20_480 ≥ 3*b^2*8 → b ≈ floor(sqrt(20_480/(24))) ≈ 29 → choose b=24 or 32 tuned for SIMD alignment.- For L2 (e.g., 256 KB) you can use larger tiles or multi-level blocking: outer block sized to fit L2, inner block to fit L1.

Other practical tips:- Use micro-kernels with register blocking to exploit SIMD (pack tiles of B into contiguous buffers).- Align blocks to cache lines (64 B) and consider prefetch and multi-threading (partition ii/jj among threads).- Test empirical performance (auto-tuning) as real hardware prefetchers and associativity affect ideal b.

Complexity: arithmetic O(N^3). Memory traffic drops substantially with good blocking, improving runtime constants. Edge cases: non-square N, small N (fallback to simple matmul), and data types (float32 vs float64 change b).

HardTechnical

101 practiced

Implement wildcard matching is_match(s: str, p: str) -> bool supporting '?' (matches any single character) and '*' (matches any sequence, including empty) using dynamic programming. Provide an O(nm) time DP solution and then optimize to O(min(n,m)) space. Give whiteboard-friendly code and explain transitions.

Sample Answer

Approach: use classic DP where dp[i][j] = whether s[:i] matches p[:j]. Transition:- If p[j-1] == s[i-1] or p[j-1] == '?': dp[i][j] = dp[i-1][j-1]- If p[j-1] == '*': dp[i][j] = dp[i][j-1] (star matches empty) OR dp[i-1][j] (star matches one more char)- Else FalseBase: dp[0][0]=True. dp[0][j] = dp[0][j-1] if p[j-1]=='*' else False.

O(nm) time, O(nm) space implementation (whiteboard-friendly):

python

def is_match(s: str, p: str) -> bool:
    n, m = len(s), len(p)
    dp = [[False] * (m+1) for _ in range(n+1)]
    dp[0][0] = True
    # empty string vs pattern prefix
    for j in range(1, m+1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            elif p[j-1] == '?' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]
    return dp[n][m]

Space optimization to O(min(n,m)): keep smaller dimension as the dp array. Here we optimize to O(m) with one row (previous row preserved). When '*' used, careful ordering: compute current row left→right using prev_row and curr_row for dp[i-1][j] and dp[i][j-1].

python

def is_match_optimized(s: str, p: str) -> bool:
    n, m = len(s), len(p)
    # ensure pattern is the shorter dimension for space if you want O(min(n,m))
    # here we use pattern-length m as width -> O(m) space
    prev = [False] * (m+1)
    prev[0] = True
    for j in range(1, m+1):
        prev[j] = prev[j-1] and p[j-1] == '*'
    for i in range(1, n+1):
        curr = [False] * (m+1)
        # dp[i][0] is False (non-empty s can't match empty pattern)
        for j in range(1, m+1):
            if p[j-1] == '*':
                curr[j] = curr[j-1] or prev[j]
            elif p[j-1] == '?' or p[j-1] == s[i-1]:
                curr[j] = prev[j-1]
        prev = curr
    return prev[m]

Key points:- '*' can match empty (dp[i][j-1]) or consume a char (dp[i-1][j]).- Order matters when using 1D: use prev (row i-1) and curr (row i), iterate j left→right.Complexity:- Time O(n*m)- Space O(m) (can choose min(n,m) by swapping roles if pattern longer than string).

Edge cases:- Multiple consecutive '*' (treated naturally).- Empty s or p.- Large inputs — still O(nm) time; consider greedy two-pointer algorithm for better average performance but DP is robust and proof-friendly.

MediumTechnical

61 practiced

Implement naive 1D convolution conv(signal: List[float], kernel: List[float]) -> List[float] in Python for full convolution (output length = len(signal)+len(kernel)-1). Provide code suitable for a whiteboard and then explain when and how to use FFT-based convolution for large inputs and the trade-offs (accuracy, performance) on CPU-limited devices.

Sample Answer

Approach: compute full 1D convolution by sliding kernel over signal using direct summation (naive O(N*M)). Handle full output length L = N+M-1; treat out-of-bounds as zero.

python

def conv(signal, kernel):
    """
    Naive full 1D convolution.
    signal: list[float], length N
    kernel: list[float], length M
    returns: list[float], length N+M-1
    """
    N, M = len(signal), len(kernel)
    if N == 0 or M == 0:
        return []
    L = N + M - 1
    out = [0.0] * L
    # For each output index, accumulate contributions
    for i in range(L):
        # j iterates over kernel indices; k = i - j is signal index
        s = 0.0
        j_min = max(0, i - (N - 1))
        j_max = min(M - 1, i)
        for j in range(j_min, j_max + 1):
            k = i - j
            s += signal[k] * kernel[j]
        out[i] = s
    return out

Key points:- Time O(N*M), space O(N+M).- Edge cases: empty inputs, non-numeric entries, very large lists.

When to use FFT-based convolution:- Use FFT convolution (via zero-padding and pointwise multiplication) when N and M are large and O(N*M) becomes impractical. FFT reduces complexity to roughly O(K log K) where K = next_power_of_two(N+M-1).- Typical libraries: numpy.fft or scipy.signal.fftconvolve.

Trade-offs on CPU-limited devices:- Performance: FFT wins for large K (break-even depends on constants; often when N*M >> K log K). But for small kernels (e.g., CNN 3–11 taps), direct convolution is faster.- Accuracy: FFT uses floating-point transforms and can introduce rounding errors; windowing/using double precision mitigates this.- Memory: FFT needs extra memory to hold padded arrays and intermediate complex arrays — can be limiting on constrained devices.- Practical approach: benchmark both methods for your sizes; consider overlap-add/overlap-save for streaming; use optimized libraries or integer FFTs if precision and memory matter.

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.