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
122 practiced
Implement a substring search function in Java that returns the first index of a pattern (needle) in a text (haystack) using the Knuth-Morris-Pratt (KMP) algorithm. Your implementation must run in O(n + m) time and use O(m) extra space for the prefix-function (where n = text length, m = pattern length). Explain correctness and complexity.
Sample Answer
**Approach (brief)** Build the KMP prefix-function (lps) for the pattern (needle) in O(m) time/space, then scan the text (haystack) using lps to avoid re-checking characters — overall O(n + m).**Java implementation**
java
// Return first index of needle in haystack or -1 if not found
public int kmpSearch(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int n = haystack.length(), m = needle.length();
int[] lps = buildLPS(needle);
int i = 0, j = 0; // i -> haystack, j -> needle
while (i < n) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++; j++;
if (j == m) return i - m; // match found
} else if (j > 0) {
j = lps[j - 1]; // fall back in pattern
} else {
i++;
}
}
return -1;
}
private int[] buildLPS(String p) {
int m = p.length();
int[] lps = new int[m];
int len = 0; // length of previous longest prefix suffix
for (int i = 1; i < m; ) {
if (p.charAt(i) == p.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
**Correctness** lps[k] stores the longest proper prefix of needle[0..k] that is also a suffix; when a mismatch occurs we jump j to lps[j-1], preserving already matched information and never missing a potential match. This guarantees we check each character of haystack at most once per advancement.**Complexity** Time: O(m) to build lps + O(n) to scan = O(n + m). Space: O(m) extra for lps. This implementation is suitable for backend string-processing tasks (log parsing, routing, pattern-based validation) where linear-time guarantees matter.
HardSystem Design
84 practiced
Design a cache invalidation strategy for a distributed multi-region cache holding user profiles that can be updated frequently and must reflect changes within ~1s. Compare cache-aside, write-through, write-behind, and push-invalidation (pub/sub) approaches. For each, analyze per-update and per-read time and space complexity, network costs, failure modes, and consistency guarantees under partitions.
Sample Answer
**Clarifying constraints**User profiles updated frequently, must reflect changes within ~1s across multi-region caches. Strong consistency desirable but availability under partition matters.**Options—summary + analysis**1) **Cache-aside (lazy)**- How: App writes DB, invalidates or deletes cache entry.- Per-update: O(1) local ops + O(1) network to invalidate (or delete). Per-read: O(1) if hit, else DB read + populate.- Space: cache stores only hot keys.- Network cost: low writes, extra reads on misses.- Failure modes: missed invalidation → stale reads until TTL; race if read/write concurrent.- Consistency under partition: Eventually consistent; can be stale >1s unless aggressive TTL or synchronous invalidation.2) **Write-through**- How: Write goes to cache synchronously then DB (or vice versa with sync).- Per-update: O(1) to cache + O(1) DB; write latency increases.- Per-read: O(1) from cache.- Space: cache holds written keys.- Network cost: higher (every write touches cache).- Failure modes: cache write failure requires retry/rollback; risk of longer write latency.- Consistency: Stronger (reads reflect recent writes if cache write is synchronous); under partition, choose to fail writes to keep consistency.3) **Write-behind (async)**- How: Write to cache immediately, persist to DB asynchronously.- Per-update: O(1) low latency; DB writes batched later.- Per-read: O(1) cache.- Space: same.- Network cost: lower amortized DB cost, but risk of lost async writes.- Failure modes: data loss on cache crash before flush; ordering challenges.- Consistency: Reads see latest write (in region) but global DB lags → risky for multi-region.4) **Push-invalidation (pub/sub)**- How: On DB commit, publish invalidation/updated object to all regions via regional brokers (Kafka, Redis Streams).- Per-update: O(R) network fan-out but message small (invalidate or delta).- Per-read: O(1) local read; misses trigger DB or local fetch.- Space: like cache-aside.- Network cost: medium (one message per update across regions).- Failure modes: message loss (mitigate with durable streams), ordering delays.- Consistency: Near-strong if delivery <1s; with durable pub/sub and acked delivery you can guarantee invalidation within SLA. Under partition, messages may be delayed — choose degrade to serving stale reads or fail.**Recommendation**For ~1s freshness across regions I’d use cache-aside + reliable pub/sub push-invalidation: writes update DB, publish invalidation/update event to region brokers; readers consult local cache then DB on miss. This balances low read latency, bounded cross-region network cost, and with durable streaming (Kafka/Redis Streams + consumer acks and sequence numbers) and short TTL fallback, it meets ~1s freshness while handling partitions by allowing controlled staleness or failing reads depending on SLAs.
HardTechnical
72 practiced
Prove that any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case using the decision-tree model. Then explain when counting sort or radix sort can achieve linear-time (O(n) or O(n + k)), listing exact time and space bounds and the required constraints on the input domain.
Sample Answer
**Proof (decision-tree lower bound)**- Model: any comparison sort on n distinct items is a binary decision tree where each internal node is a comparison and each leaf is a possible permutation (output order).- There are n! possible orderings, so the tree must have at least n! leaves.- A binary tree of height h has ≤ 2^h leaves, so 2^h ≥ n! ⇒ h ≥ log2(n!).
text
h >= log2(n!)
- Using Stirling (or standard bounds) log2(n!) = Θ(n log2 n). Therefore any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case.
text
log2(n!) = Θ(n log2 n)
Why this matters for backend engineers: for large arbitrary-key sorts (e.g., sorting DB query results by arbitrary values) you cannot beat n log n if only comparisons are available.**When counting sort or radix sort are linear**Counting sort:- Time: O(n + k)- Space: O(n + k) (output array + count array of size k)- Constraint: keys are integers in a small range 0..k-1; linear time iff k = O(n). If k ≫ n, counting sort becomes inefficient.Radix sort (LSB or MSD using stable counting sort on digits):- Let keys be integers with d digits in base b (so key range U gives d = ceil(log_b (U+1))).- If counting sort is used per digit (cost O(n + b)), total time: O(d * (n + b))- Space: O(n + b)- Achieves O(n) when d = O(1) or when b = O(n) and d = O(1), e.g. 32-bit integers with base b = 2^16 ⇒ d = 2 and per-pass counting array size b = 65536 gives time O(n + b) ≈ O(n) if n is much larger than b or if b chosen proportional to n.Practical guidance for backend systems:- Use comparison sorts (quicksort/mergesort) for general keys.- Use counting/radix when keys are integers with limited range (IDs, timestamps bucketed, fixed-width integers) to get near-linear performance, paying attention to memory (count array) and stability requirements (stable per-digit pass).
EasyTechnical
92 practiced
Consider the following Python function:\n\n
python\ndef pairs_sum_zero(arr):\n n = len(arr)\n result = []\n for i in range(n):\n for j in range(i+1, n):\n if arr[i] + arr[j] == 0:\n result.append((arr[i], arr[j]))\n return result\n
\n\na) What is the worst-case time and space complexity of pairs_sum_zero in Big-O notation? b) Propose a more efficient algorithm for the same problem, describe its time/space complexity and any trade-offs.
Sample Answer
**Answer (a) — Complexity of given function**- Time: O(n^2) — two nested loops iterate over all pairs in worst case.- Space: O(k) for result, where k is number of found pairs. In worst case k = O(n^2) (e.g., all zeros or all matching negatives/positives), so worst-case space O(n^2).**Answer (b) — More efficient algorithm (hash-based)**Approach: scan once, use a hash set to record seen values and emit a pair when the negation exists. This finds each valid pair in O(1) average lookup.
python
def pairs_sum_zero_hash(arr):
seen = set()
result = []
for x in arr:
if -x in seen:
result.append((x, -x))
seen.add(x)
return result
- Time: O(n) average; O(n^2) worst-case if hash degrades (rare in practice).- Space: O(n) for the seen set plus O(k) for result; worst-case O(n + k).Trade-offs:- Pros: Linear time on average, much better for large arrays.- Cons: Uses extra memory (O(n)); this version reports one pair per matching occurrence and may double-count order — you can canonicalize pairs (e.g., (min,max)) or deduplicate with a set if unique pairs are required. Hash lookups assume good hash behavior (typical in backend systems).
HardTechnical
92 practiced
A hot numeric routine sums differences over 100 million pairs of 64-bit values from a ByteBuffer via JNI. Discuss optimizations using memory alignment, cache-line aware blocking, loop unrolling, and SIMD/vectorization. Explain how each optimization affects throughput and per-element time, and when to prefer JVM intrinsics (Vector API) vs hand-written native code considering JNI overhead and GC interactions.
Sample Answer
**Approach summary**I would treat this as a hot inner loop problem: reduce memory stalls and expose vector parallelism. Optimize in stages and measure each change with microbenchmarks.**Memory alignment**- Align the ByteBuffer base and working pointers to 64-byte cache-line (or at least 16/32-byte) boundaries to avoid split-line accesses and enable aligned loads/stores.- Effect: reduces cycles per load, lowers L1/L2 miss penalty → improves per-element time.**Cache-line aware blocking**- Process in blocks sized to fit in L1/L2 (e.g., 4–16 KB). Read whole blocks sequentially to maximize spatial locality and prefetcher efficiency.- Effect: higher throughput due to fewer cache misses and better prefetch utilization.**Loop unrolling**- Unroll 4–8 iterations to reduce branch and loop overhead and expose independent loads for out-of-order execution.- Effect: decreases per-element overhead; helps feed SIMD units and hides memory latency.**SIMD / Vectorization**- Use 256/512-bit intrinsics (AVX2/AVX-512) to compute multiple 64-bit differences and horizontal sums per instruction.- Effect: multiplies throughput by vector width (4x for 256-bit with 64-bit lanes); reduces per-element arithmetic time dramatically.**JVM Vector API vs native via JNI**- Prefer JVM Vector API when: - You want low maintenance, safety, and portability across CPU types. - Throughput target is moderate and avoiding JNI overhead and GC pinning matters. - Recent JVM + JIT can generate efficient SIMD with zero-copy ByteBuffer and can inline hot loops.- Prefer native when: - You need hand-tuned AVX-512, non-temporal stores, or explicit prefetch beyond JIT-generated code. - You must squeeze maximum cycles/per-element and can amortize JNI call cost (batch large blocks per call). - You carefully manage GC by using direct (off-heap) ByteBuffers and avoid per-element JNI transitions.**Practical notes**- Minimize JNI transitions: do one large native call, operate on direct buffer addresses, and return a scalar result.- Benchmark with realistic data and thread counts; watch for false sharing when multi-threading.- Validate with perf/VTune and JVM JIT reports to confirm vectorization and aligned loads.
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
