Question

De-Shaw | OA Coding Questions and Solutions | Set - 11 | 2022

Answer 1

Problem 1: You're given two integers array each of size N (1<=N<=1e5) and an integer threshold sum(-1e5<=arr[i]<=1e5 and -1e9<=threshold sum<=1e9). Find two pairs 0 <= i < j < n such that arr1[i] + arr1[j] is less than or equal to the threshold sum and arr2[i] + arr2[j] is maximized. Find the maximum sum.
Problem 2: You're given an array of N (1<=N<=1e5) integers and you need to choose three triplet such that 0<=i<=j<=k and arr1[i] + arr2[j] * r + arr3[k] * r^2 is maximized where r lies in range [-1e2, 1e2]. Find the maximum sum.
Problem 3: You're given an array of N (1<=N<=5000) integers and an integer k (1<=k<=n). An array is called odd frequency count of elements in the array doesn't exceed k. Find the number of ways to partition the array such that each subarray is a good array. Return the answer modulo (1e9 + 7).

Answer 2

Q1 we can possibly solve by sorting, max dp table, plus two pointers.
Sort (arr1[i], arr2[i]) by arr1[i]. Then loop the sorted, create two dp tables - new indices (not original indices in arr2, new indices in the sroted) of max arr2 encountered 0 to i, and indices of 2nd max.
Then two pointers approach to find pairs sorted[l][0] + sorted[r][0] <= threshold, if dp_max[r] != l, sorted[l][1] + sorted[dp_max[r]][1] is a candiate answer. If l is the max, combine it with the the 2nd max (actually it should be the final answer I think).

3rd one is DP + Partitioning problem and is easiest one

Q2. Just loop through all values of j and find max element to left of j (call it a) and right of j (call it b). Then calculate a + arr[j]r +br^2. Take maximum