For given list of inputs, and channels find the maximum quality that would be achievable with input values distribution over the channels.
Quality is mesaured as:
sum of medians of the distributed sub lists on each channel.
Rule: each channel must have atleast one element.
Example:
Input: 1,2,3,4,5
Channels: 2
So possible combinations of configurations are:
Channel1 Channel2 median
1 2,3,4,5 1 + (3+4)/2 = 1+ 3.5 = 4.5 = 5 (rounded)
1,2 3,4,5 (1+2)/2 + 4 =1.5+4 = 5.5 =6
1,2,3 4,5 2 + (4+5)/2 = 6.5 =7
1,2,3,4 5 (2+3)/2 + 5 =2.5 + 5 = 7.5 = 8So answer is maximun Qulity achivable is '8' with configuration 1,2,3,4 on channel 1 and 5 on channel 2
Similarly for
input: 1,2,3,4,5
channels: 3
possible configurations are:
ch1 ch2 ch3 medians
1 2 3,4,5 1+2+4 = 7
1 2,3 4,5 1+2.5+4.5 = 8
1 2,3,4 5 1+3+5 = 9
1,2 3 4,5 1.5+ 3 + 4.5 = 9
1,2 3,4 5 1.5 + 3.5 + 5 = 10
1,2,3 4 5 2 + 4 + 5 = 11So maximum quality attainable is 11 with configuration 1,2,3 on channel1, 4 on channel 2 and 5 on channel 3.
Below is my recursive solution for it withour sorting (No need to do sorting).
import java.util.Arrays;
import java.util.List;
public class AmazonTest3 {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1,2,3,4,5,6,7);
System.out.println(Math.round(highestQuality(list, 4, 0, list.size()-1)));
}
public static double highestQuality(List<Integer> list, int ch, int start, int end) {
int length = end - start+1;
if(ch==1) {
return calculateMediun(list, start, end);
}
if(ch==2) {
double max = 0;
for(int i=0;i<length-1; i++) {
double med = calculateMediun(list, start, start+i) + calculateMediun(list, start+i+1, end);
if(max<med) {
max = med;
}
}
return max;
}
int i = 0;
double max = 0;
int traverseTill = (length - ch+1);
while(i<traverseTill) {
double curMedian = calculateMediun(list, start,start+i) + highestQuality(list, ch-1, start+i+1, end);
if(curMedian>max) {
max = curMedian;
}
i++;
}
return max;
}
//List input needs to be sorted or, we need to modify median calculation using QuickSelect algorithm.
private static double calculateMediunQuickSelect(List<Integer> list, int start, int end) {
int length = end - start+1;
int mid = (start + end)/2;
if(length%2==0) {
//these calls can be optimized!
return ((double)findKthLargestUsingQuickSelect(list.toArray(new Integer[list.size()]), mid)
+findKthLargestUsingQuickSelect(list.toArray(new Integer[list.size()]), mid+1))/2;
}
return findKthLargestUsingQuickSelect(list.toArray(new Integer[list.size()]), mid);
}
public static int findKthLargestUsingQuickSelect(Integer[] nums, int k) {
int low = 0;
int high = nums.length-1;
while(low<high) {
int pivote = partian(nums, low, high);
int revK = nums.length-k;
if(revK == pivote)
return nums[pivote];
if(revK<pivote) {
high = pivote - 1;
}
if(revK>pivote) {
low = pivote + 1;
}
}
return nums[low];
}
public static int partian(Integer[] nums, int low, int high) {
int pivotLoc = low;
int pivote = nums[high];
for(int i=low; i<=high; i++) {
if(nums[i]<pivote) {
int temp = nums[i];
nums[i] = nums[pivotLoc];
nums[pivotLoc] = temp;
pivotLoc++;
}
}
nums[high] = nums[pivotLoc];
nums[pivotLoc] = pivote;
return pivotLoc;
}
}**Solution With Sorting **
First Step: We sort the input.
With sorted input like 1,2,3,4,5, and channels = 2
The highest quality would be => 1,2,3,4 on channel 1 and 5 on channel 2.
So we can generalized this as =>
First (n-ch+1) elements would be on channel 1 and rest of the elements would be on seperate channel, which will give us maxium Quality.
ex: 1,2,3,4,5,6 channel = 3
then (n-ch+1) = (6-3+1) = 4 elements (1,2,3,4) on channel 1 and remaining elements (5), (6) on seperate channels.
channel 1 = > 1,2,3,4
channel 2 = > 5
channel 3 = > 6
Quality: 2.5 + 5 + 6 = 13.5 = >14
**Solution**
```
public static double highestQualityWithSorting(List<Integer> list, int ch, int start, int end) {
int length = end - start+1;
Collections.sort(list);
if(ch==1) {
return calculateMediun(list, start, end);
}
// n-ch+1 (not adding 1 because index is zero based)
int traverseTill = (length - ch);
double curMedian = calculateMediun(list, 0,traverseTill);
while(++traverseTill<length) {
curMedian+=list.get(traverseTill);
}
return curMedian;
}
private static double calculateMediun(List<Integer> list, int start, int end) {
int length = end - start+1;
int mid = (start + end)/2;
if(length%2==0) {
return ((double)list.get(mid)+list.get(mid+1))/2;
}
return list.get(mid);
}
```