Question 1

Explain the two pointers pattern and say when it applies.

Accepted Answer

What it does: turns two nested loops into a single pass, O(n²) → O(n). Two forms: (1) opposite ends — lo and hi move toward each other on a sorted array; (2) same direction — both move left to right at different speeds (read/write, or a sliding window). Why it works — the most important part, because it shows the justification rather than the mechanics: on a sorted array, if a[lo] + a[hi] is below the target, lowering hi is pointless — a[hi] is already the largest, so every remaining pair with lo would be smaller still. So each step eliminates a whole row of pairs; that is how the brute force's n² pairs compress into n steps. When it applies: the array is sorted (or cheap to sort) and the problem is about pairs/triples or a contiguous range. When it doesn't: the array isn't sorted and can't be (original indices are needed, say), or the subset need not be contiguous. State the trade-off too: "On an unsorted array, two pointers needs a sort first — O(n log n). A hash map gives O(n) but costs O(n) memory. If memory is the constraint, two pointers; if speed is, the hash map." That comparison completes the answer.

Question 2

Task: find the length of the longest substring without repeating characters. Think aloud.

Accepted Answer

Step 1 — clarifying questions: what characters can appear (ASCII only or Unicode)? Is case significant? Can the string be empty? Do you want the length or the substring itself? Step 2 — brute force and its complexity: check every substring — O(n²) substrings, O(n) to check each for repeats → O(n³), or O(n²) with a Set. Say this out loud: the interviewer needs to see you have a baseline. Step 3 — the optimisation and WHY: "A substring is contiguous, so a sliding window fits. I keep the window's characters in a Set. I advance right; if the character is already in the window, I move left right, removing characters until the repeat is gone. At each step I compare the window length against the maximum." Step 4 — complexity: "Even with the inner while, each character enters the window once and leaves once, so O(n). Memory is O(min(n, alphabet size))." Step 5 — dry-run: walk "abcabcbb" — the window reaches abc, then the second a pushes left forward. Answer: 3. Step 6 — edge cases: empty string → 0; all characters identical ("aaaa") → 1; all distinct → the string's length. Bonus optimisation (if time remains): keeping a Map<char, last index> instead of a Set lets you jump left straight to lastSeen + 1 rather than stepping it one at a time. Same complexity, but the inner loop disappears entirely. Offering that signals "I can improve my own solution".

Question 3

What is the difference between a fixed-size and a variable-size sliding window?

Accepted Answer

The difference in one sentence: a fixed window is given a size; a variable window is given a condition, and the size is the answer. Fixed window: questions like "maximum sum of K consecutive elements". The code is simple: sum the first k, then each step sum += a[right] - a[right - k]. Each slide is O(1), O(n) overall. The core idea is not recomputing from scratch. Variable window: "longest substring without repeats", "shortest subarray with sum at least S", "longest range with at most 2 distinct letters". The template: expand right → while the condition is violated shrink left → update the answer. An important subtlety — knowing it makes a difference: where you update the answer differs between maximising and minimising. For "longest" problems, update while the window is valid; for "shortest" problems, shrink as soon as the condition holds and update as you shrink. Confusing those two is the most common mistake. Common to both: O(n), because left and right only move forward. Practical tip: announce which variant you're in out loud — "no size is given, so it's a variable window and the condition is 'no repeats'" — that one sentence organises your own thinking and shows the interviewer you're on the right track.

Question 4

When do people wrongly apply a sliding window?

Accepted Answer

There are three typical cases, and knowing them keeps you off the wrong path in an interview. 1. When contiguity isn't required. A window is by definition a contiguous range. On "the maximum-sum subset of any elements" a window gives the wrong answer — that needs sorting, a hash map, DP or backtracking. So before coding, one question: "the subarray must be contiguous, correct?" 2. When negative numbers are present. This is the subtlest trap. "Shortest subarray with sum at least S" is a sliding-window problem only when all numbers are positive. The reason: expanding the window must only increase the sum and shrinking it must only decrease it — monotonicity. A negative number breaks that and the window returns a wrong answer. Then you need prefix sums plus a monotonic deque (or another approach). Raising this limitation yourself is a very strong signal. 3. Opposite-ends two pointers on an unsorted array. The lo++ / hi-- decision rests on the guarantee that sorting provides. On unsorted data those decisions are meaningless and the result is arbitrary. How to protect yourself: before writing code, check the pattern's precondition out loud — "is it contiguous? is it sorted? are the numbers positive?" That three-second check prevents ten minutes spent in entirely the wrong direction. Interviewers score it separately, because verifying an algorithm's preconditions matters just as much in real work.

Question 5

"Find two numbers summing to target" — what's your approach for the sorted and unsorted cases?

Accepted Answer

A classic question, and the point is that you can compare two solutions, not that you name one. Sorted array → two pointers: lo = 0, hi = n - 1. Sum too small → lo++, too large → hi--, equal → return. O(n) time, O(1) memory. Unsorted array → hash map: in one pass, for each element check whether target - a[i] is in the map; if not, add the current element. O(n) time, O(n) memory. An important detail: do the check BEFORE the insert — otherwise, when target = 2 a[i], you can use the same element twice. If it's unsorted, why not just sort? The sort is O(n log n), slower than the hash map. It also destroys the original indices — and if the problem wants indices (it usually does), recovering them after sorting is extra work. Mentioning that subtlety strengthens the answer. When sorting is still right: when memory is critical (O(1) required), or when many such queries will hit the same array — sort once, then answer each query in O(n), or even O(log n) with binary search. Be ready for the extension*: "three numbers summing to target" (3Sum) almost always follows. The answer: sort, then for each element run two pointers over the rest — O(n²). Don't forget to skip duplicates. Raising that follow-up yourself makes you look prepared.

Signal in the problem	Variant	Key detail
"A pair/triple summing to X in a sorted array"	Opposite-ends two pointers	Sum too small → `lo++`, too large → `hi--`; `O(n)` time, `O(1)` memory
"Is it a palindrome", "reverse the array"	Opposite-ends two pointers	Compare/swap until they meet in the middle
"Remove duplicates", "move zeros to the end" (in place)	Same direction (read/write)	`write` advances only on kept elements
"Maximum sum/average of K consecutive elements"	Fixed-size window	`sum += a[right] - a[right - k]`
"Longest substring without repeats"	Variable window	Track the window contents in a `Set`/`Map`; shrink on a repeat
"Shortest subarray with sum at least S"	Variable window	Shrink as soon as the condition holds and update the minimum length
The subset is not contiguous (any elements)	Sliding window does NOT apply	Think hash map, sorting, DP or backtracking

Two pointers and sliding window