Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
4
of 10 vote

sort all three arrys and take 1st element from each array
a,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

- tushar aggarwal September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 6 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)

- m@}{ September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry for asking but why we have taken abs? value

- Anonymous September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

What if the 3 arrays have a different number of elements in them? How does sorting stop you from checking every combination?

- Anonymous September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 votes

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.

- Seitz.Will September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- masterjaso September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Anonymous September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ravio September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ 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.

- Anonymous September 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- MIG September 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Victor October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Nasa October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 };
	}

}

- ttoommbb@126.com September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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);
	}

- deepjparekh September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- CT September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just one more detail. After local min take the best of 6 modified, even though not improving

- CT September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Since this approach doesn't end early and must keep searching after finding a local minimum, won't this approach simply brute force every possible combination of values?

- Anonymous September 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- ea September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just one more detail. After local min take the best of modified 6

- CT September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- ayush September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry there's a mistake in the above ans. M' stores indices of P having min diff with element in M. example, M'[0] stores index of element in P which has min diff for M[0].

- ayush September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- g September 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    	
    }

- Jack September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		
    }
}
}

- Nitin September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(N^3) is no way acceptable

- Shyam December 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Hemanth September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sourabh September 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Devesh Pratap September 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

	}
}

- charly September 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- this seems to work for me...? September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- notes... September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Also.... September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think, on the inner most loop, for M:

...
best_R = R;
break; // we can skip the rest
}

- slightly quicker... September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

cut short the loop for R, since if we find the current best solution when
R - L = x, then incrementing R will not give us a better solution.

- we can also... September 29, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nasa October 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think you should store all minimum(a,b,c) pairs having sum ==(min && equal)

Original Question: Find three numbers a, b, c from each of array A, B, C such that |a-b|, |b-c| and |c-a| are minimum

- Anonymous October 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Peter Tang October 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Carlos Roldan December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 + "].");
	}

- Jeremy Gilreath January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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].

- evi May 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- skum July 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;



}

- deepak gautam May 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 .

- s1.shubham July 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Omkar June 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Omkar June 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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...

- Omkar June 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Anonymous September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will fail in the following test case
a[]={1,10,20}
b[]={2,10,23}
c[]={3,10,24}
ans shud be 0 by picking 10,10,10

- tushar aggarwal September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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).

- crisredfi1 September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

a[] = {1, 1001}
b[] = {1, 1001}
c[] = {1001, 1001}

You'll get answer 1, 1, 1001 and correct is 1001, 1001, 1001.

- answer September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

When you do insertion in heap, it takes log n time. If n numbers have to be inserted, it is n*log n. Same as sorting.

- sarghau September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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]);
        }
     }
}

- masterjaso September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- Anonymous September 04, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More