Longest Increasing Subsequence from Two Arrays
Updated
Problem statement
Choose an array chosen of the same length as first and second. At every index i, choose either first[i] or second[i] for chosen[i].
Return the largest possible length of a strictly increasing subsequence of chosen, over all allowed choices. A subsequence keeps index order but may skip positions.
For this exercise, assume the arrays may be empty, in which case the answer is 0. Equal values cannot both extend a strictly increasing subsequence.
Function
longestChosenSubsequence(first: int[], second: int[]) → intExamples
Example 1
first = [2,3,1]second = [1,2,1]return = 2Choose [1,2,1]. The first two values form an increasing subsequence of length 2. The last position can only contain 1, so a length-three increasing sequence is impossible.
Example 2
first = [1,3,2,1]second = [2,2,3,4]return = 4Choose [1,2,3,4]. All four positions form a strictly increasing subsequence, reaching the array-length upper bound.
Example 3
first = [1,3,2,4]second = [1,3,2,4]return = 3The choices are fixed. Skip the value 2 to obtain [1,3,4]. All four values are not increasing because 3 > 2.
Constraints
0 <= first.length <= 2000.0 <= second.length <= 2000, andfirst.length = second.length.-1000000000 <= first[i] <= 1000000000.-1000000000 <= second[i] <= 1000000000.
More Squarepoint Capital interview questions
- Evaluating Circuit ExpressionsOA · Seen Jul 2026
- Match an XOR-Adjusted SumOA · Seen Oct 2025
- Maximize Palindromic WordsOA · Seen Oct 2025
- Minimize the Sum with Ceiling HalvesOA · Seen Oct 2025
- Resolve Overlapping Price RangesOA · Seen Dec 2024
- Empty ShelfOA · Seen Sep 2024
- Suggested ProductsOA · Seen Sep 2024
- Newton Square Root to a Guaranteed TolerancePHONE SCREEN · Seen Nov 2026
- Probability of Consecutive HeadsPHONE SCREEN · Seen Nov 2026
- Three Points in a Semicircle: Monte Carlo EstimatePHONE SCREEN · Seen Nov 2026
Similar questions at other companies
- Longest Increasing Price SubsequenceOpenAI · OAOpenAI interview questions
- Minimum Cost to Attend Required CoursesVisa · OAVisa interview questions
- Fill a Time Window with SongsMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Split Array Largest SumLinkedIn · OALinkedIn interview questions
- Longest Increasing SubsequenceAtlassian · OAAtlassian interview questions
- Maximum Profit from an Increasing Price TripletOdoo · OAOdoo interview questions
- Longest Increasing Subsequence LengthApple · OAApple interview questions
- Beautiful RowNutanix · OANutanix interview questions
- Split Array to Minimize the Largest SumInfosys · OAInfosys interview questions