How to approach a coding problem, word by word

Short answer. Read the problem twice before writing code. The first pass finds what is being asked. The second finds the constraints: subarray or subsequence, at most or exactly, negatives allowed or not, and the size of n. Those few words decide the algorithm. Write them down in six short lines, then start coding.

Here is one statement, taken apart.

The statement

Given an array of integers and a number k, return the length of the longest subarray whose sum is at most k. The array can contain negative numbers. 1 ≤ n ≤ 200000.

Twenty-eight words. Six of them decide the algorithm.

"subarray"

A subarray is contiguous. A subsequence is not.

One word, and half the solution space is gone. Contiguous points at a window or a prefix sum. Non-contiguous points at sorting or dynamic programming.

People misread this constantly. It is the single most expensive word on the page.

"longest"

You return a length. So you never need to store the subarray itself.

You also need a maximum. One running best value. One comparison.

A running best value and one comparison are the whole bookkeeping.

"sum is at most k"

At most, not exactly.

Exactly k would push you towards a hash map of prefix sums.

At most k is a range. Ordering helps. A hash map does not.

Exactly k is where prefix sums in a hash map earn their keep.

Two words apart in English. Two different data structures.

"can contain negative numbers"

Negative numbers in the input are the trap.

With non-negative numbers only, growing a window grows the sum. That is what makes two pointers legal.

Negatives break it. The sum stops moving in one direction.

Shrinking a window can raise the sum.

Two pointers are now wrong. Prefix sums with a sorted structure are right.

One clause moved the answer from 5 lines to 20.

The clause was in the statement the whole time.

"1 ≤ n ≤ 200000"

200 thousand rules out anything quadratic. That is 40 billion operations.

The reference for what each bound allows is time complexity.

n log n fits comfortably within the bound. Sorting is affordable. So is a binary search inside a loop.

The bound is the interviewer telling you which complexity they expect. Read it as an instruction. What each bound allows is in time complexity from the constraints.

Six lines before you code

• What comes in, and what goes out.
• The size of the input.
• Contiguous or not.
• Sorted or not.
• The edges: empty, one element, all negative.
• The pattern you think it is. And the word that made you think so.

The last line carries the weight. The words that point at each pattern are listed in the algorithm patterns cheat sheet.

Guessing happens when you cannot name the word. A lucky guess teaches nothing.

Two minutes, not thirty seconds

In a 45-minute interview, two minutes of reading feels expensive. If the clock empties your head, use the five-minute rescue script.

The reading time is the cheapest two minutes you have.

A misread problem costs the whole session. You find out at minute 30. The wrong code is already on the board.

Reading fast is not a skill anyone is testing.

The rest of the routine around this is in how to prepare properly.

Where this is drilled

On AlgoPath every step opens with signals. Those are the words in a problem that point at the pattern.

Naming the pattern comes before any code.

The recognition drill hands you an unlabelled problem. You name the pattern and justify it first.

The first 33 steps are free.