Fibonacci Number

The Spotify "Fibonacci Number" interview problem focuses on computing the nth Fibonacci number efficiently, testing recursion, memoization, dynamic programming, and math optimizations.

Problem Statement

Write a function that returns the nth Fibonacci number. The Fibonacci sequence starts with 0 and 1, where each subsequent number is the sum of the previous two: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n > 1. Solutions should avoid naive recursion's exponential time due to redundant calculations, using techniques like memoization (top-down caching), tabulation (bottom-up DP), or space-optimized iteration.[3][10]

Examples

| Input | Output | Explanation | |-------|--------|-------------| | n = 0 | 0 | Base case: F(0) = 0 [3] | | n = 1 | 1 | Base case: F(1) = 1 [3] | | n = 2 | 1 | F(2) = F(1) + F(0) = 1 + 0 = 1 [3] | | n = 3 | 2 | F(3) = F(2) + F(1) = 1 + 1 = 2 [3] | | n = 4 | 3 | F(4) = F(3) + F(2) = 2 + 1 = 3 [3] | | n = 5 | 5 | F(5) = F(4) + F(3) = 3 + 2 = 5 [1] | | n = 10 | 55 | Sequence up to 10th term [2] [10] |

Constraints

• 0 ≤ n ≤ 30 (common for 32-bit integer limits, as F(30) ≈ 832040 fits in int; larger n risks overflow).[10]
• n is an integer.
• Return type: integer (e.g., int in Java/C++, number in JS/Python).
• Time complexity expectations: O(n) with DP/memoization, not O(2^n) recursion.[4][3]
• Space complexity: O(n) for memo/table, optimizable to O(1) with variables tracking last two values.[2][3]