Assess the ability to analyze, compare, and optimize algorithmic solutions with respect to time and space resources. Candidates should be fluent in Big O notation and able to identify dominant operations, reason about worst case, average case, and amortized complexity, and calculate precise time and space bounds for algorithms and data structure operations. The topic includes recognizing complexity classes such as constant time, logarithmic time, linear time, linearithmic time, quadratic time, and exponential time, and understanding when constant factors and lower order terms affect practical performance. Candidates should know and apply common algorithmic patterns and techniques, including two pointers, sliding window, divide and conquer, recursion, binary search, dynamic programming, greedy strategies, and common graph algorithms, and demonstrate how to transform brute force approaches into efficient implementations. Coverage also includes trade offs between time and space and when to trade memory for speed, amortized analysis, optimization tactics such as memoization, caching, pruning, iterative versus recursive approaches, and data layout considerations. Candidates must be able to reason about correctness, invariants, and edge cases, identify performance bottlenecks, and explain practical implications such as cache behavior and memory access patterns. For senior roles, be prepared to justify precise complexity claims and discuss optimization choices in system level and constrained environment contexts.
MediumTechnical
73 practiced
Design an efficient Sudoku solver using backtracking augmented with constraint propagation and heuristics. Describe practical heuristics (MRV - minimum remaining values, forward checking, least-constraining-value), use of bitmasks for speed, and analyze worst-case exponential complexity vs why real puzzles are solved fast.
Sample Answer
To solve Sudoku efficiently use backtracking + constraint propagation with three heuristics: MRV (choose cell with fewest candidates), forward checking (update peers’ domains after assignment), and least-constraining-value (try values that remove fewest candidates from peers). Represent domains with 9-bit bitmasks for speed.
python
# Python: bitmask-based Sudoku solver with MRV + forward checking + LCV
ALL = (1<<9)-1 # bits 0..8 represent digits 1..9
def bit_count(x): return x.bit_count()
def bits_to_vals(x): return [i+1 for i in range(9) if x & (1<<i)]
# prepare peers: list of 81 sets of indices (rows, cols, box)
# assume peers precomputed: peers[i] -> set of indices
def solve(domains):
# domains: list of 81 ints (bitmask of candidates)
if all(d & (d-1) == 0 for d in domains): # all singletons
return domains
# MRV: pick unassigned with fewest candidates (>1)
idx = min((i for i,d in enumerate(domains) if bit_count(d)>1),
key=lambda i: bit_count(domains[i]))
# LCV: order values by how many peer candidates they'd eliminate
vals = bits_to_vals(domains[idx])
def elim_count(v):
mask = 1<<(v-1)
cnt = 0
for p in peers[idx]:
if domains[p] & mask: cnt += 1
return cnt
for v in sorted(vals, key=elim_count): # least constraining first
snapshot = domains.copy()
domains[idx] = 1<<(v-1)
# forward checking: remove v from peers
failed = False
stack = [p for p in peers[idx] if domains[p] & (1<<(v-1))]
for p in stack:
domains[p] &= ~(1<<(v-1))
if domains[p] == 0:
failed = True; break
if bit_count(domains[p]) == 1:
# propagate singleton further (simple propagation)
s = p
val = domains[s].bit_length()-1
for q in peers[s]:
domains[q] &= ~(1<<(val-1))
if domains[q] == 0: failed = True; break
if failed: break
if not failed:
res = solve(domains)
if res: return res
domains = snapshot
return None
Key points:- Bitmasks give O(1) candidate ops and fast counting.- MRV reduces branching; forward checking catches dead-ends early; LCV reduces conflicts.- Worst-case complexity is still exponential (NP-complete), but typical human puzzles are sparse and structured so propagation prunes enormously; combined heuristics solve them near-instantly.Edge cases: invalid inputs (contradictory clues), puzzles with multiple solutions (return first or enumerate), ensure peers computed correctly. Alternative: use Dancing Links (DLX) for exact-cover if you need guaranteed speed on hardest instances.
MediumTechnical
70 practiced
Compare BFS and DFS graph traversals in terms of time and space complexity (O(V+E) time), and explain scenarios where BFS is preferable (e.g., shortest path in unweighted graphs) and where DFS is preferable (e.g., topological sort, component discovery). Discuss iterative vs recursive DFS and memory footprints of queue vs recursion stack.
Sample Answer
BFS and DFS both visit every vertex and edge once in standard adjacency-list implementations, so time complexity is O(V + E). The difference is in traversal order and space usage.Space complexity:- BFS uses a FIFO queue to hold frontier nodes. In the worst case (e.g., a wide layer in a tree or a dense level in a graph) the queue can hold O(V) nodes, so worst-case space is O(V).- DFS uses a stack of active recursion frames (recursive) or an explicit stack (iterative). Worst-case depth is O(V) (a long path), so DFS worst-case space is also O(V), though typical memory usage depends on graph shape (deep vs wide).When to prefer BFS:- Shortest path in unweighted graphs (BFS finds minimum number of edges from source to all reachable nodes).- Finding the nearest node satisfying a predicate (e.g., closest target).- Level-order processing or building layer-by-layer properties.When to prefer DFS:- Topological sort and cycle detection in directed acyclic graphs (using post-order).- Connected component / strongly connected component discovery (as part of Kosaraju/Tarjan).- Space-efficient for very wide but shallow graphs because DFS tends to store only the path (depth) rather than an entire frontier.- Pathfinding where any path suffices and you want to explore deeply (backtracking, maze solving).Iterative vs recursive DFS:- Recursive DFS is concise and maps directly to theory, but recursion depth may cause stack overflow for large or adversarial graphs. Its memory usage is the recursion stack (O(depth)).- Iterative DFS using an explicit stack gives you control (can simulate post-order using visited flags or state tuples), avoids recursion limits, and can be marginally faster by avoiding function-call overhead.Memory footprint comparison:- Queue (BFS): stores all nodes at current breadth → may be large for high branching factor.- Recursion stack (DFS): stores nodes along a single path → may be large for long chains.Choose BFS when you need shortest unweighted paths or level information; choose DFS when you need ordering, component structure, or lower memory on wide graphs, and use iterative DFS when recursion limits are a concern.
MediumTechnical
140 practiced
Given a set of intervals with start and end times, design and implement an algorithm to select the maximum number of non-overlapping intervals. Provide a proof of correctness for the greedy strategy you choose (e.g., earliest finish time) and analyze time and space complexity. Implement in Python or Java.
Sample Answer
Approach:Use the classic greedy: sort intervals by increasing finish time and repeatedly pick the earliest-finishing interval that doesn't conflict with the last selected one. This maximizes the number of non-overlapping intervals.
python
from typing import List, Tuple
def max_non_overlapping(intervals: List[Tuple[int,int]]) -> List[Tuple[int,int]]:
"""
Returns a maximum-size set of non-overlapping intervals.
intervals: list of (start, end), end > start assumed.
"""
# Sort by end time (then start to stabilize)
intervals_sorted = sorted(intervals, key=lambda x: (x[1], x[0]))
result = []
last_end = float('-inf')
for s, e in intervals_sorted:
if s >= last_end:
result.append((s, e))
last_end = e
return result
Proof of correctness (sketch):Let A be solution by greedy, O an optimal solution. After sorting by finish times, greedy picks interval i1 with earliest finish. If O doesn't pick i1, we can replace O's earliest-finishing interval with i1 without reducing count because i1 finishes no later and doesn't overlap later choices. By induction on remaining intervals, greedy is optimal.Time & Space:- Time: O(n log n) for sorting + O(n) scan => O(n log n).- Space: O(n) for sorting and output (or O(1) extra aside from output if in-place).Edge cases:- Empty list, intervals with equal end times, intervals contained within others — handled by sorting tie-breaker. Validate intervals where end <= start if needed.
MediumTechnical
92 practiced
Design an O(n) expected time algorithm in Python to solve the classic Two-Sum problem: given an array and a target, return indices of two numbers that add up to target. Discuss collision handling, memory trade-offs, and how to adapt this approach for a streaming input where the array doesn't fit in memory.
Sample Answer
To solve Two-Sum in expected O(n) time we use a hash map (dictionary) that maps value -> index while scanning the array once.
python
def two_sum(nums, target):
"""
Return indices (i, j) such that nums[i] + nums[j] == target.
Expected O(n) time, O(n) extra space.
"""
seen = {} # value -> index
for i, v in enumerate(nums):
need = target - v
if need in seen:
return [seen[need], i]
# store first index for this value (keeps deterministic behavior)
if v not in seen:
seen[v] = i
return None # no pair found
Key points and reasoning:- Approach: single pass; for each element check if complement already seen. Hash lookups are O(1) expected, giving O(n) expected runtime.- Collision handling: Python dict uses open addressing + probing with high-quality hash; collisions are resolved internally (probing) and still give expected O(1). If implementing your own hashmap, use chaining or open addressing with resizing and a good hash function to keep load factor low (e.g., <0.7).- Memory trade-offs: This solution uses O(n) extra memory to store seen values. If memory is tight, options: - Sort + two pointers: O(n log n) time, O(1) extra space if in-place, but you lose original indices (you'd need to store pairs (value,index) so O(n) space or stable mapping). - Use external storage / disk-backed hash table to trade memory for I/O.- Streaming adaptation (array doesn't fit in memory): - If one pass must find a pair and you can store only a limited set: use a Bloom filter to test membership (low memory, false positives possible) then verify by fetching candidate(s) from backing store; Bloom filters can't return indices so you'd need external index mapping. - Practical approach: partition the stream by hashing values into K buckets written to disk so each bucket fits memory (external hashing / map-reduce style). Then for each bucket, load it and run in-memory two-sum. Partitioning ensures complements land in corresponding buckets (use consistent partitioning on value and target-value). This is O(n) work plus disk I/O; pick K so each bucket fits RAM.Edge cases: duplicates, negative numbers, no solution, very large integers (hashing still works).
EasyTechnical
144 practiced
Implement in Python a function that removes duplicates in-place from a sorted list of integers and returns the new length. Constraint: O(1) additional space and O(n) time. Example: nums = [0,0,1,1,1,2,2,3,3,4] -> returns 5 and modifies prefix to [0,1,2,3,4]. Explain why your algorithm meets the complexity bounds.
Sample Answer
Approach: Use two pointers (slow and fast). slow tracks position to write next unique value; fast scans the array. When nums[fast] != nums[slow], increment slow and copy nums[fast] to nums[slow]. This is in-place, O(1) extra space, single pass O(n) time.
python
def remove_duplicates(nums):
"""
Removes duplicates in-place from a sorted list.
Returns the new length (number of unique elements).
Modifies nums so that the first returned_length elements are the unique values.
"""
if not nums:
return 0
slow = 0 # index of last unique element
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast] # overwrite duplicate
return slow + 1 # length is index + 1
# Example:
# nums = [0,0,1,1,1,2,2,3,3,4]
# new_len = remove_duplicates(nums) # new_len == 5
# nums[:new_len] == [0,1,2,3,4]
Key points:- Uses two-pointer technique; only indices are extra (O(1) space).- Single linear pass: O(n) time because each element is visited once.- Handles edge cases: empty list returns 0; list with all identical elements returns 1.- Stable for sorted input; requires sorted order to work correctly.
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
