Compute Fibonacci Numbers
Company: Plymouth Rock Assurance Corporation
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Write a function that returns the `n`th Fibonacci number.
Definitions and requirements:
- Use zero-based indexing: `fib(0) = 0`, `fib(1) = 1`.
- For `n >= 2`, `fib(n) = fib(n - 1) + fib(n - 2)`.
- The input `n` is a non-negative integer.
- Discuss the time and space complexity of your approach.
- If relevant, explain how your implementation handles large `n` values or integer overflow.
Quick Answer: This question evaluates a candidate's understanding of algorithmic problem-solving, recurrence relations, numeric computation, and performance analysis, including discussion of time and space complexity and handling of large inputs or integer overflow.
Return the nth Fibonacci number using zero-based indexing.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (0,)
Expected Output: 0
Explanation: fib(0) is 0.
Input: (1,)
Expected Output: 1
Explanation: fib(1) is 1.
Input: (10,)
Expected Output: 55
Explanation: fib(10) is 55.
Input: (30,)
Expected Output: 832040
Explanation: The iterative method handles larger n efficiently.
Hints
- Clarify edge cases before coding.
- Keep outputs deterministic when several valid answers exist.