How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Google during technical interviews.

Implement Fibonacci with efficiency constraints

Quick 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.

Quick Overview

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.

Input: (10,)

Expected Output: 55

Explanation: The 10th Fibonacci number is 55.

Input: (50,)

Expected Output: 586268941

Explanation: F(50)=12586269025, and 12586269025 modulo 1,000,000,007 is 586268941.

Input: (100,)

Expected Output: 687995182

Explanation: F(100)=354224848179261915075, which becomes 687995182 after taking modulo 1,000,000,007.

Input: (1000000,)

Expected Output: 918091266

Explanation: This large input checks that the algorithm is logarithmic rather than linear or exponential.

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.

Last updated: Jun 22, 2026

Loading coding console...