Fibonacci Coding Challenge | Dataford Interview Questions

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 question is Fibonacci Coding Challenge. Start with the requirements in the Question tab.

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

Problem