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.