April 01, 2016

Palindromic Fibonacci in python

In the process of being interviewed for a job, I had to write a simple software. It was a nice exercise, and I liked it.

A contiguous sequence of unsigned integers is considered a "Fibonacci palindrome" if two conditions hold:

1. the sequence is the same whether read backward or forward.
2. either the sequence has fewer than three elements, or every contiguous three-element sequence {a, b, c} in it satisfies at least one of these conditions: $a==c, a+b==c, or a==b+c$.

Write a python function that takes as input a non-empty sequence of unsigned integers and efficiently finds the longest Fibonacci palindrome in that sequence. If there are multiple Fibonacci palindromes of the largest length, finding any one of them is sufficient.

def find_fibonacci_palindrome(sequence)

For the given sequence of numbers (list) the return should be
(start_index, length), where start_index is the index at which the
largest Fibonacci Palindrome starts and length its length.

I liked it because I had the opportunity to write 3 different version of the same function, using 3 different coding styles.
• Imperative style (C-like solution of the problem)
I have published my solution on this page on GitHub, along with 5 pages of $\LaTeX$ documentation and an extensive (and thought) testset.