NVIDIA Interview Questions

A greedy scheduling problem: sort events by start day, then use a min-heap keyed on end day to always attend whichever available event expires soonest, freeing up later days for other events. Getting the greedy proof right — why picking the earliest-ending event is optimal — is the real test, not just implementing a heap. It's a good signal for whether a candidate can reason about interval scheduling and translate that reasoning into an efficient priority-queue-based simulation instead of brute force.

A design problem: implement a stack that supports push, pop, top, and retrieving the minimum element, all in O(1) time. The standard approach keeps a second auxiliary stack that tracks the running minimum alongside the main stack (or stores each element paired with the current minimum at push time), so the minimum is always available without rescanning. It's a compact but effective test of augmenting a basic data structure with just enough extra state to support a new O(1) query.

You're given a reference to a node in a connected undirected graph and must produce a deep copy of the entire graph. The standard solution does a DFS or BFS traversal while maintaining a hash map from original nodes to their clones, so previously cloned nodes are reused instead of duplicated when revisited through a cycle. It's a strong, widely-used signal for graph traversal fundamentals plus correct handling of cycles and already-visited state — a very common building-block interview problem across big tech.

A classic "top-k" selection problem: find the k points closest to the origin out of a larger set. It can be solved with a max-heap of size k (evict the farthest point whenever a closer one is found) for an O(n log k) solution, or with a quickselect-style partition for expected O(n). It's commonly used to see whether a candidate defaults to sorting everything (O(n log n)) or recognizes the more efficient heap/quickselect approaches suited to "top-k" style questions.

This is a weighted random sampling design problem: given an array of weights, repeatedly return an index with probability proportional to its weight. The standard solution builds a prefix-sum array and then binary searches a random value into that prefix-sum range, so it tests whether a candidate can connect probability weighting to cumulative sums and then apply binary search correctly on that derived array. It's a common signal for services that need weighted load distribution or randomized selection, such as routing or recommendation systems.

Given an elevation map, compute how much water it can trap after rain — the water trapped at each index equals the shorter of the tallest bars to its left and right, minus its own height. It's solvable with two pointers in O(1) extra space, with a monotonic stack, or with two precomputed max-prefix/max-suffix arrays, making it a great vehicle for comparing multiple valid techniques in one interview. Its breadth of companies asking it reflects that it's one of the most widely used checks of two-pointer/array reasoning in the entire interview circuit.

A grid graph-traversal problem: count connected components of '1' cells using DFS, BFS, or Union-Find, being careful with boundary checks and marking visited cells so you don't recount. It's one of the most common entry points into grid-based graph problems and is often used as a warm-up before harder multi-source or Union-Find variants. The core signal is whether a candidate can translate a 2D grid into an implicit graph and correctly implement flood-fill without off-by-one or infinite-loop bugs.

Rotate an n x n matrix 90 degrees clockwise in place. The common technique is to transpose the matrix (swap elements across the diagonal) and then reverse each row, though a layer-by-layer four-way swap also works. It's a compact test of in-place matrix manipulation and geometric/index reasoning without needing any extra data structure.

Given a string and a dictionary of words, this asks whether the string can be segmented into a space-separated sequence of dictionary words. The standard solution is DP where dp[i] indicates whether the prefix of length i can be segmented, checking all dictionary words as potential suffixes ending at each position. It's a foundational string-DP problem and often a stepping stone to the harder Word Break II, testing whether a candidate can define and fill a boolean DP array correctly.

This is a shortest-path search on a grid where movement is allowed in all eight directions, so it's solved with BFS from the top-left cell, expanding layer by layer until the bottom-right cell is reached. The core skill being tested is recognizing that BFS (not DFS) guarantees the shortest path in an unweighted graph, plus careful handling of blocked cells and grid boundaries. It's a good warm-up signal for whether a candidate can model a 2D grid as a graph and correctly track visited state to avoid revisiting cells.

A hard problem: find the length of the longest strictly increasing path in a matrix, moving in four directions. It tests whether a candidate can combine DFS with memoization — treating each cell's longest path as a subproblem cached to avoid recomputation — effectively turning the matrix into a DAG (since values only increase along a path) that supports dynamic programming. It's a good signal for recognizing when grid traversal needs memoization to avoid exponential blowup.

This asks for all ways to insert +, -, and * between digits of a string so the resulting expression evaluates to a target, solved via DFS/backtracking that tracks a running value and a separate "last multiplied term" so multiplication precedence can be correctly undone and reapplied. It also requires guarding against invalid leading zeros in multi-digit operands. It's a genuinely tricky combinatorics-plus-arithmetic problem that reveals whether a candidate can manage multiple pieces of backtracking state (partial expression, current value, previous operand) simultaneously.

Combines a BFS to find the shortest transformation-sequence length between two words with a backtracking/DFS pass to reconstruct all shortest paths, typically over a graph of one-letter-different word pairs. It's notoriously easy to write a version that times out — building adjacency lazily (e.g., via wildcard patterns) instead of checking every word pair is the key optimization. This makes it a strong signal for whether a candidate can layer graph traversal with path reconstruction under real performance constraints, not just get a naive version working.

A hard graph problem: given bus routes as sets of stops, find the minimum number of buses needed to travel from a source stop to a target stop. It tests whether a candidate can reframe the problem as BFS over buses (not stops) — building a graph where routes are connected if they share a stop — since naive stop-by-stop BFS is far less efficient. It's a strong signal for graph-modeling creativity, since the natural-seeming approach isn't the efficient one.

