Nuro Software Engineer Interview Questions

LeetCode #528: Random Pick with Weight. Difficulty: Medium. Topics: Array, Math, Binary Search, Prefix Sum, Randomized. Asked at Nuro in the last 6 months.

LeetCode #269: Alien Dictionary. Difficulty: Hard. Topics: Array, String, Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort. Asked at Nuro in the last 6 months.

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

## Problem You have a stream of time-series values. Compute the running average up to each index and find the first index where that running average falls below a given threshold. Return the index, or -1 if it never does. ```python def breakdown_point(values: list[float], threshold: float) -> int: pass ``` **Example:** ``` values = [5.0, 4.0, 6.0, 1.0, 2.0] threshold = 3.5 # running avgs: 5.0, 4.5, 5.0, 4.0, 3.6 -> -1 # never drops below 3.5... wait: 3.6 > 3.5; correct: -1 values = [5.0, 4.0, 6.0, 1.0, 1.0] threshold = 3.5 # running avgs: 5.0, 4.5, 5.0, 4.0, 3.4 -> 4 ``` ## Follow-ups 1. Can you find the breakdown point in a single pass with O(1) extra space? Show the approach. 2. How would you find the breakdown point for a rolling window average (e.g., last 5 values) instead of a cumulative average? 3. If the values represent reliability scores for a distributed system, what does this metric signify operationally? 4. How would you extend this to detect when the running average crosses the threshold in either direction (both up and down crossings)?

## Problem Design a data structure that tracks element frequencies and supports max-frequency queries. ## Likely LeetCode equivalent Similar to LC 895 Maximum Frequency Stack. ## Tags coding, hash_table, design, phone

## Problem A road is divided into segments, each with a posted speed limit. A vehicle's speed is measured at discrete distance intervals. Find all road intervals (as `[start_km, end_km]` pairs) where the measured speed exceeds the speed limit for that segment. Merge adjacent or overlapping violations into single intervals. ```python def speed_violations( speed_limits: list[tuple[float, float, float]], # (start_km, end_km, limit_kph) measurements: list[tuple[float, float]] # (position_km, speed_kph) ) -> list[tuple[float, float]]: # Returns list of [start, end] violation intervals pass ``` **Example:** ``` speed_limits = [(0, 10, 80), (10, 20, 100)] measurements = [(2, 95), (5, 85), (9, 75), (12, 110), (15, 105)] -> [(2.0, 5.0), (12.0, 15.0)] # position 2 and 5 exceed limit 80; 9 does not; 12 and 15 exceed 100 ``` ## Follow-ups 1. How do you assign each measurement to the correct speed-limit segment efficiently (binary search vs. interval tree)? 2. How would you interpolate between measurement points to estimate the exact position where speed crossed the limit? 3. What is the time complexity of your merging step, and can it be done in O(n) if inputs are already sorted? 4. How would you adapt this for average-speed cameras that compute average speed between two fixed points?

## Problem Navigate through a maze grid from start to finish, typically finding the shortest path. ## Likely LeetCode equivalent Similar to LC 490 The Maze or LC 1926 Nearest Exit from Entrance in Maze. ## Tags graph, bfs, matrix, nuro

## Problem Implement the K-Means clustering algorithm for 2D points. Given a list of points and `k`, initialize centroids using the first `k` points, then iterate: assign each point to the nearest centroid, recompute centroids as the mean of assigned points. Stop when assignments no longer change or after `max_iter` iterations. ```python def kmeans( points: list[tuple[float, float]], k: int, max_iter: int = 100 ) -> tuple[list[int], list[tuple[float, float]]]: # Returns (cluster_labels, final_centroids) pass ``` **Example:** ``` points = [(1,1),(1,2),(2,1),(8,8),(8,9),(9,8)] k = 2 -> labels = [0,0,0,1,1,1] centroids = [(1.33,1.33), (8.33,8.33)] # approx ``` ## Follow-ups 1. Why does K-Means not guarantee a global optimum, and how does K-Means++ initialization improve convergence? 2. What metric would you use to choose `k` automatically (elbow method, silhouette score)? 3. K-Means assumes spherical clusters of similar size. What algorithm handles elongated or unequal clusters better? 4. How would you scale this to 1 million high-dimensional points efficiently (mini-batch K-Means, approximate nearest neighbor)?

## Problem You are given a list of bus stops with their positions along a route (in km from route start) and a list of stop names in a claimed order. Validate whether the claimed order is consistent with the physical positions (i.e., monotonically increasing distance). If not, return the corrected order sorted by distance. ```python from dataclasses import dataclass @dataclass class Stop: name: str distance_km: float def validate_stop_sequence( stops: list[Stop], claimed_order: list[str] # stop names ) -> tuple[bool, list[str]]: # Returns (is_valid, corrected_order) pass ``` **Example:** ``` stops = [Stop("A",0), Stop("B",5), Stop("C",10), Stop("D",15)] claimed_order = ["A", "C", "B", "D"] -> (False, ["A", "B", "C", "D"]) claimed_order = ["A", "B", "C", "D"] -> (True, ["A", "B", "C", "D"]) ``` ## Follow-ups 1. How do you handle stops that are not in the provided `stops` list -- raise an error or skip? 2. What if two stops are at the same distance (e.g., two doors of the same station)? How do you break ties in the corrected order? 3. For a circular route (last stop connects back to first), how does the validation logic change? 4. How would you compute the minimum number of swaps needed to transform the claimed order into the correct order?

## Problem Find a triplet in an array satisfying a constraint, using a multi-pointer approach. ## Likely LeetCode equivalent Similar in style to LC 15 3Sum. ## Tags two_pointers, arrays, nuro