Databricks Interview Questions

A binary-search-on-the-answer problem: instead of searching over indices, you binary search over possible ship capacities and use a greedy simulation to check whether a given capacity can ship all packages within D days. It tests whether a candidate recognizes a monotonic feasibility condition (larger capacity always ships in fewer-or-equal days) and can pair binary search with a linear-time greedy checker. This "binary search on answer" pattern shows up repeatedly across interview problems, so it's often used as a signal for pattern transfer, not just this specific problem.

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 design problem asking for a stack that supports push, pop, top, peekMax, and popMax — the difficulty is popMax, which must remove the maximum element from anywhere in the stack while preserving relative order of the rest. Efficient solutions typically pair a doubly linked list (for O(1) removal from the middle) with an ordered map or balanced structure keyed by value to locate the max quickly. It's a strong test of composing multiple data structures to hit better-than-O(n) time on every operation, not just the easy ones.

This design problem requires inc(key), dec(key), getMaxKey(), and getMinKey() to all run in O(1) — ruling out a plain hashmap plus heap, since heaps don't give O(1) max/min removal alongside arbitrary key updates. The standard solution buckets keys by their current count in a doubly linked list of count-buckets, combined with a hashmap from key to its bucket, so incrementing or decrementing a key just moves it to an adjacent bucket. It's a genuinely hard composition of a hash map with a linked structure, and a strong signal for whether a candidate can design toward a strict complexity bound rather than a merely-workable one.

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 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.

Binary trees only have parent-to-child pointers, but this problem needs distance-k neighbors in every direction, so the standard trick is to first do a pass adding parent pointers (or building an adjacency map), converting the tree into an undirected graph. From there it's a straightforward BFS from the target node up to depth k. It tests whether a candidate can recognize that a tree-shaped input sometimes needs to be reframed as a general graph before the right algorithm applies.

A stack-based string-processing problem: decode a nested, run-length-encoded string like "3[a2[c]]" into its expanded form, where the nesting can go arbitrarily deep. The standard approach pushes the current string and repeat count onto a stack whenever a '[' is seen and pops/multiplies/concatenates on ']'. It's a clean test of stack-based parsing and correctly handling nested state, which is exactly why it's used across companies as a string-processing check.

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.

A stack-simulation problem: asteroids move left or right, and colliding pairs are resolved by comparing sizes and directions according to a small set of rules. The stack holds asteroids that haven't yet been destroyed, and each new asteroid may trigger a cascade of comparisons against the stack top before it's pushed or discarded. It's a good test of careful, exhaustive case enumeration (which asteroid survives, ties, same-direction pairs) rather than algorithmic complexity.

This design problem asks for a counter that records hits with timestamps and can report the number of hits in the past 300 seconds. It's typically implemented with a queue (or a fixed-size circular buffer of timestamp/count pairs) that evicts entries falling outside the trailing time window as new hits arrive. It tests whether a candidate can design a data structure for a sliding time window under both single-hit and (in a common follow-up) batched-hit conditions.

A design problem requiring a hash map from key to a list of (timestamp, value) pairs, plus binary search to efficiently find the value at or before a queried timestamp. It tests whether a candidate can combine a hash map with binary search rather than resorting to a linear scan, since values are appended with strictly increasing timestamps. It's a natural fit for companies dealing with versioned or time-stamped storage — Anthropic and OpenAI probe it in the context of retrieving the right version of a model checkpoint by timestamp, a real pattern in ML infrastructure.

