DSA & Patterns

Look for an Anduril tag on the usual practice sites and you won't find one. Don't read that as a sign the round is exotic. The problems are standard mediums, the kind any serious preparation already covers. They arrive dressed in the domain: towers along a border, readings off a field sensor, a route across a grid of obstacles. The prompt is written to be vague as well. So your first move is asking what the inputs really are. The pattern comes after.

The round runs in layers. You clarify and get something working. Then the interviewer starts adding: the arrays are uneven, an input is empty or malformed, an obstacle drops onto the path you just found. You don't have to finish every layer to advance. You aren't scored mainly on complexity, though a quadratic answer where a linear one was in reach still counts against you. This lesson names the three patterns that carry most of the bank and drills each one on a problem built to the domain.

How the coding bar is set

The phone screen is a shared editor, commonly two medium problems inside about an hour. The onsite adds two more coding sessions in the same collaborative style. Difficulty tops out at medium: the recurring named problems all sit at that level. Candidates who prepare with a standard medium set and the classic seventy-five arrive ready. What sets it apart from a generic screen is the delivery: each problem arrives one clarifying question and one added constraint at a time.

Expect the prompt to escalate on purpose. A sensor problem starts with clean, sorted positions. Next they're unsorted. Then some are duplicated, and then the tower list is empty and you have to decide what a sensible return even is. A pathfinding problem starts as a straight distance between two points, walls appear, and finally whole regions become unreachable. The interviewer is watching whether your first solution was written to bend. Code that hard-coded an assumption from the opening phrasing tends to snap when the second phase lands. Then you're rebuilding it against the clock, and that's the failure this format is built to catch.

The Anduril angle

Prepare for the defense skin and the clarify-first cadence, and skip hunting for a top-fifty list. There's no proprietary trick and no company-specific problem bank. Generic drilling just never builds two habits this round leans on. One is translating the story into the pattern in the opening minute. A minimum-range-to-cover question is binary search on the answer even when it talks about towers, and a distance-to-nearest question is breadth-first search even when it talks about sensors. The other is writing for phases you haven't been told about yet. Validate inputs, say your assumptions aloud, and leave room for the constraint the interviewer is about to add. Robustness is graded. Invalid and degenerate inputs are part of the problem.

The patterns that recur

Group the recurring problems by the machinery they need and three families cover most of them. Each has a signal in the wording and a default structure that goes with it. Once you've read the signal off the domain story and committed to the structure, the minutes you saved go to the boundaries the interviewer is about to probe.

Binary search on the answer

Some prompts ask for the smallest value that makes something feasible: the minimum range that covers every crossing, the minimum capacity that ships in time. There, the answer itself is what you binary search. Feasibility is monotone. If a sensor range of ten covers the whole border, so does eleven, and if eight fails, so does seven. So the feasible values form a sorted boundary, which is exactly what binary search finds. You write a predicate that asks "can we cover everything within this range?" Then you binary search for the smallest range where it flips from false to true. The recurring border-sensor problem is this pattern in defense clothing.

The monotonic stack

Sometimes each element waits for the next one that beats it: a warmer reading, a taller neighbor, a higher price. A plain double loop is quadratic there, and a stack is linear. Keep a stack of indices whose answer is still pending, ordered so their values only decrease from bottom to top. Each new element pops every pending index it exceeds, resolving them. An index is pushed once and popped once, so the whole scan is linear despite the inner loop. The signal is the phrase "next greater," or "how far until something larger." The defense skin is a stream of sensor readings asking how long until a stronger one.

Grid breadth-first search

When the input is a grid and the question is a distance to the nearest source, use breadth-first search. It expands one ring at a time, so the first time it reaches a cell, the step count it carries is the shortest. Internalize the multi-source version. Seed the queue with every source at once, every tower or every gate, and a single sweep fills each open cell with its distance to the closest one. Walls are cells the search refuses to enter. Any cell the sweep never reaches is unreachable, and that is often what the added phase is fishing for. Depth-first recursion is the wrong reach here, because it finds a path with no promise that it's shortest.

Practice

