Longest Fibonacci-Like Subsequence
Updated
Problem statement
You are given a strictly increasing array nums of positive integers. A subsequence keeps some of the values in their original order; values in between may be skipped.
A subsequence x[1], x[2], ..., x[k] is Fibonacci-like if it has at least three values (k >= 3) and every value from the third on is the sum of the two values just before it: x[i] = x[i-1] + x[i-2].
Return the length of the longest Fibonacci-like subsequence of nums, or 0 if there is none.
Function
longestFibonacciLike(nums: int[]) → intExamples
Example 1
nums = [2,4,5,6,9,10,15,24,39]return = 5Pick 6, 9, 15, 24, 39: each value is the sum of the two before it (6 + 9 = 15, 9 + 15 = 24, 15 + 24 = 39). No longer such subsequence exists, so the answer is 5.
Example 2
nums = [1,5,20,100]return = 0No value is the sum of two smaller values in the array (1 + 5 = 6, 1 + 20 = 21, 5 + 20 = 25 are all missing), so there is no subsequence of length 3 or more. Answer: 0.
Example 3
nums = [3,4,7,11]return = 4The whole array works: 3 + 4 = 7 and 4 + 7 = 11. Answer: 4.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 10^9numsis strictly increasing
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Predicate Expression Tree EvaluatorMongoDB · PHONE SCREENMongoDB interview questions
- Word BreakBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Longest Common Contiguous Browser HistoryRoblox · PHONE SCREENRoblox interview questions
- Longest Common URL History RunDatadog · PHONE SCREENDatadog interview questions
- Count Ordered Combination Sums with Negative ValuesPinterest · PHONE SCREENPinterest interview questions
- Find Max Length of SubsequenceGoogle · PHONE SCREENGoogle interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Points by Deleting ElementsIBM · OAIBM interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
Interview reports that mention this question
Adobe interview experiences
- Adobe Web, QA, DevOps, ML Roles: 13 Experiences (Part 3 of 3)
- Adobe Interviews, Level Unknown: 38 Experiences (Part 1 of 3)
- Adobe New Grad MTS Interview Questions: 7 Experiences
- Adobe ML/Research Intern Interviews: 12 Experiences (Part 4 of 4)
- Adobe Product Intern Interviews: 15 Experiences (Part 3 of 4)