I was asked this problem at Goldman Sach last month, I tried various Greedy Approaches but all failed in some cases.
Problem:: Given 2 arrays A, B of size N. We need to rearrange the array B such that the order of the adjacent elements is reversed from the order of adjacent elements in A. Order means if the (i)th number is greater than or lesser than its adjacent number, so if A[i] > A[i+1] then B[i] must be less than B[i+1]. Arrays do not contain equal elements. Also, we need to maximize the absolute adjacent sum ie Sum of abs(B[i+1]-B[i]). We need to find the maximum possible value of this sum.
1<= N <= 10^5
Eg:
N = 4
A = {1,6,4,2}
B = {2,9,5,4}
Explanation :
In A the index follows this order : 0 < 1 > 2 > 3.
=> B must follow : 0 > 1 < 2 < 3 .
Some possibe B arrangements are : [9 2 4 5] , [5 2 4 9] , [4 2 5 9]. But only [9 2 4 5] , [5 2 4 9] maximise the sum ie 10 . So answer is 10.
One of my approaches:: I tried finding the peaks in array B corresponding to those peaks in A, placing peaks with the largest element present in B, and then filling the remaining places according to the adjacent element present in it in. For maximize purposes, I sorted the array B and then starting from the peaks in B to the valleys I filled largest - smallest values wherever possible.
I am trying to find how to find such B in time faster than O(n^2) or is there any other standard way to solve this without greedy ...