Three problems, one per family, each modeled on the defense-skinned versions that show up on the real screen. The input is the function's arguments and the expected value is its return. Write the solution and run it against the cases. Then read the walkthrough. It carries the added-constraint follow-up the interviewer reaches for once the base case works.

1

Minimum Sensor Range Along a Border

MediumSometimes asked

Problem

A stretch of border is a straight line. You are given crossings, the positions along that line that must be watched, and towers, the positions where detection towers are already placed. Every tower has the same sensor range r, and a tower covers a crossing when the distance between them is at most r.

Return the minimum range r such that every crossing is covered by at least one tower. Positions are integers and the answer is an integer. The lists are not necessarily sorted.

If a crossing sits exactly on a tower, its distance is 0. You may assume there is at least one tower and at least one crossing.

Input. Two arguments, the crossings list and the towers list. Return an integer.

Input: crossings = [1,5], towers = [2]

Output: 3

The single tower at position 2 sits distance 1 from the crossing at 1 and distance 3 from the crossing at 5. To cover both, the range must reach the farther one, so the minimum range is 3.

How this uses the pattern

Feasibility is monotone in the range: if range r covers every crossing, so does any larger range. Write a predicate that asks whether a given range covers all crossings. Then binary search for the smallest range where it becomes true. The predicate checks each crossing against its nearest tower, found by binary search over the sorted towers.

Minimum Sensor Range Along a Border

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[1,2,3],[2]]Expected: 1

Input: [[1,2,3,4],[1,4]]Expected: 1

Input: [[1,5],[2]]Expected: 3

Input: [[10],[0]]Expected: 10

Input: [[5,5],[5]]Expected: 0

Input: [[1,2,3,4,5,6,7,8,9,10],[3,7]]Expected: 3

Input: [[1],[1,2,3]]Expected: 0

Input: [[-5,0,5],[0]]Expected: 5

Input: [[1,2,3,4,5],[1,5]]Expected: 2

Need a hint? (3 available)

The Anduril angle

The words "minimum range that covers everything" signal binary search on the answer. Each crossing needs a tower within the range. So the border is covered at range r exactly when the largest distance-to-nearest-tower is at most r. That makes feasibility monotone, and binary search runs on a monotone predicate. The defense skin hides a clean minimize-the-maximum problem. The smallest range you can get away with is the worst crossing's distance to its closest tower, and the binary search proves no smaller range survives.

Take it further

A realistic escalation demands redundant coverage, then hands you degenerate inputs. First the interviewer may ask that every crossing be watched by at least two towers within range, so one tower failing isn't fatal. That turns nearest-distance into second-nearest-distance inside the same predicate. Then they push on robustness. What does the function return when the tower list is empty, or when a crossing sits far outside the towers on both ends? The walkthrough shows the one-line change from nearest to second-nearest. It also shows why validating inputs up front is part of the answer here.

Show solution & walkthrough

2

Days Until a Warmer Reading

MediumSometimes asked

Problem

A field sensor logs one temperature reading per day, given as the list temperatures. For each day, find how many days you must wait until a strictly warmer reading appears.

Return a list answer of the same length, where answer[i] is the number of days after day i until a warmer reading, or 0 if no later day is warmer.

Input. One argument, the temperatures list. Return a list of integers.

Input: temperatures = [73,74,75,71,69,72,76,73]

Output: [1,1,4,2,1,1,0,0]

Day 0 at 73 is beaten the next day by 74, so 1. Day 2 at 75 isn't beaten until day 6 at 76, four days later, so 4. Days 6 and 7 never see a warmer reading, so both are 0.

How this uses the pattern

Keep a stack of day indices whose warmer day is still pending, with their readings decreasing from bottom to top. When a new reading exceeds the reading at the top of the stack, that top day has found its warmer day: pop it and record the gap. Each index is pushed once and popped once, so the scan is linear.

Days Until a Warmer Reading

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[73,74,75,71,69,72,76,73]]Expected: [1,1,4,2,1,1,0,0]

Input: [[30,40,50,60]]Expected: [1,1,1,0]

