Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Solution with merging is valid one.
Another one solution:
1. Sort 'b' and 'c'.
2. For each element in 'a' do binary search inside 'b' and 'c' (binary search will find existing element or closest one).
3. Compare min = min( abs(a[i] - b[k]) + abs(a[i] - c[j]) + abs(b[k] - c[j]), minSoFar )
time: O(N*lgN)
space: O(1)
What if the 3 arrays have a different number of elements in them? How does sorting stop you from checking every combination?
a = [1,5]; b = [5,9]; c = [1,5]
Your algorithm returns the min as 4 when it is actually 0.
The algorithm sorting b and c and searching for the closest element within to every a also fails on:
a = [3,6]; b = [1,9]; c = [5,9]
This algorithm will return the min of 8 when the answer is 6.
This solution also fails for this example:
A -3, -2, 0, 0 1 4
B -10, -8, -5, -3, -1
C 1, 5, 10, 15, 20
The answer here is 0, -1, 1 which never align in the above mentioned triplet fashion.
This solution is correct as far as i can see. And it will pass examples above. Both previous posters probably misunderstood the "triplet" scheme. On each step we change only smallest number in triplet to the next one in corresponding array.
I think this solution is correct. If you think a,b,c as three points on the number line, then it make sense.
The only problem is that, if the minimum number are all from one array, then it will move to the end of the array. So we have to deal with this special case.
@ m@}{, the algorithmic complexity is sorting O( j Log j + k Log K ) + searching O(i * (Log j + Log k) ) versus the other approach of sorting O (i Log i + j Log j + k Log K ) + searching O( i + j + k) where i = length of a, j = length of b and k = length of c. I think that approach would be hit by the no free lunch theorem.
Tushar is solving totally different problem
i.e. arrayOne = {1,1,1};
i.e arrayTwo = {2,10, 13};
i.e arrayThree = {3,20, 23};
So Tushar's answer will give 1 1 and 1 but the question says "Find three numbers a, b, c from each of array A, B, C" a,b and c from each array. So the correct answer is 1 , 2 and 3
Voting -1.
The proposed approach is based on the assumption that the question is to find the min(|a-b| + |b-c| + |a-c|).
Supposing the problem is reduced to two arrays (a,b) instead of three(a,b,c). To find the min, I think we need to sort both array a and array b, then set two indice i and j, initializing with 0.
int i = 0, j = 0;
int min = Math.abs(a[0] - b[0]);
while (i < a.length && j < b.length) {
min = Math.min(min, Math.abs(a[i] - b[j]));
if (a[i] < b[j]) {
i++;
} else {
j++;
}
}
Right now the problem grows to three arrays (a,b,c). To find the min(Math.abs(a[i]-b[j]) + Math.abs(b[j]-c[k]) + Math.abs(a[i]-c[k])), we suppose that (a[i], b[j], c[k]) is the tuple we need to find, a[i] > b[j] > c[k]. If we could find the min pair of (a[i], c[k]), as long as b[j] is between a[i] and c[k], it will not affect the Math.abs(a[i]-b[j]) + Math.abs(b[j]-c[k]) + Math.abs(a[i]-c[k]), because Math.abs(a[i]-b[j]) + Math.abs(b[j]-c[k]) == Math.abs(a[i]-c[k]), which means Math.abs(a[i]-b[j]) + Math.abs(b[j]-c[k]) + Math.abs(a[i]-c[k]) == 2 * Math.abs(a[i]-c[k]), if a[i] > b[j] > c[k]. So abstract the three arrays as two arrays, one only "store" (actually don't need to really keep them in an array) the max values of a[w], b[w] and c[w], w is index of max array, the other only "store" the min values of a[w], b[w] and c[w]. Then apply the approach on the top, which I think could work.
I think we can do this in linear time if we sort the three arrays.
Logic:
1# Sort the arrays in ascending order
2# take three pointers pointing to the first elements of the arrays
3# Calculate the value of |a-b|+|b-c|+|c-a| and put it into result
4# increment the pointer with minimum value, if the new value is less than the one calculated above, replace it
5# keep checking till we reach the end of the arrays
package gao.zone.study;
import java.util.Arrays;
public class ThreeNumFromThreeArr {
private static class Combine {
private final int[] nums;
public Combine(int a, int b, int c) {
nums = new int[] {a,b,c};
}
public int getValue() {
int biggest = nums[0];
int smallest = nums[0];
for(int i = 1; i < nums.length ; i++) {
if(nums[1]> biggest) {
biggest = nums[i];
}
if(nums[i] < smallest) {
smallest = nums[i];
}
}
return biggest-smallest <<1;
}
public int[] toArray() {
return nums;
}
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 3, 30, 5 };
int[] arr2 = { 2, 4, 6, 8, 10 };
int[] arr3 = { 1, 4, 8, 9 };
int[] rst = findThreeNumber(arr1, arr2, arr3);
// 4,4,4.
System.out.println(Arrays.toString(rst));
}
public static int[] findThreeNumber(int[] arr1, int[] arr2, int[] arr3) {
Combine combine = null;
for (int n1 : arr1) {
int[] nearest = narrow(arr2, n1);
int[] nearest2 = narrow(arr3, n1);
Combine next = findBestCombine(n1, nearest, nearest2);
combine = getBetterCombine(combine, next);
}
return combine.toArray();
}
private static Combine findBestCombine(int n1, int[] nearest, int[] nearest2) {
Combine best = new Combine(n1, nearest[0], nearest2[0]);
for (int n2 : nearest) {
for (int n3 : nearest2) {
Combine next = new Combine(n1, n2, n3);
best = getBetterCombine(best, next);
}
}
return best;
}
private static Combine getBetterCombine(Combine c1, Combine c2) {
if(c1 == null) {
return c2;
}
if(c2 == null) {
return c1;
}
if(c1.getValue() < c2.getValue()) {
return c1;
}
return c2;
}
/**
* Find nearest two value to num. One is bigger than num, one is smaller
* than num. Or one only one result if have equals to num or no
* bigger/smaller than num.
*
* @param arr
* the arr
* @param num
* the num
* @return the int[]
*/
private static int[] narrow(int[] arr, int num) {
int positiveNear = num;// invalid value
int negativeNear = num;// invalid value
for (int n : arr) {
int offset = n - num;
if (offset == 0) {
return new int[] { num };
}
if (offset > 0) {
if (positiveNear == num || positiveNear > n) {
positiveNear = n;
}
continue;
}
if (offset < 0) {
if (positiveNear == num || negativeNear < n) {
negativeNear = n;
}
}
}
if (positiveNear == num) {
return new int[] { negativeNear };
}
if (negativeNear == num) {
return new int[] { positiveNear };
}
return new int[] { positiveNear, negativeNear };
}
}
This works when all the three arrays are of same length.
public static void FindThreeMinSum(int a[],int b[],int c[])
{
int temp1,temp2,temp3=0;
int minAB=Math.abs(a[0]-b[0]);
int minBC=Math.abs(b[0]-c[0]);
int minCA=Math.abs(c[0]-a[0]);
for(int k=0;k<a.length;k++)
{
for(int l=0;l<a.length;l++)
{
temp1=Math.abs(a[k]-b[l]);
temp2=Math.abs(b[k]-c[l]);
temp3=Math.abs(c[k]-a[l]);
if((temp1<=minAB)&&(temp2<=minBC)&&(temp3<=minCA))
{
minAB=temp1;
minBC=temp2;
minCA=temp3;
}
}
}
System.out.println(" a-b "+minAB+" b-c "+minBC+" c-a "+minCA);
}
Can be done without sorting which is most expensive component.
Keep Hash set of local minimum triplets and track minimum of them as final answer.
Start at first element of each. At each step, consider up to 6 possibilities of changing triplet to better: one of previous / next on one of the arrays. Make most improving change. If there is none, that is a local min, put in hash set.
Now, if one of the up to 6 changes is in hash set, keep moving in the same direction till it is not. (For instance, instead of previous 2 before or more)
Consider arrays as cyclical.
Just one more detail. After local min take the best of 6 modified, even though not improving
I structured the problem as follow -- calculate the min(A[0], B, C), .., min(A[n], B, C) & find the min in this set.
To calculate min(A[i], B, C), I first create a matrix of distance between B and C. Then I add the Distance(A[i], B) and Distance(A[i], C) to the matrix. The smallest number in the matrix is the min (A[i], B, C)
Apparently I am not allow to give you a github link but you can find it under edithau/findMinDistance
{
static int[] findMinDistElements(int[] A, int[] B, int[] C ) {
// initialize a matrix of distance ( |b - c| )
int[][] distMatrixBC = constructDistMatrix(B, C);
// track the min indicies and min distance
int minDistIndices[] = new int[3];
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < A.length; i++) { // O(sizeof(A)
int[] distAiB = calcDist(A[i], B); // O(sizeof(B))
int[][] distMatrix = updateDist(distMatrixBC, distAiB); // O(sizeof(B) x sizeof(C))
int[] distAiC = calcDist(A[i], C); // O(sizeof(C))
distMatrix = updateDist(distMatrix, distAiC); // O(sizeof(B) x sizeof(C))
minDist = findMinDist(distMatrix, minDistIndices, minDist, i); //O(sizeof(B) x sizeof(C))
if (minDist == 0) {
break;
}
}
int[] retVal = {A[minDistIndices[0]], B[minDistIndices[1]], C[minDistIndices[2]]};
return retVal;
}
}
hey
suppose you have 3 arrays with sizes m,n,p such that m<n<p. you can do it with O(m*p) complexity and O(m) space complexity. first take the m and p sized arrays say they are M and P. for every element in M find element in P such that their difference in min and store the index of that element in P in another array called M'.. now you have another M sized array with all min values. now for every element in M find value in N such that their difference is min and also get the diff with element in P using indices in M' array.
We need to find some definition of what is the meaning of minimum. "... |a-b|, |b-c| and |c-a| are minimum"
If we try to sum up (a-b) + (b-c) + (c-a), the answer should be 0 according to algebra.
a-b = d1
b-c = d2
c-a = d3
Should we just pick the maximum number between the three, minimum, or pick the middle one for comparison ?
By minimizing |a-b| and |b-c|, |c-a| will implicitly be minimized. O(n) running time, and O(1) space...
static int findMin(int[] nums){
int min=nums[0];
for(int iter=1;iter<nums.length;iter++){
if(nums[iter]<min){
min=nums[iter];
}
}
return min;
}
static int findMax(int[] nums){
int max=nums[0];
for(int iter=1;iter<nums.length;iter++){
if(nums[iter]>max){
max=nums[iter];
}
}
return max;
}
static int[] minimize(int A[], int B[], int C[]){
int aMin=findMin(A),
bMin=findMin(B),
cMin=findMin(C);
int aMax=findMax(A),
bMax=findMax(B),
cMax=findMax(C);
int[] result=new int[3];
int sum1 = Math.abs(cMin-bMin)+Math.abs(aMin-bMin);
int sum2 = Math.abs(cMax-bMax)+Math.abs(aMax-bMax);
if(sum1<sum2){
result[0]=aMin;
result[1]=bMin;
result[2]=cMin;
}
else{
result[0]=aMax;
result[1]=bMax;
result[2]=cMax;
}
return result;
}
This works just fine although complexity is a bit high for this one.
package algorithms.code;
public class AmazoneIQ {
int[] a={-3, -2, 0, 0, 1, 4};
int[] b={-10, -8, -5, -3, -1};
int[] c={ 1, 5, 10, 15, 20};
int flag=0;
int min=0;
int[] r={0,0,0};
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
AmazoneIQ aiq=new AmazoneIQ();
aiq.min(aiq.a,aiq.b,aiq.c);
//aiq.min(aiq.b,aiq.c,aiq.a);
//aiq.min(aiq.c,aiq.b,aiq.a);
aiq.display();
}
public void min(int[] a,int[] b,int[] c){
for(int i=0;i<a.length;i++)
for(int j=0;j<b.length;j++)
for(int k=0;k<c.length;k++)
minval(a[i],b[j],c[k]);
}
public void display(){
System.out.println("min value "+min);
System.out.println("min value a b c "+r[0]+" "+r[1]+" "+r[2]);
}
public void minval(int a,int b,int c){
int temp=Math.abs(a-b)+Math.abs(b-c)+Math.abs(c-a);
if(flag==0)
{min=temp;
r[0]=a;
r[1]=b;
r[2]=c;
flag++;
}
if(min>temp){
min=temp;
r[0]=a;
r[1]=b;
r[2]=c;
}
}
}
First sort all arrays then folowing code would give the required output
#include<iostream>
#include<stdio.h>
using namespace std;
int abs(int a,int b)
{
if(a>b)
{
return a-b;
}
else
{
return b-a;
}
}
void checkArr(int *p,int *q,int m,int n)
{
int i=0,j=0,elea=p[0],eleb=q[0];
int diffab=abs(p[0],q[0]);
int ldiffab=0;
while(i<m && j<n)
{
ldiffab=abs(p[i],q[j]);
if(ldiffab<diffab)
{
diffab=ldiffab;
elea=p[i];
eleb=q[j];
}
if(p[i]<q[j])
{
i++;
}
else
{
j++;
}
}
cout<<elea<<" "<<eleb<<endl;
}
int main()
{
int a[]={1,4,9,10};
int b[]={21,22,23,24};
int c[]={7,10,16,25};
checkArr(a,b,4,4);
checkArr(b,c,4,4);
checkArr(c,a,4,4);
return 1;
}
Find a and b such that we get min|a-b| in O(n^2) by using brute force method. Now we need a c in such a manner that |b-c| and |c-a| are minimum. For this to happen we need a value c as close as possible to (a+b)/2 . We can find this c value using Binary search on C. Hence a possibe solution would be in O(n^2logn)
#include<iostream>
#include<iomanip>
using namespace std;
int main() {
// finding minimum number in array 1 //
const int MAX = 5;
int arr_1[MAX];
cout << "Enter First Array : " << endl;
for (int count_1 = 0; count_1 < MAX; ++count_1) {
cout << "\tEnter Number : ";
cin >> arr_1[count_1];
}
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX ; j++) {
while (arr_1[i] < arr_1[j]) {
int temp;
temp = arr_1[i];
arr_1[i] = arr_1[j];
arr_1[j] = temp;
}
}
}
// array 2 //
int arr_2[MAX];
cout << "\nEnter Second Array : " << endl ;
for (int count_1 = 0; count_1 < MAX; ++count_1) {
cout << "\tEnter Number : ";
cin >> arr_2[count_1];
}
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
while (arr_2[i] < arr_2[j]) {
int temp;
temp = arr_2[i];
arr_2[i] = arr_2[j];
arr_2[j] = temp;
}
}
}
// array 3 //
cout << "\nEnter Third Array : " << endl ;
int arr_3[MAX];
for (int count_1 = 0; count_1 < MAX; ++count_1) {
cout << "\tEnter Number : ";
cin >> arr_3[count_1];
}
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
while (arr_3[i] < arr_3[j]) {
int temp;
temp = arr_3[i];
arr_3[i] = arr_3[j];
arr_3[j] = temp;
}
}
}
int sub_1, sub_2, sub_3, res;
sub_1 = (arr_1[0] > arr_2[0]) ? arr_1[0] - arr_2[0] : arr_2[0] - arr_1[0];
sub_2 = (arr_2[0] > arr_3[0]) ? arr_2[0] - arr_3[0] : arr_3[0] - arr_2[0];
sub_3 = (arr_3[0] > arr_1[0]) ? arr_3[0] - arr_1[0] : arr_1[0] - arr_3[0];
cout << "\n|a-b| " << sub_1;
cout << "\n|b-c| " << sub_2;
cout << "\n|c-a| " << sub_3;
res = sub_1 + sub_2 + sub_3;
cout << "\n\n|a-b|+|b-c|+|c-a| = " << res << endl;
cout << "\n\n\n" << setw(70) << "H.P." ;
cout << endl;
system("pause");
return 0;
}
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
public class FindCommon {
private static double getErr(int a, int b, int c)
{
double error = Math.abs(a - b);
error += Math.abs(b - c);
error += Math.abs(a - c);
return error;
}
public static void getMinErrorTriplets(List<Integer> list1, List<Integer> list2, List<Integer> list3)
{
if (list1 == null || list2 == null || list3 == null)
{
throw new IllegalArgumentException("list cannot be null");
}
int l1 = list1.size();
int l2 = list2.size();
int l3 = list3.size();
if (l1 == 0 || l2 == 0 || l3 == 0)
{
throw new IllegalStateException("length of list cannot be zero");
}
// sort the list
Collections.sort(list1);
Collections.sort(list2);
Collections.sort(list3);
int i, j, k;
i = j = k = 0;
// Index to store minimum triplets
int minIndex1 = -1;
int minIndex2 = -1;
int minIndex3 = -1;
double minError = Double.POSITIVE_INFINITY;
while (i < l1 && j < l2 && k < l3)
{
int x = list1.get(i);
int y = list2.get(j);
int z = list3.get(k);
double error = getErr(x, y, z);
if (error < minError)
{
minError = error;
minIndex1 = i;
minIndex2 = j;
minIndex3 = k;
// if error is zero break
if (error == 0)
break;
}
int minof3 = getMinofThree(x, y, z);
// reduce the error by incresing index of min error index
if (minof3 == x)
{
i++;
}
else if (minof3 == y)
{
j++;
}
else
{
k++;
}
}
System.out.println(list1.get(minIndex1)+" "+list2.get(minIndex2)+" "+list3.get(minIndex3));
}
private static int getMinofThree(int a, int b, int c)
{
return Math.min(Math.min(a, b), c);
}
public static void main (String[] args)
{
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
List<Integer> list3 = new ArrayList<>();
int [] arr1 = {1,5};
int [] arr2 = { 5, 9};
int [] arr3 = {1, 5};
for (Integer x : arr1)
{
list1.add(x);
}
for (Integer x : arr2)
{
list2.add(x);
}
for (Integer x : arr3)
{
list3.add(x);
}
printCommon(list1, list2, list3);
getMinErrorTriplets(list1,list2,list3);
}
}
First merge & sort all three lists into one sorted list, named 'pts'; but keep a marker of what was an item's original list.
As long as the left most and right most items belong to different original lists, and there exists an item from the 3rd list in-between them, then it is a potential solution.
struct Point
{
short ID; // A=0x1, B=0x02 or C=0x04, to indicate which original list
int x; // value
}
void get_min(vector<Point>& pts)
{
int len = pts.size();
int min_dist = MAX_INT;
int best_L;
int best_M;
int best_R;
int L = 0;
int M = 1;
int R = 2;
for (int L = 0; L < len-2; L++)
{
for (R = 2; R < len; R++)
{
if (pts[L].ID == pts[R].ID) // skip to next
continue;
for (M = L+1; M < R; M++)
{
if ((pts[L].ID | pts[M].ID | pts[R].ID) != 0x07) // skip to next
continue;
int dist = pts[R].x - pts[L].x;
if (dist < min_dist)
{
min_dist = dist; // just keeping track of best solution seen so far
best_L = L;
best_M = M;
best_R = R;
}
}
}
}
// print results
cout << "min_dist is " << min_dist << endl;
cout << "L is " << best_L << " " << pts[best_L] << endl;
cout << "M is " << best_M << " " << pts[best_M] << endl;
cout << "R is " << best_R << " " << pts[best_R] << endl;
}
L is the left most index
R is the right most index
M is a middle index in-between, L < M < R
remember that R - L = (R - M) + (M - L), so it doesn't really matter what M is, just that pts[L], pts[M] and pts[R] all belong to different arrays. The best solutions will minimize R - L.
Uses twice the space since all three lists are merged into one. We all know the sort would be O(nlogn).
get_min() is O(n^3) but it skips over all the non-valid candidates, only does a siple compute and check for valid candidates.
I think, on the inner most loop, for M:
...
best_R = R;
break; // we can skip the rest
}
I think we can do this in linear time if we sort the three arrays.
Logic:
1# Sort the arrays in ascending order
2# take three pointers pointing to the first elements of the arrays
3# Calculate the value of |a-b|+|b-c|+|c-a| and put it into result
4# increment the pointer with minimum value, if the new value is less than the one calculated above, replace it
5# keep checking till we reach the end of the arrays
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
The whole article including code and test find here: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-find-least.html
#include <map>
#include <vector>
#include <cassert>
#include <cmath>
struct ResultTuple{
int val[3]; // the combination of (a, b, c)
size_t absSum;
};
// Array A, B and C are mapped into CombinedArrayMap
// the value has type of "char" to indicate which array the key
// comes from.
typedef std::multimap<int, char> CombinedArrayMap;
typedef CombinedArrayMap::const_iterator CAMIterator;
void UpdateResult(CAMIterator& abc1,
CAMIterator& abc2,
CAMIterator& abc3,
size_t absSum,
ResultTuple& result)
{
result.absSum = absSum;
result.val[abc1->second - 'A'] = abc1->first;
result.val[abc2->second - 'A'] = abc2->first;
result.val[abc3->second - 'A'] = abc3->first;
}
void CalculateAndUpdateAbsSum(CAMIterator& itEnd,
CAMIterator& prev1,
CAMIterator& prev2,
CAMIterator& curVal,
ResultTuple& result)
{
if (prev1 == itEnd || prev2 == itEnd || curVal == itEnd) {
return;
}
// calculate the sum of the absolute values of difference
// 2*(max(a, b, c) - min(a, b, c))
size_t absSum = (prev1->first < prev2->first) ?
(curVal->first - prev1->first) << 1 :
(curVal->first - prev2->first) << 1;
if (absSum < result.absSum) {
UpdateResult(prev1, prev2, curVal, absSum, result);
}
}
// Find ck in Optimization 2 in Section 2
void FindNextNotXandY(CAMIterator& itEnd,
const char x,
const char y,
CAMIterator& notXYIter)
{
for (; notXYIter != itEnd; ++notXYIter) {
if (notXYIter->second != x &&
notXYIter->second != y) {
break;
}
}
}
// Find bj in Optimization 2 in Section 2
void FindNextNotX(CAMIterator& itEnd,
const char x,
CAMIterator& notXIter)
{
for (; notXIter != itEnd; ++notXIter) {
if (notXIter->second != x) {
break;
}
}
}
// Step 4 in psedo-code
void CalculateAndUpdateAbsSum(CAMIterator& itEnd,
CAMIterator& prevA,
CAMIterator& prevB,
CAMIterator& prevC,
CAMIterator& curABC,
ResultTuple& result)
{
switch (curABC->second){
case 'A':
CalculateAndUpdateAbsSum(itEnd, prevB, prevC, curABC, result);
break;
case 'B':
CalculateAndUpdateAbsSum(itEnd, prevA, prevC, curABC, result);
break;
case 'C':
CalculateAndUpdateAbsSum(itEnd, prevA, prevB, curABC, result);
break;
default:
assert(false);
}
}
// Optimization 2 in Section 2
void FindLastTwoCombinationsAndUpdate(CAMIterator& itEnd,
CAMIterator& prev1,
CAMIterator& prev2,
CAMIterator& curIter,
ResultTuple& result)
{
CAMIterator notXIter = curIter;
FindNextNotX(itEnd, curIter->second, notXIter);
if (notXIter != itEnd) {
if (prev1 != itEnd && prev1->second != notXIter->second) {
CalculateAndUpdateAbsSum(itEnd, prev1, curIter, notXIter, result);
}
if (prev2 != itEnd && prev2->second != notXIter->second) {
CalculateAndUpdateAbsSum(itEnd, prev2, curIter, notXIter, result);
}
CAMIterator notXYIter = notXIter;
FindNextNotXandY(itEnd, curIter->second,
notXIter->second, notXYIter);
CalculateAndUpdateAbsSum(itEnd, curIter, notXIter, notXYIter, result);
}
}
ResultTuple CalculateLeastAbsSum(const std::vector<int>& aVec,
const std::vector<int>& bVec,
const std::vector<int>& cVec)
{
CombinedArrayMap valueVecMap;
for (auto val : aVec) {
valueVecMap.insert(std::make_pair(val, 'A'));
}
for (auto val : bVec) {
valueVecMap.insert(std::make_pair(val, 'B'));
}
for (auto val : cVec) {
valueVecMap.insert(std::make_pair(val, 'C'));
}
CAMIterator itStart = valueVecMap.begin();
CAMIterator itEnd = valueVecMap.end();
CAMIterator prevA = itEnd;
CAMIterator prevB = itEnd;
CAMIterator prevC = itEnd;
char prevType = 0;
size_t SizeOfA = aVec.size();
size_t SizeOfB = bVec.size();
size_t SizeOfC = cVec.size();
size_t visitedA = 0;
size_t visitedB = 0;
size_t visitedC = 0;
ResultTuple result = { { INT_MAX, INT_MAX, INT_MAX }, SIZE_MAX }; // SIZE_MAX?
for (CAMIterator curIter = itStart; curIter != itEnd; ++curIter) {
// Optimization 1 in Section 2
if (prevType != curIter->second) {
CalculateAndUpdateAbsSum(itEnd, prevA, prevB, prevC, curIter, result);
// Optimization 3 in Section 2
if (result.absSum == 0) {
return result;
}
}
if (curIter->second == 'A') {
prevA = curIter;
if (++visitedA == SizeOfA) {
// Optimization 2 in Section 2
FindLastTwoCombinationsAndUpdate(itEnd, prevB, prevC,
curIter, result);
break;
}
}
else if (curIter->second == 'B') {
prevB = curIter;
if (++visitedB == SizeOfB) {
// Optimization 2 in Section 2
FindLastTwoCombinationsAndUpdate(itEnd, prevA, prevC,
curIter, result);
break;
}
}
else if (curIter->second == 'C') {
prevC = curIter;
if (++visitedC == SizeOfC) {
// Optimization 2 in Section 2
FindLastTwoCombinationsAndUpdate(itEnd, prevA, prevB,
curIter, result);
break;
}
}
else {
assert(false);
}
prevType = curIter->second;
}
return result;
}
Implementation in C++ of solution given previously. Just a couple of enhancements:
- Algorithm valid for n sets, example for 3
- Sorted the biggest 2 (or n-1) sets, the shortest one is the one I will iterate.
So 2 sorts, 1 iteration doing binary searchs in both other vectors
tushar aggarwal on September 04, 2014 | Flag Reply
3
of 5 votes
Solution with merging is valid one.
Another one solution:
1. Sort 'b' and 'c'.
2. For each element in 'a' do binary search inside 'b' and 'c' (binary search will find existing element or closest one).
3. Compare min = min( abs(a[i] - b[k]) + abs(a[i] - c[j]) + abs(b[k] - c[j]), minSoFar )
time: O(N*lgN)
space: O(1)"
const int MAX_VECTORS = 3;
int totalDistance(std::vector<int> ai_vector[MAX_VECTORS], int* ai_indexes)
{
int distance = 0;
for (int i = 0; i < MAX_VECTORS; i++)
for (int j = i + 1; j < MAX_VECTORS; j++)
distance += std::abs(ai_vector[i][ai_indexes[i]] - ai_vector[j][ai_indexes[j]]);
return distance;
}
std::array<int, MAX_VECTORS> getNVectorMinDistance(std::vector<int> ai_vector[MAX_VECTORS])
{
int size[MAX_VECTORS];
int index[MAX_VECTORS];
int minSize = std::numeric_limits<int>::max();
int minVectorIndex;
for (int i = 0; i < MAX_VECTORS; i++)
{
size[i] = ai_vector[i].size();
if (size[i] < minSize)
{
minSize = ai_vector[i].size();
minVectorIndex = i;
}
}
// Sort all but minimum set...
for (int i = 0; i < MAX_VECTORS; i++)
if (i != minVectorIndex)
std::sort(ai_vector[i].begin(), ai_vector[i].end());
// Find shortest pair in a,b
int minDistance = std::numeric_limits<int>::max();
std::array<int, MAX_VECTORS> ret;
for (int i = 0; i < size[minVectorIndex]; ++i)
{
index[minVectorIndex] = i;
for (int j = 0; j < MAX_VECTORS; ++j)
{
if (j != minVectorIndex)
{
// Find the ones close to it
int closestOne,
minDistance = std::numeric_limits<int>::max();
// >=
auto found = std::lower_bound(ai_vector[j].begin(), ai_vector[j].end(), ai_vector[minVectorIndex][index[minVectorIndex]]);
if (found != ai_vector[j].end())
{
// Bigger or equal,
if (std::abs(*found - ai_vector[minVectorIndex][index[minVectorIndex]]) < minDistance)
{
// Local min...
minDistance = std::abs(*found - ai_vector[minVectorIndex][index[minVectorIndex]]);
}
if (minDistance > 0)
{
// Try previous
if (found != ai_vector[j].begin())
{
// There is a previous one!, let's try
if (std::abs(*(found - 1) - ai_vector[minVectorIndex][index[minVectorIndex]]) < minDistance)
{
--found;
// Local min...
minDistance = std::abs(*found - ai_vector[minVectorIndex][index[minVectorIndex]]);
}
}
}
}
else
{
found = ai_vector[j].end() - 1; // No bigger or equal, so the closest lower oneis tha last element
// Lower
if (std::abs(*found - ai_vector[minVectorIndex][index[minVectorIndex]]) < minDistance)
{
// Local min...
minDistance = std::abs(*found - ai_vector[minVectorIndex][index[minVectorIndex]]);
}
}
index[j] = (found - ai_vector[j].begin());
}
}
int total;
if ((total = totalDistance(ai_vector, index)) < minDistance)
{
// Local min...
minDistance = total;
for (int k = 0; k < MAX_VECTORS; k++)
ret[k] = ai_vector[k][index[k]];
}
}
return std::move(ret);
}
This problem is analogous to saying "take three numbers, |a-b|, |b-c| and |c-a|, and treat these values as the lengths of each side of a triangle. Obtain the smallest sum of these three values, which is analogous to making a triangle from their lengths with the smallest possible perimeter." The key is to remember that you cannot evaluate any single value separately from the other two, since its two variables must be the same in the whole calculation. Nor can you simply sort the arrays and check each triplet. For instance, take the following two arrays:
// 0 4 28 9345345
// 9345346 2430572039857230495723054
// 18 9345347 230974987423879438095730245872430582305823045
Not only are they different sizes, which would cause such an algorithm to fail, but if they were the same sizes, you still would not arrive at the correct answer, which is A[3] (9345345) B[0] (9345346) and C[1] (9345347) giving you final values of 1, 1, 1. Save yourself complexity and concern, and do not sort the arrays. It is irrelevant.
public static void closestAbs(int[] a, int[] b, int[] c) {
int bestSum = Math.abs(a[0] - b[0]) + Math.abs(b[0] - c[0]) + Math.abs(c[0] - a[0]);
int tempSum;
int aNum = 0;
int bNum = 0;
int cNum = 0;
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < b.length; j++) {
for (int k = 1; k < c.length; k++) {
tempSum = Math.abs(a[i] - b[j]) + Math.abs(b[j] - c[k]) + Math.abs(c[k] - a[i]);
if (tempSum < bestSum) {
bestSum = tempSum;
aNum = i;
bNum = j;
cNum = k;
}
}
}
}
System.out
.println("Maximum distance of " + bestSum + " for a[" + aNum + "], b[" + bNum + "], c[" + cNum + "].");
}
One solution, as others already stated, is sorting all three and then use three pointers.
Assuming array A has M elements, array B has N elements, C has K elements. So above solution has time complexity O(MlogM + NlogN + KlogK)
I came up with another solution, this solution is efficient only when the elements in A, B, C are within a small range, like [0, 1000].
This solution works like this: we define a map<int, tuple<bool, bool, bool> >. tuple<bool, bool, bool> is to record one value's appearance in the three arrays. eg. map[89] = <1, 0, 1> means 89 appears in A, C, but not in B.
Then go through A, B, C to fill the map.
Last step, use two index p, q, to form a window, go through keys from 0-1000, find the smallest window range [p, q], which contains at least one appearance of A, B and C.
Time complexity, O(M + N + K + 1000), where "1000" is the range of values [0, 1000].
#include<iostream>
#include<limits>
using namespace std;
int absl(int a, int b)
{
return a>b?(a-b):(b-a);
}
void getMin(int a, int b, int c, int& inc)
{
int minV = a<b?a:b;
minV = c>minV?minV:c;
if(minV == a) inc = 1;
else if(minV == b) inc = 2;
else inc = 3;
}
void function(int arr[], int alen, int brr[], int blen, int crr[], int clen, int& a, int& b, int& c)
{
int i=0, j=0, k=0, inc=0, minV, ans = INT_MAX, prev;
while(i<=alen || j<=blen || k<=clen)
{
inc = 0;
prev = ans;
ans = min(ans, absl(arr[i], brr[j]) + absl(crr[k], brr[j]) + absl(arr[i], crr[k]));
if(prev!=ans)
{
a = arr[i];
b = brr[j];
c = crr[k];
}
if(i==alen && j == blen && k == clen) break;
else if(i==alen && c==alen) inc = 2;
else if(j==blen && k==clen) inc = 1;
else if(i==alen && j==blen) inc = 3;
else getMin(arr[i], brr[j], crr[k], inc);
if(inc == 1) i++;
else if(inc == 2) j++;
else if(inc ==3) k++;
}
}
int main()
{
int arr[] = {2, 3, 4, 6, 7, 9};
int brr[] = {0, 1, 5, 7, 8, 14};
int crr[] = {11, 12, 13, 14, 17, 23};
int alen = sizeof(arr)/sizeof(*arr);
int blen = sizeof(brr)/sizeof(*brr);
int clen = sizeof(crr)/sizeof(*crr);
int a = 0, b = 0, c = 0;
function(arr, alen, brr, blen, crr, clen, a, b, c);
cout<<" a = "<<a<<" b = "<<b<<" c = "<<c<<endl;
system("PAUSE");
return 0;
}
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| and |c-a| are minimum
=============================approach=================================
consider this problem as a merging problem ,
sort all the 3 array
now suppose we need to form a single sorted array from the given 3 array , for that in each step we pick a number from the any of the 3 array( smallest and not used ) and add this element to our array
now one main observation is that best answer will be the closest 3 number from 3 different array which are in the new array ( this will only give the best answer )
so each time we insert a new number in the array
suppose we pick it from 1ts array than store it in the variable last_from_first array
suppose we pick it from 2nd array store it in the variable last_from _second_array
suppose we pick it from 2nd array store it in the variable last_from _third_array
now after each insertion we check answer from these 3 variables ..
note -> calculate answer only all three variable must have initialized at least once ( means at least one elements picked from each array )
=================================code====================
#include<bits/stdc++.h>
using namespace std;
int arr[100],brr[100],crr[100];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>arr[i];
for(int i=0;i<n;i++) cin>>brr[i];
for(int i=0;i<n;i++) cin>>crr[i];
int ans=INT_MAX;
int last_from_first=-1,last_from_second=-1,last_from_third=-1;
int p1=0,p2=0,p3=0;
for(int i=0;i<3*n;i++)
{
if(p1<n && (arr[p1]<brr[p2] || p2==n) && (arr[p1]<crr[p3] ||p3==n))
{
last_from_first=arr[p1];
p1++;
}
else if(p2<n && (brr[p2]<arr[p1] || p1==n) && (brr[p2]<crr[p3] || p3==n))
{
last_from_second=brr[p2];
p2++;
}
else
{
last_from_third=crr[p3];
p3++;
}
if(last_from_first!=-1 && last_from_second!=-1 && last_from_third!=-1)
{
int temp=abs(last_from_first-last_from_second)+abs(last_from_first-last_from_third)+
abs(last_from_third-last_from_second);
ans=min(temp,ans);
}
// cout<<last_from_first<<" "<<last_from_second<<" "<<last_from_third<<endl;
}
cout<<ans<<endl;
}
Let the numbers be a , b , c from A , B , C .
Then let's sort them and lets denote them by x1 < x2 < x3.
Then ,
Our function is 2 * (x3-x1) which is nothing but range of the three elements.
The question can be re stated as find the minimum range such that there exists an element from each array. This can be solved using a heap .
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main ()
{
// Example 1
//int a[] = { 1, 5 };
//int b[] = { 5, 9 };
//int c[] = { 1, 5 };
// Example 2; No restrictions on array length equality, but must contain at least one element each.
int a[] = { -3, -2, 0, 0, 1, 4 };
int b[] = { -10, -8, -5, -3, -1 };
int c[] = { 1, 5, 10, 15, 20 };
// Get array sizes;
int aSize = (sizeof(a) / sizeof(int));
int bSize = (sizeof(b) / sizeof(int));
int cSize = (sizeof(c) / sizeof(int));
// Calculate mean value of array b
int bm = 0;
for_each(b, b + bSize, [&bm](int bb) {
bm += bb;
});
bm /= bSize;
// Calculate closeness of each element in array a and array c to mean value of array b (bm)
map<int, int> aClosest, bClosest, cClosest;
int i = 0;
for_each(a, a + aSize, [&a, &bm, &i, &aClosest](int aa) {
aClosest[abs(aa - bm)] = i;
++i;
});
i = 0;
for_each(c, c + cSize, [&c, &bm, &i, &cClosest](int cc) {
cClosest[abs(cc - bm)] = i;
++i;
});
int ai = 0, bi = 0, ci = 0;
// Simply lookup for element at minimal distant to bm
ai = min_element(aClosest.begin(), aClosest.end())->second;
ci = min_element(cClosest.begin(), cClosest.end())->second;
int acm = (ai + ci) / 2;
i = 0;
// Calculate closeness of each element in array b to its mean value (or to closest element in array a/b)
for_each(b, b + bSize, [&bClosest, &acm, &i](int bb) {
bClosest[abs(acm - bb)] = i;
++i;
});
// Locate closest element in array b
bi = min_element(bClosest.begin(), bClosest.end())->second;
// we have required ai, bi and ci values
return 0;
}
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main ()
{
// Example 1
//int a[] = { 1, 5 };
//int b[] = { 5, 9 };
//int c[] = { 1, 5 };
// Example 2; No restrictions on array length equality, but must contain at least one element each.
int a[] = { -3, -2, 0, 0, 1, 4 };
int b[] = { -10, -8, -5, -3, -1 };
int c[] = { 1, 5, 10, 15, 20 };
// Get array sizes;
int aSize = (sizeof(a) / sizeof(int));
int bSize = (sizeof(b) / sizeof(int));
int cSize = (sizeof(c) / sizeof(int));
// Calculate mean value of array b
int bm = 0;
for_each(b, b + bSize, [&bm](int bb) {
bm += bb;
});
bm /= bSize;
// Calculate closeness of each element in array a and array c to mean value of array b (bm)
map<int, int> aClosest, bClosest, cClosest;
int i = 0;
for_each(a, a + aSize, [&a, &bm, &i, &aClosest](int aa) {
aClosest[abs(aa - bm)] = i;
++i;
});
i = 0;
for_each(c, c + cSize, [&c, &bm, &i, &cClosest](int cc) {
cClosest[abs(cc - bm)] = i;
++i;
});
int ai = 0, bi = 0, ci = 0;
// Simply lookup for element at minimal distant to bm
ai = min_element(aClosest.begin(), aClosest.end())->second;
ci = min_element(cClosest.begin(), cClosest.end())->second;
int acm = (ai + ci) / 2;
i = 0;
// Calculate closeness of each element in array b to its mean value (or to closest element in array a/b)
for_each(b, b + bSize, [&bClosest, &acm, &i](int bb) {
bClosest[abs(acm - bb)] = i;
++i;
});
// Locate closest element in array b
bi = min_element(bClosest.begin(), bClosest.end())->second;
// we have required ai, bi and ci values
return 0;
}
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main ()
{
// Example 1
//int a[] = { 1, 5 };
//int b[] = { 5, 9 };
//int c[] = { 1, 5 };
// Example 2; No restrictions on array length equality, but must contain at least one element each.
int a[] = { -3, -2, 0, 0, 1, 4 };
int b[] = { -10, -8, -5, -3, -1 };
int c[] = { 1, 5, 10, 15, 20 };
// Get array sizes;
int aSize = (sizeof(a) / sizeof(int));
int bSize = (sizeof(b) / sizeof(int));
int cSize = (sizeof(c) / sizeof(int));
// Calculate mean value of array b
int bm = 0;
for_each(b, b + bSize, [&bm](int bb) {
bm += bb;
});
bm /= bSize;
// Calculate closeness of each element in array a and array c to mean value of array b (bm)
map<int, int> aClosest, bClosest, cClosest;
int i = 0;
for_each(a, a + aSize, [&a, &bm, &i, &aClosest](int aa) {
aClosest[abs(aa - bm)] = i;
++i;
});
i = 0;
for_each(c, c + cSize, [&c, &bm, &i, &cClosest](int cc) {
cClosest[abs(cc - bm)] = i;
++i;
});
int ai = 0, bi = 0, ci = 0;
// Simply lookup for element at minimal distant to bm
ai = min_element(aClosest.begin(), aClosest.end())->second;
ci = min_element(cClosest.begin(), cClosest.end())->second;
int acm = (ai + ci) / 2;
i = 0;
// Calculate closeness of each element in array b to its mean value (or to closest element in array a/b)
for_each(b, b + bSize, [&bClosest, &acm, &i](int bb) {
bClosest[abs(acm - bb)] = i;
++i;
});
// Locate closest element in array b
bi = min_element(bClosest.begin(), bClosest.end())->second;
// we have required ai, bi and ci values
return 0;
}
Feedbacks please? Any scope to optimize? I would love to hear improvements...
I think its more starightforward than that. Why cant we simply pick A(min, max), B(min, max), C(min, max) and then get abs of (A(min, max) - B(min, max)? Likewise for C....or is there something that I am missing
to my understanding, basically we need to pick the min number from each array to get the min combination. we really don't need to sort them. we could use a heap structure with minimum being the root node. heap structure gives us a better complexity since we dont need to sort the full array. once we have 3 heaps, pick the root node and we will get our best combination. finding the minimum will be o(1) and creating the heap will be o(n).
a[] = {1, 1001}
b[] = {1, 1001}
c[] = {1001, 1001}
You'll get answer 1, 1, 1001 and correct is 1001, 1001, 1001.
For this problem, the first, second, and third values are all interconnected. Any solution that doesn't consider them all at the time is bound to leave room for invalid use cases. A valid brute force solution is located below. The space requirement is O(1) as it only requires minimal storage variables and not copy/sort. The run time is a sad O(n^3) for the triple for loop. That makes me think there should be a better solution, but such an algorithm defies me at this time.
Note that this algorithm will actually allow for arrays that contain positive and negative integer values (as well as floating point with some modification to the data types) as well as arrays of variable length.
Here is my coded solution:
import java.util.*;
public class PickThree{
public static int[] pick(int[] a, int[] b, int[] c){
int[] result = {-1,-1,-1};
int d1 = Integer.MAX_VALUE;
int d2 = Integer.MAX_VALUE;
int d3 = Integer.MAX_VALUE;
int counter = Integer.MAX_VALUE;
for(int i = 0; i < a.length; i++){
for(int j = 0; j < b.length; j++){
for(int k = 0; k < c.length; k++){
d1 = Math.abs(a[i] - b[j]);
d2 = Math.abs(b[j] - c[k]);
d3 = Math.abs(c[k] - a[i]);
if(d1 + d2 + d3 < counter){
counter = d1+ d2 + d3;
result[0] = a[i];
result[1] = b[j];
result[2] = c[k];
}
}
}
}
return result;
}
public static void main(String []args){
int[] a = {-3,-2,0,1,4};
int[] b = {-10,-8,-5,-3,-1};
int[] c = {1,5,10,15,20};
int[] f = pick(a,b,c);
for(int i = 0; i < f.length; i++){
System.out.println(f[i]);
}
}
}
public int[] array(int[] a, int[] b,int[] c)
{
int min_sum=a[0]+b[0]+c[0];
int[] result=new int[3];
{
for(int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
for(int k=0;k<c.length;k++)
{
int temp=Maths.abs(a[i],b[j])+ Maths.abs(c[k],b[j])+ Maths.abs(a[i],b[k]);
if(temp>min_sum)
{
continue;
}else
{
min_sum=temp;
result[0]=a[i];
result[1]=b[j];
result[2]=c[k];
}
}
}
}
}
return result;
}
sort all three arrys and take 1st element from each array
- tushar aggarwal September 04, 2014a,b,c calculate min ( |a-b|+ |b-c| +c-a| ,ans)
then take next element from min(a,b,c) and then again repeat above step
time -O(nlogn) +O(n)
just think of this as sorting and then merging all 3 arrays and calculating |a-b|+ |b-c| +c-a| for each consecutive triplet..
u ll have the correct ans