Question

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

Answer 1

 

Can anyone share approach to solve this problem ? I was not able to do that during the test.

 

We don't actually need binary search. Just sort and record the 2 largest elements. O(nlogn)

 

It is a 2-pointer question. Sort by index. 1 pointer went from highest A[i] and the other pointer went from the lowest A[i]. As long as the sum is not more than threshold, we advance the low pointer and record the largest 2 elements. Why not just the largest? It is because we have to take care of the fact that we can't choose an index twice, so we record the largest 2 elements. Use the largest element when the value doesn't match, the second largest element when they do match.

 

Java (Tested with bruteforce sol)

    static int solve(int[] A, int[] B, int threshold){
        int n = A.length, max = 0, ans = 0, secMax = 0;
        int[] idx = IntStream.range(0, n).boxed().sorted(Comparator.comparingInt(o -> A[o])).mapToInt(o -> o).toArray();
        for (int i = n-1, j = 0; i >= 0; i--){
            while(j < n && A[idx[i]]+A[idx[j]] <= threshold){
                if (B[idx[j]]>max){
                    secMax=max;
                    max=B[idx[j]];
                }else if (B[idx[j]]>secMax){
                    secMax=B[idx[j]];
                }
                j++;
            }
            if (max > 0 && secMax > 0){
                int val = max==B[idx[i]]?secMax:max;
                ans = Math.max(ans, val + B[idx[i]]);
            }
        }
        return ans;
    }