Recognizing the approach from an array and a target
“Given an array and a target, how would you determine which algorithmic approach to use?”
What this tests
- Whether the candidate interrogates the input before reaching for an algorithm.
- Whether they can map concrete properties (sorted, bounded, positive-only) to concrete techniques.
- Whether they use constraints (
n) to decide which complexity is acceptable. - Whether they think in terms of a decision procedure rather than recalling one memorized problem.
Strong answer
A strong candidate does not answer with an algorithm. They answer with questions, and each question maps to a technique. Is the array sorted? Sorted plus a target means Binary Search for one element (O(log n)) or Two Pointers (Opposite Ends) for a pair (O(n)). Do I need a pair, a subarray, or a subsequence? A pair with arbitrary order is a Hash Map problem (O(n) time, O(n) space). A contiguous subarray with a sum target is Prefix Sum plus a hash map of seen prefixes. A subsequence usually means Dynamic Programming or backtracking.
Are the values constrained? All positive means a sliding window can grow and shrink monotonically (Sliding Window (Variable Size)); negatives break that monotonicity and force prefix sums. Small integer ranges (say 0..10^5) allow counting arrays instead of hash maps. What size is `n`? n ≤ 20 invites 2^n enumeration; n ≤ 5000 tolerates O(n^2); n ≤ 10^5 demands O(n log n) or better.
They then say the brute force out loud — usually O(n^2) over pairs or O(n^2) over subarrays — and identify what the inner loop is *looking for*. That inner lookup is the thing a hash map, a sorted order, or a running window replaces. This is the general engine: name the repeated question the brute force asks, then pick the structure that answers it in O(1) or O(log n).
Green flags · Red flags
- Asks whether the array is sorted before saying anything else.
- Distinguishes pair, subarray (contiguous) and subsequence explicitly.
- Mentions that negative numbers break the sliding-window invariant and switch the problem to prefix sums.
- Uses
nto derive the target complexity ("with10^5I need roughlyn log n"). - States the brute force first and identifies the repeated lookup it performs.
- Mentions the space tradeoff: two pointers on sorted input is
O(1)space; hash map isO(n).
- Immediately says "hash map" for every array-and-target problem.
- Proposes sorting without noting that sorting destroys original indices.
- Cannot say what the brute force is or why it is slow.
- Confuses subarray with subsequence.
- Never asks about duplicates, negatives, or empty input.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
n is 20 and I need a subset summing to the target?