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.
EasyTechnical
90 practiced
State the preconditions required for binary search to work correctly on an array. Implement in plain English (or pseudocode) a variant that finds the first index of a target value in a sorted array with duplicates and analyze its time complexity and edge cases.
Sample Answer
Preconditions:- The array must be sorted in non-decreasing order (ascending).- Random access is available (indexed access in O(1)).- Comparison operator is well-defined for elements and the target.- If duplicates exist, they are contiguous (implied by sorting).Approach (find first index of target): use binary search but when you find target, continue searching left half to find the first occurrence.
python
def find_first_index(arr, target):
"""
Returns the index of the first occurrence of target in sorted array arr,
or -1 if target not present.
"""
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
result = mid # record match
right = mid - 1 # continue search on left side
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
Key points / reasoning:- Standard binary search narrows the search space logarithmically.- Recording result and moving right boundary left ensures first (leftmost) match is found.- Uses safe mid computation to avoid overflow (left + (right-left)//2).Time and space complexity:- Time: O(log n) — each loop halves the search interval.- Space: O(1) — constant extra space.Edge cases:- Empty array → returns -1.- Target smaller than all elements or larger than all → returns -1.- All elements equal to target → returns 0 (first index).- Single-element array — works for match/non-match.- Duplicates scattered? (not possible in sorted array) but algorithm assumes duplicates contiguous.Alternative:- Variant that finds last occurrence: when arr[mid]==target set result=mid and left=mid+1.- Lower_bound style: find smallest index where arr[index] >= target, then check equality to return index or -1.
HardTechnical
97 practiced
Explain the roofline model and use it to determine whether a batched matrix multiply is compute-bound or memory-bound. Given: matrix multiply requires 2 * n^3 floating point operations and moves O(n^2) elements of size 4 bytes, with peak FLOPS F_peak and memory bandwidth B, compute operational intensity and decide the bottleneck.
Sample Answer
The roofline model relates peak compute (F_peak, in FLOP/s) and peak memory bandwidth (B, in bytes/s) through operational intensity I (FLOP per byte): achievable performance P = min(F_peak, I · B). If I · B ≥ F_peak the kernel is compute-bound; otherwise it’s memory-bound.Compute I for the batched n×n matrix multiply:- FLOPs ≈ 2 n^3- Data moved ÷ bytes ≈ O(n^2) elements × 4 bytes. Using the provided scaling, bytes ≈ 4 n^2.So operational intensityI = (2 n^3) / (4 n^2) = n / 2 FLOP/byte.Apply the roofline decision:- Achievable P = min(F_peak, (n/2) · B).- The kernel is compute-bound when (n/2)·B ≥ F_peak → n ≥ 2·(F_peak / B).- Otherwise memory-bound when n < 2·(F_peak / B).Interpretation and examples:- If F_peak = 1 TFLOP/s and B = 100 GB/s (100×10^9 B/s), F_peak/B = 10 FLOP/byte, threshold n ≥ 20 makes it compute-bound.- Small n (below threshold) cannot supply enough FLOPs per byte to saturate the ALUs; performance will be limited by memory transfers. Larger n increases reuse (I ∝ n) and shifts the bottleneck to compute.Notes:- The O(n^2) data-movement constant matters in practice (reads/writes for A, B, C, caching, blocking). Blocking/tiling increases effective I (reduces bytes moved), lowering the threshold n needed to become compute-bound.- Use this formula to guide whether to optimize memory path (prefetching, layout) or compute path (vectorization, better kernels).
EasyTechnical
88 practiced
Implement in Python a function 'longest_unique_substring(s)' that returns the length of the longest substring without repeating characters. Your solution should run in O(n) time and O(min(n, alphabet_size)) additional space. Explain correctness and complexity briefly.
Sample Answer
We can solve this with the sliding-window technique using a dictionary that maps characters to their last seen index. Expand the right end of the window and, when a repeated character is encountered, move the left pointer just past the last occurrence. This yields O(n) time and O(min(n, alphabet_size)) extra space.
python
def longest_unique_substring(s: str) -> int:
"""
Return length of longest substring without repeating characters.
O(n) time, O(min(n, alphabet_size)) space.
"""
last_index = {} # char -> last index seen
left = 0 # window start
max_len = 0
for right, ch in enumerate(s):
# If ch seen and inside current window, move left to last_index[ch] + 1
if ch in last_index and last_index[ch] >= left:
left = last_index[ch] + 1
last_index[ch] = right
# window length is right - left + 1
curr_len = right - left + 1
if curr_len > max_len:
max_len = curr_len
return max_len
Key correctness points:- The window [left, right] always contains unique characters.- When a repeat is found, left jumps past the previous occurrence, preserving uniqueness.- Each character index is visited once; left only moves forward, so overall linear time.Time complexity: O(n) where n = len(s). Space complexity: O(min(n, alphabet_size)) for the last_index map.Edge cases:- Empty string -> returns 0.- All identical characters -> returns 1.- Unicode characters handled since dict keys can be any character.
HardTechnical
78 practiced
Needleman-Wunsch global sequence alignment has O(n*m) time and O(n*m) space for sequences of lengths n and m. For very long biological sequences or long NLP sequences, describe algorithmic optimizations (banded DP, Hirschberg's algorithm, suffix arrays) to reduce memory or time and analyze their complexities.
Sample Answer
Brief overview: Needleman–Wunsch (NW) fills an n×m DP table -> O(nm) time and space. For very long sequences this is often infeasible; common algorithmic optimizations trade correctness guarantees, memory, or running time depending on problem structure.1) Banded DP (aka banded Needleman–Wunsch)- Idea: if sequences are similar (limited indels), most optimal path stays near diagonal. Compute only cells with |i − j| ≤ k (bandwidth k).- Time: O(k·max(n,m)). Space: O(k·max(n,m)) or O(k) per row for rolling arrays.- When to use: pairwise alignment of moderately divergent sequences or anchored alignments. Risk: misses alignments with large shifts; choose k based on expected divergence.2) Hirschberg’s algorithm (space-efficient divide-and-conquer)- Idea: computes global alignment with full optimal score but only O(min(n,m)) space using recursive split: compute forward and reverse score vectors to find split point, recurse.- Time: still O(nm). Space: O(min(n,m)) plus recursion overhead O(log n) stack.- When to use: need exact alignment but memory-limited (e.g., long reads). Trade-off: same time cost, more constant-factor work due to repeated passes.3) Suffix arrays / suffix trees and seeding approaches- Idea: index one sequence (suffix array/ FM-index) to quickly find exact/approximate matches (seeds), then extend locally with DP. This reduces DP region to seed neighborhoods.- Complexity: building suffix array/O(n)–O(n log n) and queries near O(p + occ); overall alignment time depends on seed count and extension window — often near linear in practice for sparse seeds.- When to use: long genomes or long NLP strings where high-similarity local matches exist. Trade-offs: may miss alignments without good seeds; indexes have construction cost but support many queries.Additional notes:- Combine methods: seed-and-extend + banded DP + Hirschberg for exact alignment within band.- Other optimizations: bit-parallel Myers algorithm (O(⌈m/w⌉·n) time where w = word size), SSE/AVX vectorization, heuristic filters.Summary: choose based on accuracy needs, expected divergence, memory budget, and whether many queries reuse an index.
MediumTechnical
73 practiced
You must deduplicate a terabyte-scale dataset of text where data cannot fit in memory. Compare a hash-based streaming deduplication (using chunked hashing + external index) to an external sort-based deduplication approach. Describe algorithmic complexity, IO costs, and when to use each.
Sample Answer
Situation: You need to deduplicate a terabyte of text that cannot fit in memory. Two common scalable approaches are streaming hash-based deduplication (chunked hashing + external index) and external sort-based deduplication. Below is a concise comparison covering algorithms, complexity, IO costs, trade-offs, and guidance on when to pick each.Hash-based streaming (chunk + external index)- Algorithm: Stream input, compute a cryptographic or strong non-cryptographic hash per record or chunk (e.g., SHA-256 or xxHash64). Check presence in an external key–value store or disk-backed index (LSM-tree, RocksDB, or a sorted on-disk hash table). If absent, emit record and insert hash into index.- Time complexity: O(N) hash computations and O(N) index reads/writes (amortized), so O(N) work.- IO costs: One sequential read of data + index lookups/writes for each unique and duplicate record. If index fits partly in memory (cache), many ops are in-memory; otherwise random IO dominates—use LSM-tree batched writes to convert random writes to sequential SSTable writes.- Pros/cons: Low latency, single-pass, simple to parallelize, good when deduplication must stream or integrate into pipelines. Downside: needs reliable external index storage and additional storage size ~O(U) (unique hashes). Susceptible to hash collisions (mitigate with strong hashes + optional byte-compare on match).External sort-based deduplication- Algorithm: Use external merge sort: read chunks that fit in memory, sort each chunk by record (or by hash), write sorted runs to disk, then multi-way merge runs; while merging, drop consecutive duplicates.- Time complexity: O(N log N) dominated by sorting work across runs, but with good external sort implementations constant factors are low.- IO costs: Typically 2–3 passes over data: read input, write sorted runs, read runs during merge, write final output — roughly 2–3 × data size of sequential IO (plus temporary run files). IO is mostly sequential, so high throughput on disks.- Pros/cons: Deterministic (no collision risk), no additional random-index store, excellent sequential IO patterns, predictable resource usage. Downside: multi-pass, higher CPU for comparisons, and requires temporary disk space ~O(N).When to use each- Choose hash-based streaming when you need single-pass low-latency processing, when you have a reliable disk-backed index (e.g., RocksDB) or distributed KV store, and when random IO can be mitigated (SSD/LSM). Good for streaming pipelines and incremental dedupe.- Choose external sort when you want lower operational complexity (no external index), guarantee correctness without collision risk, and can tolerate extra passes. Prefer when storage medium favors high sequential throughput (HDDs, network storage) or when merging/grouping results are also needed (e.g., aggregation).Practical tips- For hashing: use 64–256-bit hashes and optionally verify on match to avoid false positives. Batch index writes and use bloom filters to reduce index lookups.- For sorting: tune run size to memory and use parallel merges; compress runs to save IO.- Hybrid: Hash-partition the dataset (range or mod by hash) into K buckets that fit in memory, then dedupe each bucket in-memory or via external sort — combines single-pass partitioning with efficient local processing.
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
