D
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) = 0F(1) = 1F(n) = F(n - 1) + F(n - 2) for n >= 2nF(n)Your solution should handle the base cases correctly and avoid the exponential slowdown of naive recursion.
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.
0 <= n <= 30nth Fibonacci numbern = 0Output0WhyThe sequence starts with `F(0) = 0`.n = 7Output13WhyThe sequence is `0, 1, 1, 2, 3, 5, 8, 13`, so the 7th value is 13.n = 10Output55WhyBuilding from the recurrence gives `F(10) = 55`.0 <= n <= 30Input `n` is an integerReturn the exact nth Fibonacci numberdef fibonacci(n):
