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).
Overview: 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.
Read the full Google Data Scientist interview experience this question came from
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.
Community answers
Answer by usta
Test cases expect
586268941
for Input (50,). 586268941 is not a Fibonacci number.
Answer by usta
Correct solution:
def fib_double(n):
if n == 2:
return (1,2)
elif n == 1:
return (1,1)
elif n <= 0:
return (0,1)
else:
fn, fnp = fib_double(n // 2)
if n % 2 == 0:
return (2fnfnp - pow(fn,2), pow(fn,2) + pow(fnp,2))
return (pow(fn,2) + pow(fnp,2), 2fnfnp + pow(fnp,2))
return fib_double(n)[0]