A harder follow-up to Number of Islands: first label each existing island via DFS/BFS and record its size, then for every water cell, check which distinct island labels are adjacent to it and sum their sizes plus one to see if flipping that cell creates a larger island. The key subtlety is deduplicating island labels around a single water cell so the same island isn't counted twice. It's a good test of whether a candidate can compose two passes of grid traversal — component labeling followed by a targeted second scan — rather than trying to solve everything in one pass.

Tests recursive divide-and-conquer over balanced-parenthesis-like binary strings: split the string into its top-level balanced substrings, recursively transform each, then sort those substrings to maximize the resulting value before recombining. The insight that special binary strings decompose into swappable balanced units is what separates a working solution from a stuck one. It's a good signal for comfort with recursive structural decomposition and greedy reordering, a less common pattern than typical array or graph problems.

A design problem requiring O(1) get and put operations with least-recently-used eviction, implemented by combining a hash map (for O(1) lookup) with a doubly linked list (for O(1) reordering and eviction from either end). This exact structure underlies real inference key-value caches — it's reportedly one of the most frequently asked design questions at companies building LLM inference systems, since eviction policy for a bounded cache maps directly onto managing GPU memory for attention KV caches. It's a strong test of whether a candidate can compose two data structures to get O(1) across every required operation, not just some of them.

Find the length of the longest substring without repeating characters, the canonical sliding-window problem: maintain a window with two pointers and a hash map/set tracking the last-seen index of each character, jumping the left pointer forward whenever a repeat is found. It's one of the most fundamental sliding-window problems in interviewing and is often used to confirm a candidate can move beyond brute-force substring enumeration to a linear-time two-pointer approach.

A recursive tree-construction problem: find the maximum value in the current subarray to become the root, then recursively build the left and right subtrees from the subarrays on either side of that maximum. It's conceptually simple but a good check on whether a candidate can define and implement a clean recursive divide-and-conquer function with correct subarray bounds. Interviewers often follow up by asking for an O(n) stack-based construction instead of the naive O(n^2) repeated-max-scan approach.

Merging k sorted linked lists efficiently requires either a min-heap holding the current head of each list (repeatedly popping the smallest and pushing its successor) or a divide-and-conquer pairwise merge, both achieving O(N log k). It tests whether a candidate can extend the two-list merge pattern to k lists and reason about the resulting complexity rather than defaulting to an O(Nk) linear scan across lists. Correct pointer management across multiple linked lists under time pressure is the practical difficulty.

Given a list of strings, group the ones that are anagrams of each other. The typical solution hashes each string to a canonical key (either its sorted characters or a fixed-length character-count signature) and groups strings sharing a key in a hash map. It's a straightforward but reliable test of whether a candidate reaches for the right canonicalization strategy and understands the tradeoffs between sorting-based and counting-based keys.

A classic easy-level stack problem: determine whether a string of brackets is validly matched and nested. It tests the fundamental insight that a stack naturally models nested, last-in-first-out matching — pushing opening brackets and popping/comparing on closing ones. Despite its simplicity, it's a reliable early-round filter for whether a candidate reaches for the right data structure immediately rather than over-engineering a solution.

This asks for the maximum profit from a single buy and sell of one share, given a sequence of daily prices. The optimal solution is a single pass that tracks the minimum price seen so far and the best profit achievable by selling at the current price. Despite being an easy problem, it's a useful check for whether a candidate defaults to an unnecessary O(n^2) pairwise comparison or immediately sees the one-pass greedy/DP formulation.

Given an array and a target, find the two indices whose values sum to the target, typically solved in a single pass using a hash map that stores each value's complement as it's seen. It requires no advanced technique, which is exactly the point — it's a fast, low-friction warm-up used to confirm a candidate can reach for a hash map instead of defaulting to a brute-force O(n^2) nested loop.

Given prerequisite pairs, this problem asks whether all courses can be finished, which is equivalent to detecting a cycle in a directed graph. Candidates typically solve it with Kahn's algorithm (in-degree tracking and a queue) for topological sort, or with DFS using a three-color (unvisited/visiting/visited) scheme to catch back edges. It tests fundamental graph modeling skills — representing prerequisites as an adjacency list and correctly distinguishing cycle detection from simple reachability.

This is a multi-source BFS problem: all initially rotten oranges are enqueued simultaneously, and the grid is processed level by level to find the minimum number of minutes until no fresh orange remains (or -1 if some are unreachable). It tests whether a candidate can generalize single-source BFS to multiple simultaneous sources and correctly track elapsed time via BFS levels rather than per-cell distance tracking. A common trap is starting BFS from a single source or forgetting to check for oranges that can never rot.

A canonical unbounded-knapsack dynamic programming problem: given coin denominations and a target amount, find the minimum number of coins needed to make that amount (or determine it's impossible). The standard solution builds a bottom-up DP array where each amount's answer depends on smaller amounts reduced by each coin denomination. It's often used to gauge whether a candidate can correctly set up and reason about a 1D DP recurrence and its base cases, a foundational skill for many other DP problems.

A binary-search problem: find a target value's index in a rotated sorted array in O(log n) time. It tests whether a candidate can identify which half of the array around the midpoint is properly sorted at each step, then decide whether the target falls within that sorted half or the other one. Its wide reach across companies reflects how well it isolates genuine binary-search intuition from candidates who only know the textbook sorted-array version.

One of the most fundamental linked-list problems: reverse the direction of every next pointer, either iteratively with three tracked pointers (prev, current, next) or recursively. It's usually a warm-up used to confirm basic pointer-manipulation fluency before moving into harder problems, and interviewers often ask for both the iterative and recursive versions on the spot to gauge how deeply a candidate understands the mechanics rather than having memorized one form.