A repeatable interview method
Restate the problem. Clarify duplicates, ordering, input size and no-solution behavior. Describe a simple correct approach before optimizing. State an invariant, implement it, trace a normal case and a boundary case, then explain time and space. Do not begin by guessing a memorized pattern.
These are original worked examples. The DSA catalog contains more exercises with individual hints and approaches. Use our visual DSA lessons to see the structures in action. You should still submit and test solutions on the linked practice platform.
Two Sum — avoid searching every pair
Return two distinct indices whose values sum to the target. Return no pair if none exists. Assume any valid pair is acceptable; inputs need not be sorted.
A nested loop tries O(n²) pairs with O(1) extra memory. To reduce repeated work, store each previously seen value's index. For the current value, look up the complement. Search before inserting so an element cannot pair with itself.
For [2, 7, 11] and target 9, process 2: need 7, not seen; store 2. Process 7: need 2, found at index 0; return [0, 1]. For [3, 3] and target 6, the second 3 finds the first 3. A set alone is insufficient when the result requires indices.
Python
def two_sum(values, target):
seen = {}
for index, value in enumerate(values):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []
assert two_sum([2, 7, 11], 9) == [0, 1]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([3], 6) == []
assert two_sum([-2, 4], 2) == [0, 1]
Java
The widened subtraction avoids integer overflow while calculating the complement. Save as TwoSumDemo.java, compile and run with a JDK.
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TwoSumDemo {
static int[] twoSum(int[] values, int target) {
Map<Long, Integer> seen = new HashMap<>();
for (int index = 0; index < values.length; index++) {
long complement = (long) target - values[index];
Integer previous = seen.get(complement);
if (previous != null) return new int[]{previous, index};
seen.put((long) values[index], index);
}
return new int[0];
}
public static void main(String[] args) {
if (!Arrays.equals(twoSum(new int[]{3, 3}, 6), new int[]{0, 1})) {
throw new AssertionError("Repeated values must work");
}
if (twoSum(new int[]{3}, 6).length != 0) {
throw new AssertionError("Cannot reuse one element");
}
}
}
C++
Save as two_sum.cpp; compile with C++17. This function accepts int values and target, so long long safely represents the difference of two input integers on typical 32-bit-int implementations.
#include <cassert>
#include <unordered_map>
#include <vector>
std::vector<int> two_sum(const std::vector<int>& values, int target) {
std::unordered_map<long long, int> seen;
for (int index = 0; index < static_cast<int>(values.size()); ++index) {
long long complement = static_cast<long long>(target) - values[index];
auto found = seen.find(complement);
if (found != seen.end()) return {found->second, index};
seen[values[index]] = index;
}
return {};
}
int main() {
assert((two_sum({3, 3}, 6) == std::vector<int>{0, 1}));
assert(two_sum({3}, 6).empty());
assert((two_sum({-2, 4}, 2) == std::vector<int>{0, 1}));
}
Expected time is O(n); additional memory is O(n). Hash-table operations have worst cases, so do not claim an unconditional linear worst-case bound. Sorting and two pointers is an alternative, but original indices must be preserved and sorting costs O(n log n).
Binary search — make the interval precise
Find the first position whose value is at least target in a sorted list. Use a half-open interval from left inclusive to right exclusive. Positions before left are smaller than target; the answer remains between left and right, including right as the insertion position.
def lower_bound(values, target):
left, right = 0, len(values)
while left < right:
middle = left + (right - left) // 2
if values[middle] < target:
left = middle + 1
else:
right = middle
return left
assert lower_bound([1, 3, 3, 8], 3) == 1
assert lower_bound([1, 3, 3, 8], 9) == 4
assert lower_bound([], 3) == 0
Each step excludes a portion that cannot contain the answer. Time is O(log n), extra space O(1). An insertion position is not automatically a match: check it is in bounds and its value equals the target. Practise binary search problems.
Sliding window — longest substring without repetition
A brute-force approach checks all substrings and duplicates. Maintain the left boundary of a valid window and the last index of each character. When a character repeats within the window, advance left past its previous occurrence. Never move left backward.
def longest_unique(text):
last = {}
left = 0
best = 0
for right, character in enumerate(text):
if character in last:
left = max(left, last[character] + 1)
last[character] = right
best = max(best, right - left + 1)
return best
assert longest_unique("abba") == 2
assert longest_unique("abcabcbb") == 3
assert longest_unique("") == 0
On abba, an old occurrence of a lies before the current window. The maximum prevents it from reopening an invalid range. Expected time O(n), memory O(k) for distinct characters. This is character-based, not user-perceived grapheme segmentation. Practise sliding window.
BFS — shortest distance in an unweighted graph
All edges have equal cost. Mark a vertex visited when enqueuing it, not when removing it, so several neighbors do not enqueue it repeatedly.
from collections import deque
def shortest_distances(graph, start):
distance = {start: 0}
queue = deque([start])
while queue:
vertex = queue.popleft()
for neighbor in graph.get(vertex, []):
if neighbor not in distance:
distance[neighbor] = distance[vertex] + 1
queue.append(neighbor)
return distance
assert shortest_distances({0: [1, 2], 1: [3], 2: [3], 3: []}, 0)[3] == 2
assert shortest_distances({0: []}, 0) == {0: 0}
BFS visits increasing edge-distance layers. With adjacency lists, traversal takes O(V + E) over the reachable graph and O(V) additional space. It does not solve arbitrary weighted shortest paths; choose a suitable weighted algorithm. Practise graphs.
Dynamic programming — maximum non-adjacent sum
Choose a subset of values without selecting adjacent positions. Selecting nothing is allowed. A brute-force recursion branches on take or skip and repeats states. At each position, the best result is the better of skipping it or taking it plus the best result two positions earlier.
def non_adjacent_sum(values):
two_back = 0
one_back = 0
for value in values:
current = max(one_back, two_back + value)
two_back, one_back = one_back, current
return one_back
assert non_adjacent_sum([2, 7, 9, 3, 1]) == 12
assert non_adjacent_sum([]) == 0
assert non_adjacent_sum([-5, -2]) == 0
Time O(n), space O(1). If the task requires choosing at least one value or reconstructing selected indices, the contract and stored state must change. Practise dynamic programming.
Transfer exercises
For each example, add an edge case, explain the invariant and solve a nearby variant without copying. Try Two Sum with all index pairs, binary search with last occurrence, a window with at most k distinct values, BFS path reconstruction and non-adjacent sum with reconstruction. Write down why your changes are correct.
References: Python deque, Java HashMap, Microsoft unordered_map. Algorithm explanations and exercises above are original.