Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
Apparently |a-b|+|b-c|+|c-a| is the same as 2*(max(a,b,c)-min(a,b,c)), so we are just gonna try to minimize max(a,b,c)-min(a,b,c)
First we need to iterate each of the array to find their respective max and min so to determine their range;
I split all the possibilities into two cases:
1. At least two of the arrays are disjoint, this can be determined from comparing their max and min. In this case, we only pick an array A and find the other array B, so that B is the furthest disjoint array of A, for example if A is disjoint with both B and C, such that A. max<B.min and A.max<C.min, additionally we know B.min < C.min, then we pick C; now apparently the desired combination will require C.min and A.max, which will determine the desired minimum, and we only need to pick any element b from B such that b<=C.min and b>=B.min;
2. None of the two arrays out of the three are disjoint of each other. Meaning they all have joint sections. For this case we first need to find the common joint range of all three(guaranteed to exist since none of them disjoint of each other), since the desired combination must be around this range, which will be between max(A.min, B.min, C.min) and min(A.max, B.max, C.max), I will call this range r, bounded by r.min and r.max. Second, we iterate through all three list again and discard all elements outside this range except for the element immediately next to the range, specifically for an element a of array A, we keep a
if (a<=r.max&&a>=r.min) || a==max(A[A.min - r.min] || a==min(A[r.max - A.max]))
where A[A.min - r.min] is the sub-array of A bounded by A.min and r.min. Third, now it's the algorithm proper, heap sort and merge all three lists in to list L1, keep an equal size array L2 to record from which of the three array A,B or C every element in L1 came from. Finally, iterate through L1 from the left, and for every element e encountered, calculate the difference between the max and min elements in the sub-array bounded left by e and such that contains at least one element from each of the 3 original lists. If the difference is the least of all differences found, record the difference and the sub-array.
After the iteration, we will have the min, and the three numbers will be the resulting sub-array's starting and ending element plus any element between them that's from the third array
public class MinThreeDifferences
{
public Class MinValues implements Comparable<MinValues>
{
int value;
char arrayId;
int idx;
MinValues(int v,int index, char id)
{
value=v;
idx=index;
arrayId=id;
}
public int compareTo(MinValues mv)
{
return value-mv.value;
}
}
public static MinValues[] findMinDifferences(int[] a, int [] b, int[] c) throws NullPointerException
{
if(a==null ||b==null||c==null)
{
throw new NullPointerException();
}
//Sort the three arrays from which we will be pulling our values.
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
MinValues[] minDiffThree=new MinValues[3];//Array to store 3 values with min difference across a, b, and c
//Store the minimum value from each of the three arrays (a,b,c)
minDiffThree[0]=new MinValues(a[0],0,'a');
minDiffThree[1]=new MinValues(b[0],0,'b');
minDiffThree[2]=new MinValues(c[0],0,'c');
int minDiff=Integer.MAX_VALUE();
do
{
Arrays.sort(mindDiffThree);//Sort the array of values from a,b,c
minDiff=Math.min(minDiff,minDiffThree[2].value-minDiffThree[0].value);//Find the minimum difference between the maximum and minimum value across all 3(a,b,c) arrays.If it's less then the current min difference, update minDiff.
minDiffThree[0].idx++;//Point to the next highest value in the array containing the minimum value across all 3 arrays.
int[] minArray=null;//Reference that will point to the array containing the min value.
switch(minDiffThree[0].arrayId)//Identify the array containing the minimum value element.
{
case'a':
minArray=a;
break;
case 'b':
minArray=b;
break;
case 'c':
minArray=c;
break;
case deafult:
break;
}
}while(minDiffThree[0].idx<minArray.length)//If there are no more elements left in the minimum element array, stop.
return minDiffThree;
}
//Create an array of random integers of size n
private static int[] getArray(int n)
{
if(n<=0)
{
return null;
}
Random rnd=new Random();
int[] arr=new int[n];
for(int i=0;i<arr.length;i++)
{
arr[i]=rnd.nextInt(101);
}
}
public static void main(String[] args)
{
Random rnd=new Random();
int[] a=MinThreeDifferences.getArray(rnd.nextInt(101));
int[] b=MinThreeDifferences.getArray(rnd.nextInt(101));
int[] c=MinThreeDifferences.getArray(rnd.nextInt(101));
MinValues[] m= MinThreeDifferences.findMinDifferences(a,b,c);
System.out.println(m[0].value, m[1].value,m[2].value);
}
}
//Time complexity is O(nlogn), where this is the time taken to sort the largest array of the three. Space Complexity is O(1).
For each a, number in A
- find bSmall, largest number is less equal a in B
- find bBig, smallest number is greater equal a in B
- find cSmall, largest number is less equal a in C
- find cBig, smallest number is greater equal a in C
- calculate distance and find minimum: {a, bSmall, cSmall}, {a, bSmall, cBig}, {a, bBig, cSmall}, {a, bBig, cBig}
C++, O(n^2)
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_INTEGER = 2147483646;
void compareDistance(int& a, int& b, int& c, int& minDistance, int A, int B, int C) {
int t;
t = abs(A - B) + abs(B - C) + abs(C - A);
if (t < minDistance) {
minDistance = t;
a = A;
b = B;
c = C;
}
}
void findMinDistanceInThreeArray(vector<int>& A, vector<int>& B, vector<int>& C) {
int minDistance, t;
int a, b, c;
int i, j, k;
bool foundSmallB, foundEqualB, foundBigB;
bool foundSmallC, foundEqualC, foundBigC;
sort(A.begin(), A.end());
sort(B.begin(), B.end());
sort(C.begin(), C.end());
a = b = c = 0;
minDistance = MAX_INTEGER;
j = 0;
k = 0;
for (i = 0; i < A.size(); i++) {
if (j < 0) j = 0;
if (j < B.size()) {
foundSmallB = false;
foundEqualB = false;
foundBigB = false;
while (j < B.size() - 1 && B[j] < A[i]) j++;
if (B[j] == A[i]) {
foundEqualB = true;
} else {
if (B[j] > A[i] && j - 1 >= 0) j--;
if (B[j] < A[i]) {
foundSmallB = true;
if (j + 1 < B.size() && B[j + 1] > A[i]) foundBigB = true;
} else {
foundBigB = true;
j--;
}
}
}
if (k < 0) k = 0;
if (k < C.size()) {
foundSmallC = false;
foundEqualC = false;
foundBigC = false;
while (k < C.size() - 1 && C[k] < A[i]) k++;
if (C[k] == A[i]) {
foundEqualC = true;
} else {
if (C[k] > A[i] && k - 1 >= 0) k--;
if (C[k] < A[i]) {
foundSmallC = true;
if (k + 1 < C.size() && C[k + 1] > A[i]) foundBigC = true;
} else {
foundBigC = true;
k--;
}
}
}
if (foundEqualB && foundEqualC) {
minDistance = 0;
a = A[i];
b = B[j];
c = C[k];
break;
} else if (foundEqualB) {
if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k + 1]);
} else if (foundEqualC) {
if (foundSmallB) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
if (foundBigB) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k]);
} else {
if (foundSmallB) {
if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k + 1]);
}
if (foundBigB) {
if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k]);
if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k + 1]);
}
}
}
cout << a << ", " << b << ", " << c << "\n";
}
int main(int argc, char* argv[]) {
vector<int> A, B, C;
A.push_back(1);
A.push_back(5);
A.push_back(100);
B.push_back(1);
B.push_back(45);
B.push_back(75);
C.push_back(1);
C.push_back(100);
C.push_back(200);
findMinDistanceInThreeArray(A, B, C);
return 0;
}
This is my try. Complexity is O(n*log n). Correct me, if I'm wrong.
// Solution itself: |a-b| + |b-c| + |c-a| is actually equal to max(|a-b|,|a-c|,|c-a|)*2.
// So, we must choose as closely placed set of numbers as possible.
// I walk through A and find as close values from B and C as possible.
// Solution complexity is O(sizeA*(log(sizeB)+log(sizeC)), it is O(n*log(n)) if all the sizes are roughly equal.
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <utility>
using std::vector;
struct Solution {
int sum;
int valueA;
int valueB;
int valueC;
Solution() : sum(INT_MAX) {};
Solution(int vA, int vB, int vC) : valueA(vA), valueB(vB), valueC(vC) {
sum = abs(vA - vB) + abs(vA - vC) + abs(vB - vC);
};
};
Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C);
int main()
{
// vector<vector<int> > s = { { 10,20,30 }, { 1, 2, 3 }, { 1, 1, 1 } };
vector<vector<int> > s = { { 2,2,2 },{ 1, 0, -1 },{ 3, 4, 5 } };
Solution solution = findMinSet(s[0], s[1], s[2]);
std::cout << "Sum: " << solution.sum << ", set is (" << solution.valueA << ", " << solution.valueB << ", " << solution.valueC << ")" << std::endl;
return 0;
}
// returns couple of elements of sorted array, closest to given value.
// if the exact value present, it returns pair of this value
// if all elements in array is less, than value, then return pair of maximim values
// if all elements in array is more, than value, then return pair of minimum values
// if element is not present, then return pair of closest to value element from below and closest element from above.
std::pair<int, int> findClosestPair(const vector<int> & vec, int value) {
assert(vec.size() > 0);
size_t maxIndex = vec.size() - 1;
size_t minIndex = 0;
if (value <= vec[minIndex]) return std::make_pair(vec[minIndex], vec[minIndex]);
if (value >= vec[maxIndex]) return std::make_pair(vec[maxIndex], vec[maxIndex]);
while (maxIndex - minIndex > 1) {
size_t testIndex = (maxIndex + minIndex) / 2;
int testValue = vec[testIndex];
if (testValue == value) return std::make_pair(testValue, testValue);
if (testValue < value) minIndex = testIndex;
else maxIndex = testIndex;
}
return std::make_pair(vec[minIndex], vec[maxIndex]);
}
Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C) {
assert(A.size()>0);
assert(B.size()>0);
assert(C.size()>0);
std::sort(B.begin(), B.end());
std::sort(C.begin(), C.end());
Solution s;
for (auto i : A) {
std::pair<int, int> pairB = findClosestPair(B, i);
std::pair<int, int> pairC = findClosestPair(C, i);
// possible variants: A-Bmin-Cmin, A-Bmin-Cmax, A-Bmax-Cmin, A-Bmax-Cmax
Solution s1(i, pairB.first, pairC.first);
if (s1.sum < s.sum) s = s1;
Solution s2(i, pairB.first, pairC.second);
if (s2.sum < s.sum) s = s2;
Solution s3(i, pairB.second, pairC.first);
if (s3.sum < s.sum) s = s3;
Solution s4(i, pairB.second, pairC.second);
if (s4.sum < s.sum) s = s4;
}
return s;
}
Simplify the formula f = |a-b|+|b-c|+|c-a|, we get 6 scenarios:
a>b>c: f = 2a - 2c
a>c>b: f = 2a - 2b
b>a>c: f = 2b - 2c
b>c>a: f = 2b - 2a
c>a>b: f = 2c - 2b
c>b>a: f = 2c - 2a
It seems f = max(|a-b|,|a-c|,|c-a|)*2, but you may find the maximum result in case 1:
a>b>c: f = a-b+b-c+a-c = 2a - 2c. But what if you can't find b which satisfies a>b>c, this maximum value in fact is impossible to obtain. You erroneously get a max result.
But I think you could correct your solution like this, each time you get a minimum value, check it before you use it. For example, if current minimum value comes from f = 2|a-c|, determine whether there is b satisfying a>b>c or c>b>a. If such a b doesn't exist, discard the result. Otherwise, save it.
// amazon-interview-questions
// Given three arrays A, B, C containing unsorted numbers.
// Find three numbers a, b, c from each of array A, B, C such that | a - b | +| b - c | +| c - a | is minimum.
// Solution itself: |a-b| + |b-c| + |c-a| is actually equal to max(|a-b|,|a-c|,|c-a|)*2.
// So, we must choose as closely placed set of numbers as possible.
// I walk through A and find as close values from B and C as possible.
// Solution complexity is O(n*log(n)) if all the sizes are roughly equal.
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <utility>
using std::vector;
struct Solution {
int sum;
int valueA;
int valueB;
int valueC;
Solution() : sum(INT_MAX) {};
Solution(int vA, int vB, int vC) : valueA(vA), valueB(vB), valueC(vC) {
sum = abs(vA - vB) + abs(vA - vC) + abs(vB - vC);
};
};
Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C);
int main()
{
// vector<vector<int> > s = { { 10,20,30 }, { 1, 2, 3 }, { 1, 1, 1 } };
// vector<vector<int> > s = { {1, 5, 100}, { 1,45,75 }, { 1,100,200 } };
vector<vector<int> > s = { { 2,2,2 },{ 1, 0, -1 },{ 3, 4, 5 } };
Solution solution = findMinSet(s[0], s[1], s[2]);
std::cout << "Sum: " << solution.sum << ", set is (" << solution.valueA << ", " << solution.valueB << ", " << solution.valueC << ")" << std::endl;
return 0;
}
// returns couple of elements of sorted array, closest to given value.
// if the exact value present, it returns pair of this value
// if all elements in array is less, than value, then return pair of maximim values
// if all elements in array is more, than value, then return pair of minimum values
// if element is not present, then return pair of closest to value element from below and closest element from above.
std::pair<int, int> findClosestPair(const vector<int> & vec, int value) {
assert(vec.size() > 0);
size_t maxIndex = vec.size() - 1;
size_t minIndex = 0;
if (value <= vec[minIndex]) return std::make_pair(vec[minIndex], vec[minIndex]);
if (value >= vec[maxIndex]) return std::make_pair(vec[maxIndex], vec[maxIndex]);
while (maxIndex - minIndex > 1) {
size_t testIndex = (maxIndex + minIndex) / 2;
int testValue = vec[testIndex];
if (testValue == value) return std::make_pair(testValue, testValue);
if (testValue < value) minIndex = testIndex;
else maxIndex = testIndex;
}
return std::make_pair(vec[minIndex], vec[maxIndex]);
}
Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C) {
assert(A.size()>0);
assert(B.size()>0);
assert(C.size()>0);
std::sort(B.begin(), B.end());
std::sort(C.begin(), C.end());
Solution s;
for (auto i : A) {
std::pair<int, int> pairB = findClosestPair(B, i);
std::pair<int, int> pairC = findClosestPair(C, i);
// possible variants: A-Bmin-Cmin, A-Bmin-Cmax, A-Bmax-Cmin, A-Bmax-Cmax
Solution s1(i, pairB.first, pairC.first);
if (s1.sum < s.sum) s = s1;
Solution s2(i, pairB.first, pairC.second);
if (s2.sum < s.sum) s = s2;
Solution s3(i, pairB.second, pairC.first);
if (s3.sum < s.sum) s = s3;
Solution s4(i, pairB.second, pairC.second);
if (s4.sum < s.sum) s = s4;
}
return s;
}
Step1: Sort all the three arrays
Step2: Scan the array of minimum length for each element , say ai in array A
Step3: Find the element bj in B using binary search such that | bj -ai | is minimun
Step4: Find the element ck1 in C using binary search such that | ck1 - bj | is minimum
Step5: Find the element ck2 in C using binary search such that | ck2 - ai | is minimum
Step6: temp_val = min{ |ai- bj| + |bj - ck1| +|ck1- ai| ,|ai- bj| + |bj - ck2| +|ck2- ai| }
Step7: if(temp_val < val) val=temp_val; store {a,b,c} //here {ai,bj,ck1} or {ai,bj,ck2} which gives minimum value of temp_val
Step8: Goto Step2
Step9: return{a,b,c}
Time Complexity: O(nlogn)
O(nlogn) => time to sort three array, where n is the size of largest array
O(nlogn) => for each elerment of minimum size array we are searching three times using binary search
so O(nlogn) +O(nlogn) =O(nlogn)
Space Complexity => O(1)
Here in Binary search to search any element x , we wil calculate the absolute difference of x with A[mid] ,A[mid-1] and A[mid +1] , if |x -A[mid]| == 0 than return A[mid] otherwise reduce the problem towards left or right half of the array which gives minimum difference with x, i.e if |x -A[mid-1]| < |x -A[mid +1]| move to left half. if |x -A[mid-1]| == |x -A[mid +1]| than check if x > A[mid] move to right half otherwise left half.
solution seems to be correct. But time complexity is O(n^2logn)
O(nlogn) to sort + we have to iterate each element in one array and for each element we do 3 binary searches so it is O(n^2logn)
/*Given three arrays A,B,C containing unsorted numbers.
* Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.
* */
package com.rakshith.triplet;
import java.util.Arrays;
public class triplet1 {
int aa=0;int bb=0;int cc=0;
void findTriplet(int a[],int b[],int c[]){
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
System.out.println(minVal(a,b)+minVal(b,c)+minVal(c,a));
}
int minVal(int arr1[],int arr2[]){
int i=0;
int min=Integer.MAX_VALUE;
while(i<(arr1.length)){
int j=0;
while(j<(arr2.length)){
if((Math.abs(arr1[i]-arr2[j]))<min){
min=Math.abs(arr1[i]-arr2[j]);
}
j++;
}
i++;
}
System.out.println(min);
return min;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={10,15,20};
int b[]={5,10,25};
int c[]={3,5,15};
triplet1 trip = new triplet1();
trip.findTriplet(a, b, c);
}
}
/*Given three arrays A,B,C containing unsorted numbers.
* Find three numbers a, b, c from each of array A, B, C such that |a-b|+|b-c| +|c-a| is minimum.
* */
package com.rakshith.triplet;
import java.util.Arrays;
public class triplet1 {
int aa=0;int bb=0;int cc=0;
void findTriplet(int a[],int b[],int c[]){
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
System.out.println(minVal(a,b)+minVal(b,c)+minVal(c,a));
}
int minVal(int arr1[],int arr2[]){
int i=0;
int min=Integer.MAX_VALUE;
while(i<(arr1.length)){
int j=0;
while(j<(arr2.length)){
if((Math.abs(arr1[i]-arr2[j]))<min){
min=Math.abs(arr1[i]-arr2[j]);
}
j++;
}
i++;
}
System.out.println(min);
return min;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={10,15,20};
int b[]={5,10,25};
int c[]={3,5,15};
triplet1 trip = new triplet1();
trip.findTriplet(a, b, c);
}
}
public static int[] findTripletWithMinDist(int[] arr, int[] brr, int[] crr)
{
int[] abcsum = new int[4];
int minsum = Integer.MAX_VALUE;
Arrays.sort(brr); // brr.length*O(brr.length); time
Arrays.sort(crr);
for (int i = 0; i < arr.length; i++) {
int a = arr[i];
int j = 0; int k = 0;
int diff = Integer.MAX_VALUE; int prevDiff = Integer.MAX_VALUE;
while (j < brr.length && k < crr.length) {
diff = brr[j] - crr[k];
if (diff <= prevDiff) {
if (minsum >= Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a)) {
minsum = Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a);
prevDiff = diff;
abcsum[0] = a;
abcsum[1] = brr[j];
abcsum[2] = crr[k];
}
}
if (diff > 0) {
k++;
} else {
j++;
}
}
}
abcsum[3] = minsum;
return abcsum;
}
public static int[] findTripletWithMinDist(int[] arr, int[] brr, int[] crr)
{
int[] abcsum = new int[4];
int minsum = Integer.MAX_VALUE;
Arrays.sort(brr); // brr.length*O(brr.length); time
Arrays.sort(crr);
for (int i = 0; i < arr.length; i++) {
int a = arr[i];
int j = 0; int k = 0;
int diff = Integer.MAX_VALUE; int prevDiff = Integer.MAX_VALUE;
while (j < brr.length && k < crr.length) {
diff = brr[j] - crr[k];
if (diff <= prevDiff) {
if (minsum >= Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a)) {
minsum = Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a);
prevDiff = diff;
abcsum[0] = a;
abcsum[1] = brr[j];
abcsum[2] = crr[k];
}
}
if (diff > 0) {
k++;
} else {
j++;
}
}
}
abcsum[3] = minsum;
return abcsum;
}
I have an idea based on two pointers solution as follows. Please let me know if I miss any corner case
1. Sort each array
2. make 3 pointers all start from the beginning of each array
3. calculate the |a-b| + |b-c| + |c-a| based on those 3 pointers. If the value is less than the current minimum, update the minimum and save current a, b, c as result
4. compare all three integers pointed by pointers and only advanced the pointer which points to the minimum value
5. repeat step 3 and 4 until all 3 pointers can't be moved forwarded anymore
This is a duplicate problem and refer to details here: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-find-least.html
Here is the pseduo-code
1. Combine the 3 arrays into one with data structure to indicate which array the value comes from
2. Sort this big array (of data structure) with the value from A, B and C as key
3. Assign minAbsSum, prevA, prevB and prevC as invalid (to track last A, B and C visited so far)
4. Go through each element in the big array.(Loop the big array)
4.1 If curVal is from array A, pick curVal, prevB and prevC. Go to 4.4
4.2 If curVal is from array B, pick curVal, prevA and prevC. Go to 4.4
4.3 If curVal is from array C, pick curVal, prevA and prevB. Go to 4.4
4.4 Calculate the sum of the absolute values of difference
if prevB and prevC are valid in case of 4.1
if prevA and prevC are valid in case of 4.2
if prevA and prevB are valid in case of 4.3
4.5 Update the minAbsSum if absSum < minAbsSum,
4.6 Return if minAbsSum = 0, otherwise continue
// Test
//********************************************************************************
void testCase1()
{
std::vector<int> aVec = { 9, 7, 5, 7, 4, 8, 12, 30, 50 };
std::vector<int> bVec = { 30, 5, 9, 20, 35, 70, 50, 12 };
std::vector<int> cVec = { 8, 10, 30, 21, 6, 3, 6, 10, 0 };
ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
assert(result.absSum == 0);
assert(result.val[0] == 30);
assert(result.val[1] == 30);
assert(result.val[2] == 30);
}
void testCase2()
{
std::vector<int> aVec = { 9, 7, 6, 8, 4, 5, 3, 1, 2 };
std::vector<int> bVec = { 20, 10, 19, 12, 15, 17, 14, 12 };
std::vector<int> cVec = { 30, 31, 21, 40, 25, 23, 36, 40, 50 };
ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
assert(result.absSum == 24);
assert(result.val[0] == 9);
assert(result.val[1] == 10);
assert(result.val[2] == 21);
}
void testCase3()
{
// 3 vectors has 4 and 9, this case should return 4
std::vector<int> aVec = { 9, 7, 6, 8, 4, 5, 3, 1, 2 };
std::vector<int> bVec = { 20, 4, 19, 2, 15, 17, 9, 12 };
std::vector<int> cVec = { 3, 13, 9, 40, 25, 23, 6, 4, 5 };
ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
assert(result.absSum == 0);
assert(result.val[0] == 4);
assert(result.val[1] == 4);
assert(result.val[2] == 4);
}
void testCase4()
{
// 3 vectors has two sets result
// (90, 89, 91) and (3, 4, 5)
// in this case, it should return (3, 4, 5)
std::vector<int> aVec = { 90, 3, 16, 28, 45, 35, 63, 71, 82 };
std::vector<int> bVec = { 89, 4, 19, 26, 48, 37, 69, 72, 86 };
std::vector<int> cVec = { 91, 5, 15, 29, 43, 33, 66, 74, 85 };
ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
assert(result.absSum == 4);
assert(result.val[0] == 3);
assert(result.val[1] == 4);
assert(result.val[2] == 5);
}
void testCase5()
{
std::vector<int> aVec = { 90, 83, 16, 28, 45, 35, 63, 71, 3 };
std::vector<int> bVec = { 95, 88, 19, 26, 48, 37, 69, 72, 1 };
std::vector<int> cVec = { 91, 85, 15, 29, 43, 33, 66, 74, 2 };
ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
assert(result.absSum == 4);
assert(result.val[0] == 3);
assert(result.val[1] == 1);
assert(result.val[2] == 2);
}
0) sort a, b, c
1) i,j,k = 0 to length
2) calculate X = |a[i] - b[j]|, Y = |b[j] - c[k]|, Z = |c[k] - a[i]|
3) max = maximum(X, Y, Z)
4) minimize max
- if max == X
a[i] > b[j]:
j++
else:
i++
- if max == Y
b[j] > c[k]:
k++
else:
j++
- if max == Z
c[k] > a[i]:
i++
else:
k++
public class MinimumSum {
public int[] findMinimum(int[] a, int[] b, int[] c) {
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
int i = 0, j = 0, k = 0;
long x = Math.abs(a[i] - b[j]);
long y = Math.abs(b[j] - c[k]);
long z = Math.abs(c[k] - a[i]);
long minimum = x + y + z;
int minI = i;
int minJ = j;
int minK = k;
while (minimum != 0 && i < a.length && j < b.length && k < c.length) {
// find max of x, y, z
long max = Math.max(Math.max(x, y), z);
// minimize max
if (max == x) {
if (a[i] > b[j]) {
j++;
} else {
i++;
}
} else if (max == y) {
if (b[j] > c[k]) {
k++;
} else {
j++;
}
} else { // max == z
if (c[k] > a[i]) {
i++;
} else {
k++;
}
}
if (i < a.length && j < b.length && k < c.length) {
x = Math.abs(a[i] - b[j]);
y = Math.abs(b[j] - c[k]);
z = Math.abs(c[k] - a[i]);
long current = x + y + z;
if (current < minimum) {
minimum = current;
minI = i;
minJ = j;
minK = k;
}
} else {
break; // stop searching
}
}
return new int[]{a[minI], b[minJ], c[minK]};
}
int binarySearch(int target, vector<int> & array){
int left = 0, right = array.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(array[mid] == target){
return target;
}
else if(array[mid] < target){
left = mid + 1;
}
else{
right = mid - 1;
}
}
if(right == -1){
return array[left];
}
else if(right == array.size() - 1){
return array[right];
}
else{
return abs(array[right] - target) > abs(array[left] - target) ? array[left] : array[right];
}
}
bool check(vector<int> & array, int a, int b){
if(a > b) swap(a, b);
// find the ga >= a; find the lb <= b;
// if(ga <= lb) return true;
// else return false;
int ga, lb;
int left = 0, right = array.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(array[mid] == a){
ga = a;
break;
}
else if(array[mid] < a){
left = mid + 1;
}
else{
right = mid - 1;
}
}
if(right == array.size() - 1){
return false;
}
ga = array[right];
int left = 0, right = array.size() - 1;
while(left <= right){
int mid = left + (right - left)/2;
if(array[mid] == b){
ga = a;
break;
}
else if(array[mid] < b){
left = mid + 1;
}
else{
right = mid - 1;
}
}
lb = array[left];
return ga <= lb;
}
int findMinimum(vector<int> & a, vector<int> & b, vector<int> & c){
int minSum = -1;
for(int i = 0; i < a.size(); i++){
int numb = binarySearch(a[i], b);
if(check(c, a[i], numb)){
minSum = min(minSum, 2 * abs(a[i] - numb));
}
int numc = binarySearch(a[i], c);
if(check(b, a[i], numc)){
minSum = min(minSum, 2 * abs(a[i] - numc));
}
}
for(int i = 0; i < b.size(); i++){
int numc = binarySearch(b[i], c);
if(check(a, b[i], numc){
minSum = min(minSum, s * abs(b[i] - numc));
}
}
return minSum;
}
package com.company;
import java.lang.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
int a[] = {1,5,100};
int b[] = {1,45,75};
int c[] = {1,100,200};
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
int p = a.length;
int q = b.length;
int r = c.length;
int diff = Integer.MAX_VALUE;
int i=0,j=0,k=0;
int[] arr = new int[3];
while(i<p || j<q || k<r){
int max_v = Math.max(a[i],Math.max(b[j],c[k]));
int min_v = Math.min(a[i],Math.min(b[j],c[k]));
int curr_diff = max_v - min_v;
if(curr_diff < diff){
diff = curr_diff;
arr[0] = a[i];
arr[1] = b[j];
arr[2] = c[k];
}
if(curr_diff == 0) {
break;
}
if(a[i] == min_v) i++;
else if(b[j] == min_v) j++;
else k++;
}
System.out.print(arr[0] + " " + arr[1] + " " + arr[2]);
}
}
By minimizing |a-b|+|b-c|+|c-a|, the question is asking for the minimum range of one number from each array.
First I would sort each array, then simultaneously iterate through each array, advancing the position in the array which is looking at the minimum value compared to the positioned values in the other arrays. Each iteration would set a,b,c if a minimum range is found. The iteration would stop when the minimum positioned value is at the end of an array, whereby further looking at values would only increase the range.
This should run in O(nlogn) time (from sorting), where n is the length of the longest array out of A,B, or C and O(c) space complexity.
- johnsgresham September 16, 2015Parts could be "cleaned up" if the approach was abstracted to any number of input arrays, not just three.