Fibonacci Coding Challenge

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is Fibonacci Coding Challenge. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

SS&C Technologies Holdings QA automation may need to validate sequence calculations for large test inputs related to SS&C Advent Geneva processing. Given an index n and a positive modulus mod, return the nth Fibonacci number modulo mod without generating every preceding value.

The Fibonacci sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n >= 2.

Formal Specification

Implement fibonacci(n, mod):

Input: n, a non-negative integer, and mod, a positive integer.
Output: The integer F(n) % mod.
Use an algorithm that handles very large values of n efficiently. Do not construct the complete sequence from 0 through n.

Constraints

0 <= n <= 10^18
1 <= mod <= 10^9 + 7
The result must be returned as an integer
The algorithm should run in O(log n) time

Function Signature

def fibonacci(n, mod):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output