Verkada Software Engineer Onsite Coding Questions

LeetCode #986: Interval List Intersections. Difficulty: Medium. Topics: Array, Two Pointers, Sweep Line. Asked at Verkada in the last 6 months.

LeetCode #1235: Maximum Profit in Job Scheduling. Difficulty: Hard. Topics: Array, Binary Search, Dynamic Programming, Sorting. Asked at Verkada in the last 6 months.

LeetCode #12: Integer to Roman. Difficulty: Medium. Topics: Hash Table, Math, String. Asked at Verkada in the last 6 months.

LeetCode #1233: Remove Sub-Folders from the Filesystem. Difficulty: Medium. Topics: Array, String, Depth-First Search, Trie. Asked at Verkada in the last 6 months.

LeetCode #981: Time Based Key-Value Store. Difficulty: Medium. Topics: Hash Table, String, Binary Search, Design. Asked at Verkada in the last 6 months.

LeetCode #435: Non-overlapping Intervals. Difficulty: Medium. Topics: Array, Dynamic Programming, Greedy, Sorting. Asked at Verkada in the last 6 months.

LeetCode #56: Merge Intervals. Difficulty: Medium. Topics: Array, Sorting. Asked at Verkada in the last 6 months.

LeetCode #1146: Snapshot Array. Difficulty: Medium. Topics: Array, Hash Table, Binary Search, Design. Asked at Verkada in the last 6 months.

## Problem Design an object-oriented API for controlling a multi-camera system. The API must support switching active cameras, adjusting settings (resolution, framerate, exposure), and streaming frames to registered consumers. ```python from abc import ABC, abstractmethod class Camera(ABC): @abstractmethod def start(self) -> None: ... @abstractmethod def stop(self) -> None: ... @abstractmethod def capture_frame(self) -> bytes: ... @abstractmethod def set_resolution(self, width: int, height: int) -> None: ... class CameraManager: def register(self, cam_id: str, camera: Camera) -> None: ... def activate(self, cam_id: str) -> None: ... def stream(self, cam_id: str, consumer: callable, fps: int) -> None: ... def switch(self, from_id: str, to_id: str, seamless: bool = False) -> None: ... ``` **Scenario:** A security system has 8 cameras. Design how you would allow a client to request a seamless switch with no dropped frames. ## Follow-ups 1. How does the abstract base class enforce the contract across camera hardware types? 2. How would you implement frame buffering to guarantee no frames are dropped during a switch? 3. What design pattern would you use to notify multiple consumers when a new frame is ready? 4. How would you add authentication so only authorized clients can call `switch`?

## Problem The classic coupon collector problem: there are N distinct types of coupons. Each draw gives a uniformly random coupon. Compute the expected number of draws to collect at least one of each type. Also write a simulation to verify the analytical result. ```python def expected_draws(n: int) -> float: # Analytical formula using harmonic numbers # E[T] = N * H(N) where H(N) = sum(1/k for k in 1..N) pass def simulate_draws(n: int, trials: int = 100_000) -> float: # Monte Carlo simulation; returns mean draws per trial pass ``` **Example:** ``` expected_draws(6) -> 14.7 simulate_draws(6) -> ~14.7 (within 1% for 100k trials) ``` ## Follow-ups 1. Derive the expected_draws formula from first principles using the geometric distribution. 2. What is the variance of the number of draws? How do you derive it? 3. If some coupons are twice as likely as others, how does the expected value change? 4. How would you compute the probability of finishing in exactly K draws?

## Problem Given the text of a Python source file, extract all class definitions including their names, base classes, and line numbers. Return a tree representing the inheritance hierarchy among the classes found. ```python from dataclasses import dataclass @dataclass class ClassDef: name: str bases: list[str] line: int def find_classes(source: str) -> list[ClassDef]: # Parse source and return all class definitions pass def build_hierarchy(classes: list[ClassDef]) -> dict[str, list[str]]: # Returns {parent: [child, ...]} for classes defined in the file pass ``` **Example:** ```python source = """ class Animal: pass class Dog(Animal): pass class Poodle(Dog): pass """ find_classes(source) -> [ClassDef("Animal", [], 2), ClassDef("Dog", ["Animal"], 4), ...] build_hierarchy(...) -> {"Animal": ["Dog"], "Dog": ["Poodle"]} ``` ## Follow-ups 1. Should you use regex or `ast.parse`? What are the trade-offs? 2. How do you handle classes with multiple inheritance? 3. How would you extend this to detect diamond inheritance patterns? 4. How would you scale this to analyze an entire repository of 10,000 files?

## Problem Remove the minimum number of intervals to make the rest non-overlapping. ## Likely LeetCode equivalent LC 435 (Non-overlapping Intervals) is the direct match. ## Tags greedy, sorting, intervals

## Problem Given a list of closed intervals [l, r], find all integer positions that are covered by an odd number of intervals. Return the positions as a sorted list. ```python def odd_coverage(intervals: list[tuple[int,int]]) -> list[int]: # intervals: list of [l, r] inclusive # returns: sorted list of integers covered by an odd number of intervals pass ``` **Example:** ``` odd_coverage([(1,4),(2,6),(5,8)]) # Coverage count: 1->1, 2->2, 3->2, 4->2, 5->2, 6->2, 7->1, 8->1 # Odd positions: [1, 7, 8] -> [1, 7, 8] ``` ## Follow-ups 1. What is the difference array technique and how does it solve this in O(n + max_range)? 2. How do you handle very large coordinate ranges (up to 10^9) without allocating a huge array? 3. How would you generalize this to return ranges of odd-coverage rather than individual points? 4. If intervals can overlap at non-integer boundaries (e.g., [1.5, 3.5]), how does your algorithm change?

## Problem You are designing a security camera management system for a building. Each camera has a field of view represented as a 2D polygon. Given the floor plan as a rectangle and N camera polygons, determine what fraction of the floor area is covered and identify uncovered zones. ```python from typing import List, Tuple Point = Tuple[float, float] Polygon = List[Point] class SecurityCameraSystem: def __init__(self, floor_width: float, floor_height: float): ... def add_camera(self, cam_id: str, fov: Polygon) -> None: ... def coverage_fraction(self) -> float: ... def uncovered_regions(self) -> List[Polygon]: ... ``` **Scenario:** 4 cameras cover a 100x50 m floor. A new regulation requires 95% coverage. Your system must flag if the requirement is not met. ## Follow-ups 1. How do you compute the union area of N potentially overlapping polygons? 2. What is the inclusion-exclusion principle and how does it apply here? 3. For large buildings with 500 cameras, how would you spatially index FOVs to speed up coverage queries? 4. How would you handle camera blind spots created by walls or obstacles within the floor plan?