Implement Fibonacci with efficiency constraints
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Write a function `fib(n)` that returns the nth Fibonacci number (0-indexed: fib(0)=0, fib(1)=1).
Requirements:
- Handle `n` up to at least 10^6.
- Discuss time and space complexity.
- If exact integers are too large for the language’s native int, explain what you would do (e.g., modulo arithmetic or big integers).
Quick Answer: This Coding & Algorithms interview prompt for Data Scientist roles evaluates algorithmic efficiency, dynamic programming principles and numeric-handling considerations by requiring computation of the nth Fibonacci number at very large input sizes; abstraction level: implementation-level algorithmic optimization and complexity analysis.
Implement `solution(n)`, which computes the 0-indexed Fibonacci number where F(0)=0 and F(1)=1. Because Fibonacci numbers become extremely large, return F(n) modulo 1,000,000,007. Your solution should be efficient enough for very large n and should not use the naive exponential recursive definition. If an exact integer version were required in a language with fixed-width integers, you would use a big integer library such as Java BigInteger, Python int, or C++ multiprecision; alternatively, modulo arithmetic as used here keeps values bounded.
Constraints
- 0 <= n <= 1,000,000,000
- Use MOD = 1,000,000,007
- Expected time complexity is O(log n)
Examples
Input: (0,)
Expected Output: 0
Explanation: This is the base case: F(0)=0.
Input: (1,)
Expected Output: 1
Explanation: This is the other base case: F(1)=1.
Hints
- The identities F(2k)=F(k)*(2*F(k+1)-F(k)) and F(2k+1)=F(k)^2+F(k+1)^2 can compute Fibonacci values by repeatedly doubling the index.
- Apply the modulo after additions and multiplications so intermediate values stay small.