Backend practice series: 1. Requirements and data design · 2. APIs and overbooking · 3. Interview review · 4. Recursion and sorting · 5. SQL exercises · 6. SQL on the E-Learning database
This post quickly reviews sorting and searching, then goes deep on recursion: complexity, memoization, and replacing recursion with an explicit stack. Afterwards you can handle the usual interview follow-ups and solve the two exercises that come with it. Big-O basics are in Basic algorithms; try the exercises yourself before opening the solutions.
At a glance:
flowchart TD
R[Recursive function] --> T["Recurrence T(n)"]
R --> S["Stack: O(depth)"]
R --> Q{Repeated subproblems?}
Q -->|yes| M[Memoization]
Q -->|no| D{Depth depends on data?}
D -->|yes| L["Loop + ArrayDeque"]
D -->|no| K[Keep recursion]
SO[Sorting] --> P["int[]: Dual-Pivot Quicksort"]
SO --> TS["Object[]: stable TimSort"]
1. Algorithms review
Key idea: remember the order of the complexity classes and the sorting table below; merge sort and heap sort are always O(n log n), quick sort’s worst case is O(n²).
- Classes (best to worst): O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
- There’s time and space complexity, and best / average / worst cases. Big-O usually means the worst or amortised case (amortised: the average cost over many operations).
- Stable: elements with equal keys keep their original order.
| Sorting algorithm | Best | Average | Worst | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Search complexity table
| Search | Complexity | Requirement |
|---|---|---|
| Linear | O(n) | None |
| Binary | O(log n) | Sorted data with O(1) random access |
Hash table (HashMap) |
O(1) average | Worst case O(log n) since Java 8 (buckets become trees) |
Balanced tree (TreeMap) |
O(log n) | When you need ordering or range queries |
| Graph traversal BFS/DFS | O(V + E) |
2. Recursion, the senior view
Key idea: interviews ask three things: the complexity, how to optimise when subproblems repeat, and how to avoid StackOverflowError.
2.1 The complexity of a recursive function
Key idea: write the recurrence T(n) (the running time expressed in terms of itself on smaller input) from the number of recursive calls and the work per level, then match it to a familiar shape.
| Recurrence | Example | Time | Stack depth |
|---|---|---|---|
| T(n) = T(n − 1) + O(1) | sum 1..n, powLinear, walking an array recursively |
O(n) | O(n) |
| T(n) = T(n / 2) + O(1) | fast exponentiation, binary search | O(log n) | O(log n) |
| T(n) = 2T(n / 2) + O(n) | merge sort | O(n log n) | O(log n) |
| T(n) = T(n − 1) + O(n) | reverseNaive (a new string per level), recursive selection sort |
O(n²) | O(n) |
| T(n) = T(n − 1) + T(n − 2) + O(1) | naive Fibonacci | O(φⁿ) ≈ O(1.618ⁿ) | O(n) |
Two things people forget:
- Recursion’s memory includes the stack, so
sum(n)uses O(n) memory without allocating anything. - For divide and conquer, what matters is number of branches × size of each branch, not just “it halves the input”.
2.2 Memoization: when subproblems repeat
Key idea: when subproblems repeat, remember their results (memoization) and the complexity collapses from exponential to linear. That’s the root of dynamic programming.
Naive Fibonacci computes fib(28) twice, fib(27) three times, and so on (fib(30) takes 2.7 million calls). Like doing homework without scratch notes: every question is worked out from scratch.
| Version | Time | Memory |
|---|---|---|
fibNaive |
O(2ⁿ) | O(n) stack |
fibMemo (top-down) |
O(n) | O(n) array + O(n) stack |
fibIter (bottom-up, two variables) |
O(n) | O(1), no stack |
Code for the three Fibonacci versions
// O(2^n): every call splits in two, and subproblems get recomputed over and over
static long fibNaive(int n) {
return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}
// Memoization (top-down): each n is computed once -> O(n) time, O(n) memory + O(n) stack
static long fibMemo(int n, long[] memo) {
if (n < 2) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
}
// Tabulation (bottom-up) reduced to two variables: O(n) time, O(1) memory, no stack
static long fibIter(int n) {
long prev = 0, cur = 1;
for (int i = 0; i < n; i++) {
long next = prev + cur;
prev = cur;
cur = next;
}
return prev;
}
// fibNaive(30) = 832040 after 2,692,537 calls; fibMemo(90) = fibIter(90) = 2880067194370816120
2.3 Replacing recursion with an explicit stack
Key idea: when recursion depth depends on the data, push the “work still to do” onto an ArrayDeque on the heap and loop until it’s empty. Java doesn’t optimise tail calls, so this is the reliable fix.
Data of arbitrary depth (category trees, nested comments, dependency graphs) can take a service down: a degenerate tree 100,000 levels deep makes the recursive version throw StackOverflowError, while the loop keeps working.
The conversion rule:
- Each recursive call becomes a
push; the function body becomes the processing after apop. - For post-order results (children before the parent): push an extra “children visited” marker, or use two stacks.
- For graphs: add a
visitedset, otherwise cyclic data loops forever even without recursion.
Code for counting a category tree: recursive and explicit stack
record Category(String name, List<Category> children) {
Category(String name) { this(name, new ArrayList<>()); }
}
// Recursive: short, but stack depth = tree depth
static int countRecursive(Category c) {
int total = 1;
for (Category child : c.children()) total += countRecursive(child);
return total;
}
// Loop + explicit stack: the stack lives on the heap, not limited by -Xss
static int countIterative(Category root) {
Deque<Category> stack = new ArrayDeque<>();
stack.push(root);
int total = 0;
while (!stack.isEmpty()) {
Category c = stack.pop();
total++;
for (Category child : c.children()) stack.push(child);
}
return total;
}
// A degenerate tree that is a straight line 100,000 levels deep:
// countIterative(root) -> 100001; countRecursive(root) -> StackOverflowError
Exercises
Exercise 1: Recursion
Task (paraphrased): Use recursion to (a) compute 2ⁿ, (b) compute xⁿ, (c) compute 1 + 2 + … + n, (d) sum the even numbers in an integer array, (e) check whether an array is symmetric, (f) reverse a string.
The general recipe: a base case plus a step that shrinks the problem into a smaller instance of itself.
- (b) Fast exponentiation is O(log n) instead of O(n); (c) real code uses n(n+1)/2; (f) the string-concatenation version is O(n²), the two-pointer one O(n).
- The model answer in the slides calls a
pow2function that is never defined; the version below is complete.
Solution to Exercise 1: RecursionDrills
public final class RecursionDrills {
// (a) 2^n = 2 * 2^(n-1); stop at n = 0. A bit shift works too: 1L << n (n < 63)
static long powerOfTwo(int n) {
if (n < 0) throw new IllegalArgumentException("n must be >= 0");
return n == 0 ? 1 : 2 * powerOfTwo(n - 1);
}
// (b) Straightforward: x^n = x * x^(n-1) -> O(n) calls, n frames deep
static long powLinear(long x, int n) {
return n == 0 ? 1 : x * powLinear(x, n - 1);
}
// (b) Better: fast exponentiation, x^n = (x^(n/2))^2 [* x if n is odd] -> O(log n)
static long pow(long x, int n) {
if (n < 0) throw new IllegalArgumentException("n must be >= 0");
if (n == 0) return 1;
long half = pow(x, n / 2);
long sq = Math.multiplyExact(half, half); // throws ArithmeticException on overflow
return (n % 2 == 0) ? sq : Math.multiplyExact(sq, x);
}
// (c) S(n) = n + S(n-1); stop at n = 0. (In real code use n(n+1)/2, which is O(1))
static long sum(int n) {
return n <= 0 ? 0 : n + sum(n - 1);
}
// (d) Sum of even numbers from index i to the end
static long sumEven(int[] a, int i) {
if (i == a.length) return 0;
int self = (a[i] % 2 == 0) ? a[i] : 0; // a[i] % 2 == 0 also works for negatives
return self + sumEven(a, i + 1);
}
// (e) Symmetric if both ends match and the middle is symmetric too
static boolean isSymmetric(int[] a, int left, int right) {
if (left >= right) return true;
return a[left] == a[right] && isSymmetric(a, left + 1, right - 1);
}
// (f) reverse(s) = reverse(s[1..]) + s[0]: readable, but O(n^2) because each level builds a new string
static String reverseNaive(String s) {
return s.length() <= 1 ? s : reverseNaive(s.substring(1)) + s.charAt(0);
}
// (f) O(n) version: swap inside a char array with two pointers
static String reverse(String s) {
char[] c = s.toCharArray();
swap(c, 0, c.length - 1);
return new String(c);
}
private static void swap(char[] c, int l, int r) {
if (l >= r) return;
char t = c[l]; c[l] = c[r]; c[r] = t;
swap(c, l + 1, r - 1);
}
public static void main(String[] args) {
System.out.println(powerOfTwo(10)); // 1024
System.out.println(pow(3, 13)); // 1594323
System.out.println(sum(100)); // 5050
System.out.println(sumEven(new int[]{1, 2, 3, 4, -6}, 0)); // 0
System.out.println(isSymmetric(new int[]{1, 2, 3, 2, 1}, 0, 4)); // true
System.out.println(reverse("backend")); // dnekcab
}
}
What to keep in mind with recursion in Java:
More: silent long overflow and choosing recursion or a loop
Exercise 2: Alternating largest and smallest
Task (paraphrased): Given n distinct integers (n ≤ 1000), print them in the order largest, smallest, second largest, second smallest, and so on. For example [9, 7, 12, 8, 6, 5] → 12 5 9 6 8 7.
Approach: sort ascending, then walk two pointers from both ends, taking right then left until they meet. O(n log n) time because of the sort, O(n) space.
Two small bugs in the original answer: it calls sort(a) without defining it (it should be Arrays.sort(a)), and when n is even it never prints a trailing newline, which glues consecutive test outputs together on judges that run multiple test cases.
Solution to Exercise 2: MaxMinOrder
import java.io.*;
import java.util.*;
public class MaxMinOrder {
static int[] arrange(int[] input) {
int[] a = input.clone(); // don't mutate the caller's array
Arrays.sort(a);
int[] out = new int[a.length];
int lo = 0, hi = a.length - 1, k = 0;
while (lo <= hi) {
out[k++] = a[hi--];
if (lo <= hi) out[k++] = a[lo++];
}
return out;
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer st = new StreamTokenizer(in); // faster than Scanner for large input
st.nextToken();
int n = (int) st.nval;
int[] a = new int[n];
for (int i = 0; i < n; i++) { st.nextToken(); a[i] = (int) st.nval; }
StringJoiner sj = new StringJoiner(" ");
for (int v : arrange(a)) sj.add(String.valueOf(v));
System.out.println(sj);
}
}
Remember
- Can you write the recurrence for fast exponentiation, merge sort and naive Fibonacci, and derive time and stack depth?
- Can you explain why calling
pow(x, n/2)twice throws away the O(log n) advantage? - Do you know when to memoize, when to switch to tabulation, and why not to memoize with
computeIfAbsent? - Can you turn a recursive tree walk into a loop with
ArrayDeque, cycles included? - Can you explain why
Arrays.sortuses different algorithms forint[]andObject[]?
Interview questions
Junior
What is the base case of a recursive function? What happens if it’s missing or wrong?
It’s the smallest case where the function returns immediately without calling itself (say n == 0). If it’s missing or wrong, the function keeps calling itself until it throws StackOverflowError.
Every recursive step has to move closer to the base case. A step that doesn’t shrink the problem (a negative n against an n == 0 check) also recurses forever. That’s why invalid input should be rejected at the top of the function.
What is a stable sort, and when does it matter?
Stable means elements with equal keys keep their original relative order. It matters when you sort in several passes by several criteria.
Example: sort orders by time, then stable-sort by status, and within each status they stay in time order. In Java, List.sort and Arrays.sort(Object[]) use TimSort, which is stable. Arrays.sort(int[]) uses Dual-Pivot Quicksort, which isn’t, but two equal primitives are indistinguishable, so it doesn’t matter.
Mid
What is the complexity of fast exponentiation and of naive Fibonacci? Explain with recurrences.
Fast exponentiation: T(n) = T(n/2) + O(1), so O(log n) time and stack. Naive Fibonacci: T(n) = T(n−1) + T(n−2) + O(1), calls grow exponentially around 1.618ⁿ, while the stack is only O(n).
pow(x, n)makes exactly one call topow(x, n/2)plus O(1) work. Writingpow(x, n/2) * pow(x, n/2)(two calls) gives T(n) = 2T(n/2) + O(1) = O(n) and throws the advantage away.fib(30)takes about 2.7 million calls.
How do memoization and tabulation differ?
Both store subproblem results so nothing is computed twice; memoization goes top-down with recursion, tabulation goes bottom-up with a loop.
- Memoization: keep the recursive function and check the cache before computing. Easy to derive from the formula and computes only the states needed, but uses stack and can overflow.
- Tabulation: fill a table from the small cases upwards. No stack and often less memory, but you work out the evaluation order. Fibonacci shrinks to two variables, O(1) memory.
Why does Arrays.sort use different algorithms for int[] and Object[]?
Primitives don’t need stability, so it uses the fast Dual-Pivot Quicksort; objects do, so it uses TimSort.
- Dual-Pivot Quicksort: fast in practice, sorts in place, cache-friendly.
- TimSort: elements “equal” under the comparator are still different objects. TimSort is stable, O(n log n) worst case and close to O(n) on nearly sorted data, at the cost of O(n) extra memory.
- A comparator that breaks the contract (not transitive) can make TimSort throw
IllegalArgumentException: Comparison method violates its general contract.
Senior
A recursive function passes its tests but crashes in production with StackOverflowError. What do you do?
Switch to a loop with an explicit stack or queue (ArrayDeque), or change the algorithm so the depth is O(log n). Raising -Xss is only a band-aid.
Usually the recursion depth grows with the real data size: a long list, a tree degenerated into a line, cyclic data with no stop condition. Java doesn’t optimise tail calls, so a tail-recursive rewrite won’t help. Also: test with production-sized data and detect cycles with a visited set.
Useful phrases for interviews
- “Every recursive solution needs a base case and a step that makes the problem smaller.”
- “Since the JVM doesn’t do tail-call optimisation, I’d turn deep recursion into a loop with an explicit stack.”
- “Let me write the recurrence first: one call on half the input plus constant work, so it’s logarithmic.”
- “The subproblems overlap, so memoization brings this down from exponential to linear.”
- “I’d avoid computeIfAbsent for recursive memoization, because the mapping function would modify the map it’s running in.”
- “Remember the stack counts as memory: this recursion is O(n) space even though it allocates nothing.”
- “After sorting, two pointers from both ends give me the alternating order in a single pass.”
- “If the input comes from users or imports, I won’t let its depth decide my stack depth.”
Notes based on the Fundamentals of Backend course (Ronin Engineer), rewritten in my own words.