"Interview question of the week" from Cassidy Williams 20-Jun-2022

index.py

def prev_fibonacci_number(fibo):
    '''Given a number that could be part of the fibonacci sequence, find its predecessor in the fibonacci
    sequence or return -1 if it's not part of the sequence
    
    We really only need to keep track of the most recent two numbers we've seen in the sequence, just in case
    this needs to be used on super large numbers'''
    
    if fibo <= 0:
        return -1

    if fibo == 1:
        return 1

    first_fibo_number = 1
    second_fibo_number = 1
    while True:
        next_fibo_number = first_fibo_number + second_fibo_number
        if next_fibo_number == fibo:
            return second_fibo_number
        if next_fibo_number > fibo:
            return -1
        # we need to keep getting larger
        first_fibo_number = second_fibo_number
        second_fibo_number = next_fibo_number

assert prev_fibonacci_number(1) == 1
assert prev_fibonacci_number(0) == -1
assert prev_fibonacci_number(2) == 1
assert prev_fibonacci_number(3) == 2
assert prev_fibonacci_number(4) == -1
assert prev_fibonacci_number(1111111111) == -1
assert prev_fibonacci_number(1134903170) == 701408733 
assert prev_fibonacci_number(354224848179261915075) == 218922995834555169026
assert prev_fibonacci_number(49235814277468209595489570918088205406471236376456384909120564298267422802712916193422893933710321716261919358672578960137652220384891310734479430127573127629649805706147536) == 30429406687252699593351538566798377185959387146188807456930182333582300837496418114201395161146835096636683896770018795242809817174157327000900543689883458177726950222631993
assert prev_fibonacci_number(49235814277468209595489570918088205406471236376456384909120564298267422802712916193422893933710321716261919358672578960137652220384891310734479430127573127629649805706147537) == -1

prompt.txt

Given a Fibonacci number, give the previous Fibonacci number. If the number given is not a Fibonacci number, return -1.