Fibonacci Number

The Fibonacci Number problem tests how well you can reason about recursion, performance, and optimization. It’s a great warm-up because each optimization you make exemplifies how you should approach harder dynamic programming problems.

Problem Statement

Given an integer n, return the nth Fibonacci number.

The Fibonacci sequence is defined as:

• F(0) = 0

• F(1) = 1

• F(n) = F(n - 1) + F(n - 2) for n >= 2

  
  

Assume n is a non-negative integer.

1. Clarify Requirements Before Jumping Into Code

Before touching code, let's pause and make sure we understand the expectations.

• Input: a single non-negative integer n

• Output: the nth Fibonacci number

• Base cases: n = 0 and n = 1

• Constraints: Is n small or large?

In most interviews, n can be large enough that naive recursion will fail due to time limits or stack depth. Always assume that performance matters.

2. Identify the Category of the Question

We have overlapping subproblems here, which tells us this is a classic Dynamic Programming problem.

Common patterns for this category of question include:

• Plain recursion

• Recursion with memoization (top-down DP)

• Iterative DP (bottom-up)

• Space-optimized iteration

3. Consider a Brute-Force Approach to Understand the Problem

The definition of the question actually gives us a pretty big hint to our first approach at a solution for this problem. In other words, recursion!

• If n <= 1, return n

• Otherwise, return fib(n - 1) + fib(n - 2)

This approach gives us:

• Time complexity: O(2ⁿ)

• Space complexity: O(n) due to recursion stack

It works conceptually, but it recalculates the same values over and over. That’s a red flag.

4. Brainstorm More Solutions

The brute-force version keeps recomputing fib(3), fib(4), and so on. That repetition jumps out immediately as an opportunity for optimization.

So as a first pass at improving our brute-force solution, let's try memoization.

• We'll cache the results of fib(n) the first time we compute them

• Then we can reuse cached values instead of recomputing

That drops our time complexity to O(n), but I still pay a cost for recursion overhead and stack space. Can we do better?

To answer that question, let's remember that most recursive solutions can also be implemented iteratively.

Let's visualize the sequence growing:

• Start with an array of size n

• Fill in our first two values: 0 and 1

• Then, for each iteration of the array, add the previous two values

• Move forward until we've reached n

We've managed to drop the overhead associated with recursion, but our space complexity ultimately is still O(n).

So as a further optimization, let's ask ourselves: do we need the full array of values?

In this case, the answer is no. We actually only need to know the values of n-1 and n-2. So all we really need is to track those two variables!

No array, no recursion, constant space.

That’s the cleanest solution.

Final approach recap:

• Handle base cases 0 and 1

• Use a loop for iterations 2 to n

• Track the values of n-1 and n-2 so we can calculate the current Fibonacci iteration

• Build up to n

5. Discuss Trade-Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Recursive	O(2ⁿ)	O(n)	Simple, mirrors definition	Extremely slow
Memoized recursion	O(n)	O(n)	Fast, intuitive	Extra memory, recursion stack
Iterative DP	O(n)	O(n)	Clear, efficient	Uses array
Space-optimized loop	O(n)	O(1)	Fastest, minimal memory	Slightly less obvious

6. Write Pseudocode to Structure Your Thoughts

if n <= 1:
    return n

prev = 0
curr = 1

for i from 2 to n:
    next = prev + curr
    prev = curr
    curr = next

return curr

7. Consider Edge Cases

A few things to watch for:

• n = 0

• n = 1

• Very large n (integer overflow if not specified otherwise)

For this problem, I assume results fit within a 32-bit integer unless told otherwise.

8. Write Full Code Syntax

public class FibonacciNumber {

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        int prev = 0;
        int curr = 1;

        for (int i = 2; i <= n; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }

        return curr;
    }
}

9. Test Your Code

System.out.println(fib(0)); // 0
System.out.println(fib(1)); // 1
System.out.println(fib(2)); // 1
System.out.println(fib(5)); // 5
System.out.println(fib(10)); // 55

Each test checks either a base case or a standard Fibonacci value.

10. Key Lessons to Remember for Future Questions

• Always start with the simplest correct solution, even if it’s inefficient.

• Look for overlapping subproblems. This often signals dynamic programming.

• Question whether recursion is necessary.

• If a value only depends on a fixed number of previous states, space optimization is usually possible.

• Interviewers care more about how I arrive at the solution than the final code.

Fibonacci is small, but the thinking process scales to much harder problems.

Good Luck and Happy Coding!