Input: [[30,60,90]]Expected: [1,1,0]

Input: [[90,80,70]]Expected: [0,0,0]

Input: [[50]]Expected: [0]

Input: [[50,50,50]]Expected: [0,0,0]

Input: [[55,50,60,45,70]]Expected: [2,1,2,1,0]

Input: [[71,71,72,70,72]]Expected: [2,1,0,1,0]

Need a hint? (3 available)

The Anduril angle

The phrase "how many days until a warmer reading" signals a monotonic stack. Comparing every day against every later day is quadratic and folds on a long log. A stack that holds only the days still waiting for a warmer reading resolves each one exactly when the warmer day arrives. The skin is a sensor stream, but the mechanics are the canonical next-greater scan. The stack stays decreasing, and each new reading clears out every pending day it beats.

Take it further

A realistic escalation makes the log circular. The interviewer says the readings wrap around, so a late reading's warmer day may be an early one, and asks for the same waits on a cyclic sequence. The fix is to walk the indices twice, taking each index modulo the length. A pending day at the end can then be resolved by a day near the start, without ever building a doubled array. The walkthrough shows why one extra pass is enough and how the stack logic stays identical.

Show solution & walkthrough

3

Distance to the Nearest Tower

MediumSometimes asked

Problem

A patrol area is a grid. Each cell is one of three values: 0 marks a detection tower, -1 marks an obstacle the signal cannot pass, and 2147483647 marks an open cell whose distance to the nearest tower is unknown.

Fill every open cell with the number of steps to the nearest tower, moving only up, down, left, or right, and never through an obstacle. An open cell that no tower can reach keeps its value of 2147483647. Return the filled grid.

Input. One argument, the grid of integers. Return the grid with open cells filled in.

Input: grid = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]

Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

A breadth-first sweep starts from both towers at once, and each open cell takes the fewest steps to whichever tower is closer. The open cell at the top left is three steps from the nearest tower, and every obstacle stays -1.

How this uses the pattern

This is multi-source breadth-first search. Seed a queue with every tower cell at distance 0, then sweep outward. Each time you reach an open cell for the first time, its distance is one more than the cell you came from. Every source starts together, so the first arrival at any cell is its distance to the nearest tower.

Distance to the Nearest Tower

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Test Cases

Input: [[[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]]Expected: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Input: [[[2147483647,0],[2147483647,2147483647]]]Expected: [[1,0],[2,1]]

Input: [[[0]]]Expected: [[0]]

Input: [[[0,-1,2147483647]]]Expected: [[0,-1,2147483647]]

Input: [[[2147483647,2147483647],[2147483647,2147483647]]]Expected: [[2147483647,2147483647],[2147483647,2147483647]]

Input: [[[2147483647,-1,2147483647],[0,-1,2147483647]]]Expected: [[1,-1,2147483647],[0,-1,2147483647]]

Input: [[[0,2147483647,2147483647,2147483647]]]Expected: [[0,1,2,3]]

Input: [[[2147483647,2147483647],[0,2147483647]]]Expected: [[1,2],[0,1]]

Need a hint? (3 available)

The Anduril angle

A distance-to-nearest-source question on a grid is breadth-first search, and the many-towers version is the multi-source variant. Skip running a separate search from each tower and taking the minimum. Seed the queue with all towers at once. The rings from every tower then interleave, and the first time a cell is reached, the step count is already its distance to the closest tower. The sweep simply refuses to enter obstacle cells. Cells it never reaches are the coverage gaps, which is what the follow-up phase tends to ask about.

Take it further

A realistic escalation adds terrain that slows the signal. The interviewer adds cells that still pass a signal but cost two steps instead of one. The grid is no longer uniform, and a plain queue can finalize a cell before a cheaper route reaches it. With only two edge costs, the fix is a double-ended queue. Push a same-cost neighbor to the front and a costlier one to the back, which keeps the frontier in cost order without a full heap. The walkthrough shows why uniform breadth-first search breaks once steps carry different costs, and how the deque restores the first-arrival guarantee.

Show solution & walkthrough