Question 1

How do you turn an O(n²) nested-loop solution into O(n) with a hash structure? Explain with an example.

Accepted Answer

This is the single most useful answer in an algorithm interview, so keep it ready as a template. First state the general principle: "A nested loop is really asking 'is there another element matching this one?'. I answer that question in O(1) by keeping what I have already seen in a Map/Set, instead of rescanning the array each time." Then show two-sum: "For nums[i] the required partner is exactly known — target - nums[i]. I go through in one pass; at each step I first look up target - nums[i] in the map, and if it is absent I store the current value with its index. Looking up BEFORE storing matters, otherwise an element can pair with itself." Always state complexity on both axes: O(n) time, O(n) extra memory — and stress that this is a deliberate trade-off. A closing note of honesty lands well: "If n is genuinely small, the O(n²) solution may be the better choice for its simplicity — I make that call by looking at the input size."

Question 2

How would you find whether an array contains a duplicate? Compare a few approaches.

Accepted Answer

This question tests your ability to choose, so compare three approaches rather than giving one: Nested loops: O(n²) time, O(1) memory. Simple and needs no extra memory — the only option if memory is genuinely tight. Sort then compare neighbours: O(n log n) time, O(1) extra memory if sorted in place. But it mutates the original array, which is often unacceptable. Seen-set: O(n) time, O(n) memory. One pass, and it stops at the first duplicate, so in practice it often does not even reach n. Then justify the choice: "My default is the Set, because time is usually more expensive than memory. But in a memory-constrained environment — embedded, or very large data — I would take the sorting approach." Adding an idiomatic detail makes a good impression: in Kotlin, seen.add(n) returning false already means the element was present — no separate contains call needed; Dart behaves the same. That folds the check into a single operation.

Question 3

How would you solve "count the subarrays that sum to k"?

Accepted Answer

Name the naive solution first so the interviewer can see your line of thought: "Checking every end for every start is O(n²)." Then show the transformation mathematically — this is the core of the answer: "sum(i..j) = prefix[j] - prefix[i-1]. I want that to equal k, so prefix[i-1] = prefix[j] - k. Standing at j, I ask: how many times have I seen the value prefix - k so far? That is a hash map lookup." Give the algorithm briefly: one pass, accumulate prefix, add counts.get(prefix - k) to the answer, then increment counts[prefix]. Time O(n), memory O(n). Always mention the seed — this is the detail interviewers wait for: counts = {0: 1} is what counts subarrays starting at the very beginning. Omitting it gives wrong answers on tests like [1,1,1], k=2. Finish by noting negative and zero values: a sliding window does not work here because the sum is not monotonic, whereas the prefix + map approach handles negatives correctly. That remark lifts the answer above middle level.

Question 4

When is a hash-based solution the WRONG choice?

Accepted Answer

This question checks whether you apply the tool blindly, so list concrete cases: When sorted output is required: a hash preserves no order. For "the 10 smallest elements" or "all keys greater than k", a balanced tree (TreeMap/SplayTreeMap), a sorted array or a heap is the right choice. Range queries: finding keys in [a, b] with a hash means scanning everything — O(n). A sorted structure does it in O(log n + k). When memory is critical: O(n) extra memory is not always available. In embedded environments or on very large data, sorting plus two pointers fits better. Prefix search: "all words starting with 'ka'" gets no help from a hash — that is a trie's job. Very small n: for 10–20 elements the overhead of building a hash structure can exceed a plain linear scan. When worst-case guarantees are required: hashing is O(1) on average; in real-time or security-critical systems an O(n) worst case may be unacceptable, and a balanced tree's O(log n) guarantee wins. A closing line lands well: "I treat hashing as my default, but the moment I hear order, range or prefix in the requirement I immediately look toward a tree or a trie."

Question 5

How do you state the complexity of a hash-based solution correctly in an interview?

Accepted Answer

Three clarifications separate you from the average candidate here. First — separate average from worst case. Saying "O(1)" is incomplete. The correct form: "A hash lookup is O(1) on average; in the worst case, if all keys land in one bucket, it can be O(n). In practice modern runtimes guard this with hash randomization and tree-ification." Second — state memory too. Giving time complexity and staying silent on space is the most commonly missed step. Always express it as a pair: "O(n) time, O(n) extra memory." Third — do not forget the cost of hashing the key itself. If the key is a string, the hash depends on its length: hashing n words is really O(n·L) where L is the average length. In anagram bucketing, sorting the letters adds O(k log k) — O(n·k log k) overall. Raising that detail yourself shows the interviewer immediately that you compute complexity rather than recite it. Also name amortization correctly: when the map grows, the rehash costs O(n), but since it happens once every n operations the amortized cost per operation stays O(1).

Pattern	Structure	How you recognise it	Complexity
Frequency counter	Map: value → count	"how many times", "most frequent", "is it an anagram"	O(n) time / O(k) memory
Complement lookup	Map: value → index	"two numbers summing to target"	O(n) / O(n)
Bucketing / grouping	Map: normalised key → list	"group by", "collect the ones sharing ..."	O(n·k) / O(n)
Seen-set	Set: elements already seen	"any duplicate", "is there a cycle", "unique"	O(n) / O(n)
Prefix sum + map	Map: prefix sum → count/index	"number of subarrays summing to k"	O(n) / O(n)

Hashing interview patterns