A design problem: build an array that supports taking cheap snapshots and later querying the value of any index at any past snapshot, without paying the cost of copying the whole array on every snap(). The efficient solution stores, per index, a sparse list of (snap_id, value) pairs and binary-searches that list on get() rather than materializing full array copies — the model-state-checkpointing framing (as noted in this problem's source context) maps directly onto this pattern, since checkpointing large state cheaply and querying it later by version is the same underlying need. It tests whether a candidate reaches for a lazy, per-index versioning scheme instead of a naive full-copy snapshot.

A fixed-size sliding window problem: find all starting indices where a substring of the given string is an anagram of a pattern. The efficient approach maintains a running character-frequency count for the current window and compares it against the pattern's frequency count as the window slides one character at a time, avoiding recomputation from scratch. It's a common early-stage filter for whether a candidate can maintain incremental window state (add one char, remove one char) instead of re-scanning each window.

A shortest-path problem with an added constraint on the number of edges (stops) used: the standard approaches are a bounded Bellman-Ford (relax all edges K+1 times) or a modified Dijkstra/BFS that tracks both cost and stop count as part of the search state. It tests whether a candidate understands why plain Dijkstra can fail here (it doesn't account for the stop limit) and can adapt a shortest-path algorithm to a secondary constraint — a pattern that generalizes to real routing and logistics problems.

Given a starting IP address and a count of addresses to cover, the task is to output the minimum number of CIDR blocks that exactly cover that range. The approach converts the IP to a 32-bit integer, then repeatedly takes the largest power-of-two-aligned block starting at the current address that doesn't overshoot the remaining count, subtracting it and continuing. It's a bit-manipulation problem dressed in networking terminology, testing comfort with binary representations and address alignment rather than networking domain knowledge itself.

A grid flood-fill problem: for each unvisited land cell, run DFS or BFS to measure the connected island's size and track the maximum across all islands. It's a direct, well-known application of grid traversal with visited-tracking, generally used as an accessible warm-up to confirm a candidate can implement flood fill cleanly (including edge and boundary handling) before moving to a harder graph or DP follow-up.

An extension of the classic House Robber DP where houses are arranged in a circle, so the first and last house can't both be robbed. The standard solution runs the original linear DP twice — once excluding the first house, once excluding the last — and takes the max of the two results. It's a good test of recognizing how a small structural change (circular vs. linear) can be handled by decomposing into two instances of a known subproblem rather than inventing new DP state.

This is a design problem: implement a Tic-Tac-Toe board that reports a winner in O(1) per move instead of rescanning the whole board after every play. The standard trick is maintaining running counters per row, per column, and for each diagonal, incrementing or decrementing them per player's move so a win can be detected by checking whether any counter hits the board size. It's a solid signal for whether a candidate can convert an O(n) check into an O(1) amortized one by choosing the right incremental state.

Given a list of words, return the k most frequent ones, with ties broken by lexicographic order. It combines a frequency hash map with either a heap using a custom comparator for the tie-breaking rule, or a bucket-sort-by-frequency approach for an O(n) alternative. The tie-breaking requirement is the real trap — many otherwise-correct solutions get the right frequencies but the wrong order among equally-frequent words, making this a good test of attention to problem-statement detail, not just knowledge of heaps.

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.

A design problem: implement an iterator over a BST's in-order traversal with next() and hasNext(), where next() should run in average O(1) time and the iterator should use O(h) extra memory rather than flattening the whole tree upfront. The standard solution uses an explicit stack that's incrementally pushed further down the left spine as needed, simulating in-order traversal lazily. It tests whether a candidate can convert a typically-recursive traversal into an iterative, resumable one under a real memory constraint.

A concurrency fundamentals problem: three methods running on different threads must always execute in a fixed order (first, then second, then third), even though thread scheduling is otherwise unpredictable. It's typically solved with simple synchronization primitives like semaphores, locks, or condition variables to make one thread wait until a prior one signals completion. As an Easy-difficulty concurrency problem, it's commonly used as a first check of whether a candidate understands basic thread synchronization at all before moving to harder multithreading problems.

A concurrency problem where two threads must alternate printing "foo" and "bar" a fixed number of times, strictly interleaved. It's typically solved with two semaphores (or equivalent locks/condition variables) that each thread signals and waits on so it never gets two turns in a row. It's a step up from the most basic synchronization problems, testing whether a candidate can coordinate a repeating back-and-forth handoff between exactly two threads without deadlocking.

A concurrency problem modeling water molecule formation: hydrogen and oxygen threads arrive in arbitrary order and must be grouped so that output only ever occurs in valid H2O ratios (two hydrogen for every one oxygen), with threads from different groups never interleaving mid-molecule. Solutions typically use semaphores or barriers to gate how many hydrogen/oxygen threads can proceed at once and to synchronize a group's release. It's a stronger concurrency test than simple alternation problems since it requires enforcing a ratio constraint across an arbitrary number of threads, not just fixed pairwise ordering.

The canonical deadlock/resource-contention concurrency problem: five philosophers alternately think and eat, but each needs both adjacent forks (shared resources) to eat, and a naive "pick up left fork, then right fork" strategy can deadlock if every philosopher grabs their left fork simultaneously. Common fixes include imposing a strict resource-acquisition order, using a resource hierarchy, or limiting how many philosophers may attempt to eat concurrently. It's a well-known and heavily cited test of whether a candidate understands deadlock conditions and standard avoidance strategies, not just basic mutual exclusion.

A concurrency problem combining the familiar FizzBuzz logic with thread coordination: four separate threads are each responsible for printing numbers, "fizz", "buzz", or "fizzbuzz" respectively, and must take turns in strict numeric order without any thread printing out of turn. It's typically solved with multiple semaphores signaling which thread's condition (divisible by 3, by 5, by both, or neither) is currently active. It tests whether a candidate can extend two-thread alternation patterns to a four-way coordination scheme driven by a shared condition.