Question

De-Shaw | SDE Summer Intern | OA Coding Questions and Solutions | Set - 6 | 2022

Answer 1

For a new statistic, span-relation, for two arrays of integers, arr1 ,and arr2 is the product of the minimum of the arr1 and the sum of the arr2. For example, the span relation of [2,4,3,5] and [1,2,3,4] is 2x(1+2+3+4) = 20.

 

Given two arrays(as list in java) arr1 and arr2 of n integers each and an integer k, choose exactly k indices i1, i2, ..., ik such that the span-relation of the sets [arr1[i1], arr1[i2], ..., arr1[ik] and arr2[i1], arr2[i2], ..., arr2[ik] is maximum.

 

Return the maximum possible span-relation.

 

Example1:
Given n=4, k=3, arr1=[2,1,3,4] and arr2=[1,3,3,2].
Output: 12
Explanation: One optimal selection of k indices is 0,2 and 3. The sets formed are [2,3,4] and [1,3,2] giving a maximum span-relation of 2x(1+3+2) = 12.

 

Example2:
Given n=8, k=4, arr1=[7,9,17,7,8,5,12,4] and arr2=[13,10,7,1,3,12,15,5].
Output: 315
Explanation: Optimal way to choose the k indices is 0,1,2 and 6 giving the sets [7,9,17,12] and [13,10,7,15] giving the maximum span-relation of 7x(13+10+7+15) = 315.

 

Example3:
Given n=5, k=1, arr1=[7,5,10,9,6] and arr2=[4,2,3,1,1].
Output: 30

 

Function Description:
Complete the function getMaxSpanRelation, which has the following parameters(s)
int arr1[n]: an array of n integers.
int arr2[n]: an array of n integers.
int k: the number of indices to choose

 

Return:
long int: the maximum possible span-relation.

 

Constraints:
1 <= n <= 10^5
1 <= k <= n
0 <= arr1[i] <= 5000
0 <= arr2[i] <= 5000

Answer 2

O(n*K) solution which gives partial result due to TLE : 

By the way can we use dynamic programming to solve this? Is this solution works?
Help me if I'm wrong.

 

Can we use other approaches to solve this problem? Please someone help me out.

 

class Solution{
    
    public long maxSpanRelation(int idx, List<Integer> arr1, long mini, List<Integer> arr2, long sum, int k, long[][] dp){
        if(idx==arr1.size()){
            if(k==0){
                return mini*sum;
            }
            
            return 0;
        }
        
        if(dp[idx][k]!=-1) return dp[idx][k];
        
        long pick = maxSpanRelation(idx+1, arr1, Math.min(mini, arr1.get(idx)), arr2, sum+arr2.get(idx), k-1, dp);
        long notPick = maxSpanRelation(idx+1, arr1, mini, arr2, sum, k, dp);
        
        return dp[idx][k] = Math.max(pick, notPick);
    }
    
    public long getMaxSpanRelation(List<Integer> arr1, List<Integer> arr2, int k){
        int n = arr1.size();
        long[][] dp = new long[n][k+1];
        for(long[] d1 : dp){
            Arrays.fill(d1, -1);
        }
        
        return maxSpanRelation(0, arr1, 5001, arr2, 0, k, dp);
    }
}

public class Main {
    public static void main(String[] args) {
        int n; // n is the number of integers that will be stored in arr1 and arr2
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>(); 
        int k; // k is the number of the same indices from both arr1 and arr2 will be chosen by the programmer 
        Solution sol = new Solution();
        sol.getMaxSpanRelation(arr1, arr2, k);
    }
}