CV Engineer Interview Prep — Algorithms & Data Structures

Focus areas: problems that appear in ML/CV engineer coding screens. Pattern-first: learn the pattern, then apply it across problems.

1. Sliding Window — Video/Temporal Processing

Pattern

Maintain a window of fixed or variable size. Expand right, shrink left when condition violated. Time: O(N) Space: O(W) where W = window size.

Problem: Maximum subarray (Kadane's algorithm)

def max_subarray(arr: list) -> int:
    """Max sum contiguous subarray. Used in temporal attention."""
    max_sum = cur_sum = arr[0]
    for x in arr[1:]:
        cur_sum = max(x, cur_sum + x)
        max_sum = max(max_sum, cur_sum)
    return max_sum

Problem: Sliding window max (monotonic deque)

from collections import deque

def sliding_window_max(nums: list, k: int) -> list:
    """
    Max in every k-length window. Used in temporal max pooling.
    O(N) using monotonic decreasing deque.
    """
    dq = deque()   # stores indices, front = max
    result = []
    for i, x in enumerate(nums):
        # Remove elements outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # Maintain decreasing order
        while dq and nums[dq[-1]] < x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

# Example: max activation in temporal window
# nums = [1,3,−1,−3,5,3,6,7], k=3
# → [3, 3, 5, 5, 6, 7]

2. Two Pointers — Array Manipulation

Problem: Remove duplicates in sorted array (in-place)

def remove_duplicates(nums: list) -> int:
    """Used in NMS de-duplication patterns."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

Problem: Merge intervals (used in temporal track merging)

def merge_intervals(intervals: list) -> list:
    """
    Merge overlapping intervals. 
    Used in object track merging, frame deduplication.
    """
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

3. Binary Search — Threshold Finding

Pattern

Use binary search whenever you can define a monotonic predicate.

Problem: Find best confidence threshold

def find_threshold(scores: list, labels: list, target_precision: float) -> float:
    """
    Binary search for minimum threshold that achieves target precision.
    """
    def precision_at_thresh(t: float) -> float:
        preds = [s >= t for s in scores]
        tp = sum(p and l for p, l in zip(preds, labels))
        fp = sum(p and not l for p, l in zip(preds, labels))
        return tp / (tp + fp + 1e-8) if (tp + fp) > 0 else 0.0

    lo, hi = 0.0, 1.0
    for _ in range(50):   # binary search on real values
        mid = (lo + hi) / 2
        if precision_at_thresh(mid) < target_precision:
            lo = mid
        else:
            hi = mid
    return hi

Problem: Minimum batch size to keep latency ≤ budget

def max_feasible_batch(latency_fn, max_latency_ms: float) -> int:
    """Binary search over batch sizes. Assumes latency is monotone."""
    lo, hi = 1, 512
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if latency_fn(mid) <= max_latency_ms:
            lo = mid
        else:
            hi = mid - 1
    return lo

4. Heap / Priority Queue

Problem: Top-K detections by score

import heapq

def topk_detections(detections: list, k: int) -> list:
    """
    detections: list of (score, box) tuples
    Returns top-K by score in O(N log K).
    """
    # Min-heap of size K
    heap = []
    for score, box in detections:
        heapq.heappush(heap, (score, box))
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

Problem: K-th largest element (Quickselect O(N) avg)

import random

def kth_largest(nums: list, k: int) -> int:
    """Quickselect — average O(N), worst O(N²). Useful in score thresholding."""
    k = len(nums) - k   # convert to 0-indexed kth smallest
    def quickselect(lo, hi):
        pivot = nums[hi]
        p = lo
        for i in range(lo, hi):
            if nums[i] <= pivot:
                nums[i], nums[p] = nums[p], nums[i]
                p += 1
        nums[p], nums[hi] = nums[hi], nums[p]
        if p == k:   return nums[p]
        if p < k:    return quickselect(p+1, hi)
        return quickselect(lo, p-1)
    return quickselect(0, len(nums)-1)

5. Graph Algorithms — Scene Graphs & Dependencies

Problem: Topological sort (pipeline dependency resolution)

from collections import deque

def topological_sort(n: int, edges: list) -> list:
    """
    Kahn's algorithm. Used in ML pipeline DAG scheduling.
    edges: [(u, v)] meaning u must come before v
    Returns: topological order, or [] if cycle detected.
    """
    adj = [[] for _ in range(n)]
    in_degree = [0] * n
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return order if len(order) == n else []

Problem: Connected components (tracking scene objects)

def count_components(n: int, edges: list) -> int:
    """Union-Find (DSU) — O(N α(N)) for connected components."""
    parent = list(range(n))
    rank   = [0] * n

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path compression
            x = parent[x]
        return x

    def union(x, y):
        px, py = find(x), find(y)
        if px == py: return False
        if rank[px] < rank[py]: px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]: rank[px] += 1
        return True

    components = n
    for u, v in edges:
        if union(u, v):
            components -= 1
    return components

6. Dynamic Programming — Sequence Problems

Problem: Longest common subsequence (tracking trajectory matching)

def lcs(s1: list, s2: list) -> int:
    """
    O(N*M). Used in tracking: match predicted tracks to detections.
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Problem: Hungarian algorithm (assignment problem)

# Used in SORT/DeepSORT to match tracks to detections
# In practice, use scipy.optimize.linear_sum_assignment
from scipy.optimize import linear_sum_assignment
import numpy as np

def match_tracks_to_detections(cost_matrix: np.ndarray,
                                threshold: float = 0.7) -> list:
    """
    cost_matrix: (N_tracks, N_detections) IoU cost (1 - IoU)
    Returns list of (track_idx, det_idx) matched pairs.
    """
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    matches = []
    for r, c in zip(row_ind, col_ind):
        if cost_matrix[r, c] < threshold:
            matches.append((r, c))
    return matches

7. String / Hashing — Data Deduplication

Problem: Find duplicate frames (perceptual hashing)

def dhash(image_array, hash_size: int = 8) -> int:
    """
    Difference hash for near-duplicate image detection.
    Compare each pixel to right neighbor → 64-bit hash.
    """
    import numpy as np
    # Resize to (hash_size+1, hash_size)
    img = image_array
    # Flatten difference comparisons to bits
    diff = img[:, 1:] > img[:, :-1]   # (H, W-1) bool array
    return sum(bool(v) << i for i, v in enumerate(diff.flatten()))

def hamming_distance(h1: int, h2: int) -> int:
    """Count differing bits. <= 10 bits → likely duplicate."""
    return bin(h1 ^ h2).count('1')

8. Complexity Cheatsheet for CV Operations

9. Interview Coding Patterns

Pattern 1: "Implement X from scratch" — Template

# 1. Start with the math definition
# 2. Handle edge cases first
# 3. Implement the naive O(N²) version
# 4. Optimize to O(N log N) or O(N) if needed
# 5. Add a 3-line test at the end

Pattern 2: Vectorize with numpy/torch

# Avoid Python loops when operating on arrays
# Prefer broadcasting over explicit indexing
# Example: pairwise L2 distances
def pairwise_l2(A, B):
    # A: (N, D), B: (M, D)
    # Naive: O(N*M*D) loop
    # Fast: |a - b|² = |a|² + |b|² - 2 a·b^T
    A_sq = (A ** 2).sum(dim=1, keepdim=True)   # (N, 1)
    B_sq = (B ** 2).sum(dim=1, keepdim=True).T  # (1, M)
    return torch.sqrt((A_sq + B_sq - 2 * A @ B.T).clamp(min=0))

Pattern 3: Memory-efficient computation

# For large N, compute in chunks to avoid OOM
def chunked_pairwise(A, B, chunk_size=1024):
    results = []
    for i in range(0, len(A), chunk_size):
        results.append(pairwise_l2(A[i:i+chunk_size], B))
    return torch.cat(results)