Problem
Return the n-th Fibonacci number. fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2).
Approach 1 — naive recursion (DON'T)
cpp
long long fib_naive(int n) {
return n < 2 ? n : fib_naive(n - 1) + fib_naive(n - 2);
}
Time: O(2^n) — fib(40) already takes seconds. Same subproblem solved billions of times.
Approach 2 — memoization (top-down DP)
cpp
#include <unordered_map>
long long fib_memo(int n, std::unordered_map<int, long long>& cache) {
if (n < 2) return n;
auto it = cache.find(n);
if (it != cache.end()) return it->second;
long long v = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
cache[n] = v;
return v;
}
long long fib_memo(int n) {
std::unordered_map<int, long long> cache;
return fib_memo(n, cache);
}
Time: O(n). Space: O(n) (the map + the recursion stack).
Approach 3 — iterative (best space)
cpp
long long fib_iter(int n) {
if (n < 2) return n;
long long a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
long long c = a + b;
a = b;
b = c;
}
return b;
}
Time: O(n). Space: O(1).
Approach 4 — [object Object] (compile-time)
cpp
constexpr long long fib_ct(int n) {
if (n < 2) return n;
long long a = 0, b = 1;
for (int i = 2; i <= n; ++i) { long long c = a + b; a = b; b = c; }
return b;
}
static_assert(fib_ct(20) == 6765); // computed at compile time!
Overflow warning
fib(93) > 2^63 - 1 — overflows long long. Use boost::multiprecision::cpp_int or __int128 for larger n.
What interviewers look for
- Spot the exponential blow-up of naive recursion.
- Articulate the memoisation pattern (cache + recursive call).
- Know that the iterative version uses constant space.
- Bonus: mention matrix exponentiation gives O(log n).