Fibonacci and Longest Subsequence | Dataford Interview Questions

WebMD uses ordered relevance signals to rank content returned by products such as the WebMD Symptom Checker. Implement a function that performs two independent computations: return the nth Fibonacci number and the length of the longest strictly increasing subsequence in an integer sequence.

Use the Fibonacci definition F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2). A subsequence may skip elements, but it must preserve their original order. It is strictly increasing, so equal adjacent values are not allowed.

Formal Specification

Given an integer n and a list of integers nums, return a two-element list [fib, lis_length], where fib is F(n) and lis_length is the length of the longest strictly increasing subsequence of nums.

Constraints

0 <= n <= 100000
0 <= len(nums) <= 100000
-10^9 <= nums[i] <= 10^9
The subsequence must be strictly increasing

Function Signature

def fibonacci_and_lis(n, nums):

Your question is Fibonacci and Longest Subsequence. 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

Formal Specification

Constraints

0 <= n <= 100000
0 <= len(nums) <= 100000
-10^9 <= nums[i] <= 10^9
The subsequence must be strictly increasing

Function Signature

def fibonacci_and_lis(n, nums):

Your question is Fibonacci and Longest Subsequence. 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.