Problem

On a Glassdoor engineering screen, you may be asked to implement a basic sequence generator efficiently. Write a function that returns 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

Formal Specification

• Input: An integer n
• Output: An integer representing F(n)

Your solution should handle the base cases correctly and avoid the exponential slowdown of naive recursion.

Examples

Example 1

Input: n = 0
Output: 0

Explanation: By definition, the 0th Fibonacci number is 0.

Example 2

Input: n = 7
Output: 13

Explanation: The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, so F(7) = 13.

Example 3

Input: n = 10
Output: 55

Explanation: F(10) = 55 after building the sequence iteratively from the two previous values.

Constraints

• 0 <= n <= 30
• Return the exact integer value of the nth Fibonacci number
• Prefer an iterative or memoized solution over naive recursion