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.