Algorithmic Problem-Solving and Data Structure Selection Questions
The higher-order meta-skill of attacking an unfamiliar problem: recognizing problem archetypes and mapping them to known techniques, decomposing under constraints, and choosing, composing, or designing the right data structures to meet specified operation costs (LRU cache, min-stack, ordered maps, disjoint-set/union-find). Covers reasoning about trade-offs between competing structures and approaches, working through medium-to-hard problems methodically, handling problem variations, and communicating an approach before coding. The connective-tissue topic that ties the individual structure and algorithm topics together, rather than any single structure or algorithm.
Find the length of the longest substring of a given string that contains no repeated characters. Solve it in O(n) time using a window that expands and contracts over the string, and explain what state you track to know when to shrink the window from the left.
Sample Answer
Direct answer
Slide a window over the string with two pointers, and keep a hash map from character to the index right after its most recent occurrence. When the character at the right pointer has been seen before at or after the current window's left edge, jump the left pointer forward to just past that previous occurrence, but never backward, and track the widest window seen along the way. Because the left pointer only ever advances and the right pointer sweeps the string once, the whole scan is O(n) time using O(min(n,alphabet size)) space for the map.
Approach
- Maintain
last_seen, mapping each character to one past the index of its most recent occurrence (storing index + 1 lets an unseen character default cleanly to 0). - Maintain
left, the window's start, andbest, the longest valid window length so far. - For each
right, if the current character was seen before, setleft = max(left, last_seen[char]); themaxis essential, not optional. - Update
bestwith the current window lengthright - left + 1, then recordlast_seen[char] = right + 1.
def length_of_longest_substring(s: str) -> int:
"""O(n) time, O(min(n, alphabet size)) space sliding window."""
last_seen: dict[str, int] = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last_seen:
left = max(left, last_seen[ch])
best = max(best, right - left + 1)
last_seen[ch] = right + 1
return best
if __name__ == "__main__":
print(length_of_longest_substring("abcabcbb")) # 3
print(length_of_longest_substring("bbbbb")) # 1
print(length_of_longest_substring("pwwkew")) # 3
print(length_of_longest_substring("")) # 0
Running this prints 3, 1, 3, 0, matching the well-known cases for this problem.
Key points
- Why
max, not a direct jump, is required: dropping themaxand always jumpingleft = last_seen[ch]breaks correctness whenever a repeated character's earlier occurrence already fell outside the current window, because that would moveleftbackward, re-including characters that had already been correctly excluded. Concretely, on"abba"a buggy version withoutmaxreports length 3, while the correct version reports 2 (the true answer, since"ab"and"ba"are the longest repeat-free substrings, both length 2). Verifying this directly:
def buggy_longest(s: str) -> int:
last_seen: dict[str, int] = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last_seen:
left = last_seen[ch] # missing max(): can move left backward
best = max(best, right - left + 1)
last_seen[ch] = right + 1
return best
def correct_longest(s: str) -> int:
last_seen: dict[str, int] = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last_seen:
left = max(left, last_seen[ch])
best = max(best, right - left + 1)
last_seen[ch] = right + 1
return best
if __name__ == "__main__":
print("abba ->", buggy_longest("abba"), "vs correct", correct_longest("abba"))
Running this prints abba -> 3 vs correct 2: the buggy version claims a length-3 window exists in "abba", but no 3-character substring of "abba" is actually repeat-free, so 3 is wrong.
- An alternative that uses a set instead of a map (shrinking
leftone character at a time until the repeat is gone, rather than jumping straight to the right position) is also correct and still O(n) overall, since each character enters and leaves the set at most once, but it does more per-step work whenever the repeat is far behind the current position.
Complexity
Time: O(n), since right advances once per character and left never moves backward, so together they make at most O(n) total steps. Space: O(min(n,alphabet size)) for the map.
Edge cases
- Empty string: returns 0.
- All identical characters (e.g.,
"bbbbb"): returns 1. - All unique characters: returns the full length of the string.
- A single character: returns 1.
You are given a stream of pairwise connections arriving over time (for example, dependency edges or account-merge events) and need to answer 'are these two items connected yet' after each one, without recomputing connectivity from scratch. Implement a structure that answers both the connect and the query operation efficiently, and explain why a fresh BFS/DFS after every update would not scale.
Sample Answer
Direct answer
Maintain a disjoint-set (union-find) structure over the items: each connect(u, v) event does two finds plus one union, and each are these connected query does two finds and compares the results, both in amortized time so close to constant that it is treated as O(α(n)) in practice (α is the inverse Ackermann function, which is at most 4 for any realistic input). A fresh breadth-first or depth-first search (BFS/DFS, traversals that explore a graph outward from a start node) after every new edge would instead cost O(V+E) per query, so answering q queries over a growing graph costs O(q⋅(V+E)) total, which scales far worse as both the edge stream and the query count grow.
Structured elaboration
Union-find keeps each connected group as a tree with a representative root, updated incrementally as edges arrive:
find(x): walk up parent pointers to the root, flattening the path as you go (path compression).connect(u, v): find both roots; if they differ, attach the smaller tree under the larger one's root (union by rank) and merge.connected(u, v): true exactly whenfind(u) == find(v).
This is fundamentally an incremental structure: each new edge only touches the two trees it connects, never the whole graph, so the cost of processing an edge does not grow as the graph grows. Re-running BFS/DFS from scratch after every edge, by contrast, always pays for a full traversal of everything reachable so far, regardless of how small the actual change was.
The same primitive answers three framings that look different on the surface: cycle detection while building an undirected graph (adding edge (u, v) closes a cycle exactly when find(u) == find(v) already, before the union), the running count of connected components (start at n and decrement by one on every union that actually merges two different roots), and an incrementally updated dependency or account-merge graph (the scenario here): all three are the same "maintain connectivity as edges stream in" problem.
Worked example
class DSU:
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x: int) -> int:
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def connected(self, a: int, b: int) -> bool:
return self.find(a) == self.find(b)
def union(self, a: int, b: int) -> bool:
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # (a, b) already connected: this edge closes a cycle
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
self.components -= 1
return True
dsu = DSU(6) # nodes 0..5
stream = [(0, 1), (2, 3), (0, 2), (4, 5), (1, 3)] # last edge closes a cycle
for u, v in stream:
created_new_link = dsu.union(u, v)
print(f"connect({u},{v}) -> new_edge={created_new_link}, "
f"connected_now={dsu.connected(u, v)}, "
f"components_remaining={dsu.components}")
print("query(0,3):", dsu.connected(0, 3))
print("query(0,4):", dsu.connected(0, 4))
print("total_components:", dsu.components)
Running this prints:
connect(0,1) -> new_edge=True, connected_now=True, components_remaining=5
connect(2,3) -> new_edge=True, connected_now=True, components_remaining=4
connect(0,2) -> new_edge=True, connected_now=True, components_remaining=3
connect(4,5) -> new_edge=True, connected_now=True, components_remaining=2
connect(1,3) -> new_edge=False, connected_now=True, components_remaining=2
query(0,3): True
query(0,4): False
total_components: 2
The (1, 3) edge returns new_edge=False because 1 and 3 were already in the same group (via 0-1 and 0-2-3), so that edge closes a cycle rather than merging anything, and the component count correctly stays at 2.
Key points
unionreturning false is exactly the cycle-detection signal: the edge connects two nodes already in the same group.componentsneeds no separate pass to compute: it is decremented once per union that actually merges two distinct groups.
Complexity
O(α(n)) amortized per connect or queryversus
one BFS/DFSO(V+E)×queriesq=O(q⋅(V+E))for the BFS/DFS-from-scratch alternative. Space is O(n) for the parent and rank arrays.
Edge cases
- A self-loop edge
(u, u):find(u) == find(u)trivially, sounioncorrectly reports no new edge without special-casing it. - Edges referencing a node outside the initial size: the structure needs to be sized (or dynamically grown) for the maximum node ID up front, since union-find here uses array indices, not a hash map.
- Duplicate edges arriving again later: handled the same way as a cycle-closing edge, no extra logic needed.
Trade-offs & pitfalls
Union-find only answers connectivity and component membership; unlike a BFS/DFS traversal, it cannot reconstruct the actual path between two connected nodes, so if the caller needs the path (not just "are they linked"), you still need a traversal on top. It also has no efficient support for removing an edge once merged (there is no "un-union"): if the stream needs to delete edges as well as add them, standard union-find is the wrong tool, and you would look at fully offline processing (process deletions in reverse as unions, if the full edge stream is known ahead of time) or dedicated dynamic-connectivity structures rather than trying to force a delete through this structure.
Given a sorted array and a target value, find two numbers that add up to the target using O(1) extra space. Explain why sorted order lets you avoid the hashmap you would otherwise need, and how you would adapt the same technique to intersect two sorted arrays.
Sample Answer
Direct answer
On a sorted array, start one pointer at the beginning and one at the end, and move them toward each other based on how the current pair's sum compares to the target: this finds the pair in one linear pass using O(1) extra space, no hash map required. Sorted order is exactly what makes the hash map unnecessary, since it tells you in which direction to move without needing to remember every value you have already seen. The same converging-pointer idea, applied to two arrays instead of one target sum, gives you their intersection: advance whichever array currently has the smaller value.
Structured elaboration
Two-sum on a sorted array: maintain the invariant that every valid pair still under consideration lies between left and right. If arr[left] + arr[right] == target, you are done. If the sum is too small, arr[left] cannot be part of any valid pair with anything to its left (everything to the left is even smaller, making the sum only smaller), so advance left. If the sum is too large, by the same logic on the other side, retreat right. Because the array is sorted, this monotonic narrowing never skips over a valid pair: if one exists, it is found.
Why sorted order removes the need for a hash map: an unsorted two-sum needs a hash map to remember "have I seen the complement of this value yet," since there is no way to know which direction to search without that memory. Sorted order replaces that memory with structure: the comparison arr[left] + arr[right] versus target alone tells you which pointer must move, with no need to have seen anything before.
Adapting to intersect two sorted arrays: instead of pointers converging toward each other, they move in the same direction, each independently, starting both at index 0. Compare the current elements of each array: if equal, that value is in the intersection, and advance both; if array a's current element is smaller, it cannot match anything later in b (which is only larger from here), so advance a; otherwise advance b. This is the same "sorted order tells you which pointer to move, so no hash map is needed" idea, just applied across two sequences instead of within one.
Worked example
Two-sum, sorted array:
def two_sum_sorted(arr: list[int], target: int) -> tuple[int, int]:
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
return left, right
if s < target:
left += 1
else:
right -= 1
return -1, -1
arr = [2, 7, 11, 15]
print(two_sum_sorted(arr, 18))
Running this prints:
(1, 2)
arr[1] + arr[2] = 7 + 11 = 18.
Sorted-array intersection:
def intersect_sorted(a: list[int], b: list[int]) -> list[int]:
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] == b[j]:
result.append(a[i])
i += 1
j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return result
a = [1, 2, 2, 3, 5, 8]
b = [2, 2, 3, 6, 8, 9]
print(intersect_sorted(a, b))
Running this prints:
[2, 2, 3, 8]
Key points
- Both algorithms use the same underlying idea: sorted order lets a single comparison decide which pointer must move, replacing the memory a hash map would otherwise need to provide.
- The intersection version keeps every duplicate (two
2s appear in both inputs, so two2s appear in the output); deduplicating the result, if needed, is a separate, trivial step.
Complexity
O(n) time,O(1) extra spacefor the sorted two-sum (n is the array length), and
O(n+m) time,O(1) extra space (excluding output)for the intersection of arrays of length n and m, since each pointer advances at most once per element and never backtracks.
Edge cases
- Empty or single-element array:
two_sum_sortedcorrectly returns(-1, -1)since thewhile left < rightloop never runs. - No valid pair exists: the loop exits naturally when
leftmeetsright, returning(-1, -1). - Negative numbers: handled correctly, since the comparison
s < target/s > targetdoes not depend on sign. - One array is empty in the intersection case: the
whileloop's length check exits immediately, correctly returning an empty result.
Trade-offs & pitfalls
Reaching for a hash map here works too (build a set of one array's values in O(n) time and O(n) space, then scan the other), and is actually necessary if the input is not sorted and sorting it first is not acceptable (for example, if the original order must be preserved in the output); but given already-sorted input, that hash map is pure overhead, since the sort order already encodes everything the hash map would tell you. A common mistake is trying to adapt the sum-target converging-pointer pattern directly to intersection by starting the second pointer at the end instead of at the start: intersection is fundamentally a same-direction scan (both arrays are being consumed left to right looking for equal elements), not a converging one (which relies on one array's values increasing while the other's decrease, a relationship two independent sorted arrays don't have with each other).
You are given jobs, each with a start time, end time, and profit, and can only work one job at a time. Choose a subset of non-overlapping jobs that maximizes total profit. Explain why the simple 'always pick the job that finishes earliest' greedy rule (which works when every job has equal profit) is no longer sufficient once jobs carry different profits.
Sample Answer
Direct answer
Sort jobs by end time, then define dp[i] as the best achievable profit using the first i (sorted) jobs: either skip job i, or take it and add the best profit among jobs finishing no later than job i's start (found via binary search on the sorted end times). This gives an O(n log n) dynamic program. The "always take the job that finishes earliest" greedy rule only maximizes the COUNT of non-overlapping jobs; once jobs carry different profits, it ignores value entirely and can discard one lucrative job in favor of several cheap ones.
Structured elaboration
- Sort jobs by end time.
p(i)= the count of (sorted) jobs whose end time is ≤ job i's start time; found by binary search since end times are sorted.- Recurrence:
dp[i] = max(dp[i-1], profit_i + dp[p(i)]). - A parallel boolean array records whether job i was taken, so the actual chosen jobs can be reconstructed by walking backward.
from bisect import bisect_right
def weighted_interval_scheduling(jobs):
"""
jobs: list of (start, end, profit).
Returns (max_profit, chosen_jobs) using O(n log n) DP.
"""
jobs = sorted(jobs, key=lambda x: x[1])
ends = [e for _, e, _ in jobs]
n = len(jobs)
dp = [0] * (n + 1)
choice = [False] * (n + 1)
for i in range(1, n + 1):
s, e, p = jobs[i - 1]
j = bisect_right(ends, s) # count of jobs ending <= s
take = p + dp[j]
skip = dp[i - 1]
if take > skip:
dp[i] = take
choice[i] = True
else:
dp[i] = skip
chosen = []
i = n
while i > 0:
if choice[i]:
chosen.append(jobs[i - 1])
s, e, p = jobs[i - 1]
i = bisect_right(ends, s)
else:
i -= 1
chosen.reverse()
return dp[n], chosen
def earliest_finish_greedy(jobs):
"""Naive greedy: sort by end time, take a job if compatible with the last taken one. Ignores profit."""
jobs = sorted(jobs, key=lambda x: x[1])
total = 0
last_end = float("-inf")
taken = []
for s, e, p in jobs:
if s >= last_end:
taken.append((s, e, p))
total += p
last_end = e
return total, taken
jobs = [
(0, 1, 1),
(1, 2, 1),
(2, 3, 1),
(0, 3, 10),
]
greedy_profit, greedy_taken = earliest_finish_greedy(jobs)
dp_profit, dp_taken = weighted_interval_scheduling(jobs)
print("earliest-finish greedy (ignores profit):", greedy_profit, greedy_taken)
print("weighted DP (optimal):", dp_profit, dp_taken)
Output:
earliest-finish greedy (ignores profit): 3 [(0, 1, 1), (1, 2, 1), (2, 3, 1)]
weighted DP (optimal): 10 [(0, 3, 10)]
Worked example
Four jobs: three tiny back-to-back jobs each worth 1, plus one long job worth 10 that overlaps all three. The earliest-finish greedy takes the three tiny jobs (they're mutually compatible and each looks attractive by finish time) for a total profit of 3. The weighted DP correctly recognizes the single long job is worth more than all three short ones combined, and picks it alone for a profit of 10, exactly matching the run above.
Complexity
O(nlogn) time: O(nlogn) for the initial sort plus O(nlogn) total for the
n binary searches; O(n) space for the dp and choice arrays.
Edge cases
- Empty job list:
n=0,dp=[0], the loop never runs, returning(0, []). - Single job:
dp[1] = max(dp[0], profit) = profit(sincedp[0]=0), so that one job is
always taken. - Back-to-back (boundary) jobs: "compatible" here means one job's end is ≤ the next
job's start;bisect_right(ends, s)counts a job ending at exactlysas compatible, so
adjacent jobs like(0,1,1)and(1,2,1)in the worked example are correctly treated as
non-overlapping; using the wrong bisect variant can either double-count a boundary case or
wrongly exclude a legally compatible job. - All jobs mutually overlapping: the DP reduces to picking whichever single job has the
highest profit, since no combination of two or more can be taken together.
Trade-offs & pitfalls
- Pitfall: forgetting to sort by end time first breaks the monotonicity the binary search depends on.
- Streaming variant: this DP needs the full sorted list to compute each
p(i), so it doesn't directly apply if jobs must be decided immediately on arrival without storing the whole set; that calls for either a genuinely online algorithm (with weaker guarantees) or periodic re-solving over a bounded lookahead buffer. - Recovering the chosen jobs, not just the total profit, requires the extra
choicearray shown above; the profit-only version of the DP throws that information away.
Rotate an array to the right by k steps in-place, using O(1) extra space (k may exceed the array's length). Explain your approach, and how the same in-place three-reversal trick generalizes: reversing a string in place, or rotating a 2D matrix in place.
Sample Answer
Direct answer
Reverse the whole array, then reverse the first k elements and the remaining n-k elements separately; three linear passes compose into the fully rotated result with no auxiliary array. The same reversal trick generalizes directly: reversing a string in place is the identical two-pointer, swap-from-both-ends routine, and rotating a square matrix 90 degrees in place is a transpose followed by reversing each row, both built on the same in-place-swap primitive as the array rotation.
Structured elaboration
Why three reversals produce a rotation. Reversing the entire array puts every element in fully reversed order. Reversing the first k elements of that reversed array un-reverses exactly the block that should now sit at the front, restoring its original relative order; reversing the remaining n-k elements does the same for the remainder. Normalizing with k %= n handles k values larger than the array's length or equal to zero.
Generalizing to a string. The same in-place two-pointer swap from both ends is exactly what reverses a string, provided the string is held in a mutable container (a list of characters, for example, since Python's own string type is immutable and cannot be reversed truly in place without first converting it).
Generalizing to a square matrix. Transposing swaps matrix[i][j] with matrix[j][i] for every i < j, turning rows into columns. Reversing each row afterward flips left to right. Combined, what was the first column read top to bottom becomes the first row read left to right, which is exactly a 90-degree clockwise turn.
Related in-place-preprocessing techniques (with an honest space caveat). Prefix-sum preprocessing builds an auxiliary array once, in O(n) time, so that any later range-sum query answers in O(1); this trades O(n) extra space for fast queries, so it is not itself an O(1)-extra-space technique, even though it shares this family's "one linear pass, reuse the result" character. Product-except-self, by contrast, genuinely can be done with O(1) extra space beyond the required output array: a first pass fills the output with the running product of everything to each index's left, and a second pass multiplies in the running product of everything to that index's right, needing no separate auxiliary array at all.
Worked example
def rotate_array(nums: list[int], k: int) -> None:
n = len(nums)
if n <= 1:
return
k %= n
if k == 0:
return
def reverse(i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
def reverse_string_inplace(chars: list[str]) -> None:
i, j = 0, len(chars) - 1
while i < j:
chars[i], chars[j] = chars[j], chars[i]
i += 1
j -= 1
def rotate_matrix_90_cw_inplace(matrix: list[list[int]]) -> None:
n = len(matrix)
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5, 6, 7]
rotate_array(arr, 3)
print(arr)
chars = list("hello")
reverse_string_inplace(chars)
print("".join(chars))
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_matrix_90_cw_inplace(m)
print(m)
Running this prints [5, 6, 7, 1, 2, 3, 4], then olleh, then [[7, 4, 1], [8, 5, 2], [9, 6, 3]].
Complexity
rotate_array: time O(n) for the three reversal passes, since they compose additively into a single linear scan rather than multiplying; space O(1) extra, using only the two index pointers inside each reversal call.
reverse_string_inplace: time O(n), one pass with two pointers closing in from both ends; space O(1) extra beyond the mutable character list itself.
rotate_matrix_90_cw_inplace: time O(n2) for an n-by-n matrix, since the transpose visits each of the n2 cells once; space O(1) extra, since both the transpose and the row reversals swap in place with no auxiliary matrix.
Edge cases
- k = 0, or k a multiple of the array's length once normalized via
k %= n:rotate_arraydetects this and returns immediately without performing any reversals, since the array is already in its correct rotated position. - Empty or single-element array or string: both
rotate_array(via itsn <= 1guard) andreverse_string_inplace(viawhile i < jnever firing) return immediately with nothing to do. - A non-square matrix passed to
rotate_matrix_90_cw_inplace: this implementation assumes a square matrix, and a non-square transpose changes the matrix's dimensions, so it cannot be rotated true in place this way.
Trade-offs & pitfalls
Forgetting k %= n for a k larger than the array's length either wastes work or, in a careless implementation, indexes out of range. The transpose-then-reverse-rows trick only works for a square matrix: transposing a non-square matrix changes its dimensions, so a genuinely non-square rotation needs a separate output buffer rather than a true in-place transform. Python's string immutability means a real in-place string reversal needs a mutable container (a list of characters, or a bytearray) first; there is no way to mutate a str object's characters directly.
Unlock Full Question Bank
Get access to all Algorithmic Problem-Solving and Data Structure Selection interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.