Length of Longest Fibonacci Subsequence

Length of Longest Fibonacci Subsequence

What is this problem about?

The "Length of Longest Fibonacci Subsequence interview question" asks you to find the length of the longest subsequence in a strictly increasing array that follows the Fibonacci rule (A_i + A_j = A_k). A subsequence is derived by deleting zero or more elements from the original array. This "Length of Longest Fibonacci Subsequence coding problem" is a step up from basic sequence problems, requiring you to identify patterns within a sorted set.

Why is this asked in interviews?

This problem is commonly asked at top-tier companies like Amazon and Goldman Sachs. It tests a candidate's proficiency with the "Dynamic Programming interview pattern" and the "Hash Table interview pattern". It requires an understanding of how to define a state that captures enough information to build upon previous results—in this case, using the last two elements of a potential sequence.

Algorithmic pattern used

The solution typically involves Dynamic Programming. Since a Fibonacci sequence is determined by its last two terms, we can use a DP table dp[i][j] to store the length of the longest Fibonacci-like subsequence ending with the elements at index i and j. We use a hash map to quickly find the index of the element arr[j] - arr[i] (the required preceding term). If it exists at index k, then dp[i][j] = dp[k][i] + 1.

Example explanation

Array: [1, 2, 3, 4, 5, 6, 7, 8]

1. Consider pairs (1, 2). The next element should be 1+2=3. It exists. Current length = 3.
2. Next pair is (2, 3). The next should be 2+3=5. It exists. Current length = 4.
3. Next pair is (3, 5). The next should be 3+5=8. It exists. Current length = 5. The sequence is [1, 2, 3, 5, 8], length 5.

Common mistakes candidates make

• Missing the sequence length requirement: Forgetting that a Fibonacci sequence must have at least 3 elements.
• O(n^3) brute force: Checking every triplet without using DP or a Hash Map to speed up the lookup.
• Incorrect DP state: Trying to use a 1D DP array, which doesn't work because the next term depends on the last two terms, not just one.

Interview preparation tip

When a sequence depends on multiple previous terms, your DP state usually needs to reflect that. Practice 2D DP problems and learn how to map array values to their indices using a Hash Table for O(1) lookups.