Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

By minimizing |a-b|+|b-c|+|c-a|, the question is asking for the minimum range of one number from each array.

First I would sort each array, then simultaneously iterate through each array, advancing the position in the array which is looking at the minimum value compared to the positioned values in the other arrays. Each iteration would set a,b,c if a minimum range is found. The iteration would stop when the minimum positioned value is at the end of an array, whereby further looking at values would only increase the range.

public int[] findMinRange(int[] A, int[] B, int[] C) {
	if(A == null || B == null || C== null || A.length < 1 || B.length < 1 || C.length < 1)
		return null;
	
	Arrays.sort(A);
	Arrays.sort(B);
	Arrays.sort(C);

	int minRange = Integer.MAX_VALUE;
	int[3] result;
	int a, b, c, aPos = bPos = cPos = 0;
	int min , max;

	while(true)
	{
		a = A[aPos];
		b = B[bPos];
		c = C[cPos];

		min = Math.min(a, Math.min(b, c));
		max = Math.max(a, Math.max(b, c));
		if(max-min < minRange) {
			minRange = max-min;
			result = {a, b, c};
		}
		
		// increase position at minimum value, break if at the end of the array
		if(a <= b && a<= c) {
			if(aPos == A.length -1) {
				break;
			} else {
				aPos++;
			}
		} else if (b <= a && b <= c) {
			if(bPos == B.length -1) {
				break;
			} else {
				bPos++;
			}
		} else if (c <= a && c <= b) {
			if(cPos == C.length -1) {
				break;
			} else {
				cPos++;
			}
		} else {
			break;
		}
	}

	return result;
}

This should run in O(nlogn) time (from sorting), where n is the length of the longest array out of A,B, or C and O(c) space complexity.

Parts could be "cleaned up" if the approach was abstracted to any number of input arrays, not just three.

- johnsgresham September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Fails for a simple case {1,5,100},{1,45,75},{1,100,200}

- Abhi September 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution failed when we array have negative value

- Dhioyt October 30, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Apparently |a-b|+|b-c|+|c-a| is the same as 2*(max(a,b,c)-min(a,b,c)), so we are just gonna try to minimize max(a,b,c)-min(a,b,c)
First we need to iterate each of the array to find their respective max and min so to determine their range;
I split all the possibilities into two cases:
1. At least two of the arrays are disjoint, this can be determined from comparing their max and min. In this case, we only pick an array A and find the other array B, so that B is the furthest disjoint array of A, for example if A is disjoint with both B and C, such that A. max<B.min and A.max<C.min, additionally we know B.min < C.min, then we pick C; now apparently the desired combination will require C.min and A.max, which will determine the desired minimum, and we only need to pick any element b from B such that b<=C.min and b>=B.min;
2. None of the two arrays out of the three are disjoint of each other. Meaning they all have joint sections. For this case we first need to find the common joint range of all three(guaranteed to exist since none of them disjoint of each other), since the desired combination must be around this range, which will be between max(A.min, B.min, C.min) and min(A.max, B.max, C.max), I will call this range r, bounded by r.min and r.max. Second, we iterate through all three list again and discard all elements outside this range except for the element immediately next to the range, specifically for an element a of array A, we keep a

if (a<=r.max&&a>=r.min) || a==max(A[A.min - r.min] || a==min(A[r.max - A.max]))

where A[A.min - r.min] is the sub-array of A bounded by A.min and r.min. Third, now it's the algorithm proper, heap sort and merge all three lists in to list L1, keep an equal size array L2 to record from which of the three array A,B or C every element in L1 came from. Finally, iterate through L1 from the left, and for every element e encountered, calculate the difference between the max and min elements in the sub-array bounded left by e and such that contains at least one element from each of the 3 original lists. If the difference is the least of all differences found, record the difference and the sub-array.
After the iteration, we will have the min, and the three numbers will be the resulting sub-array's starting and ending element plus any element between them that's from the third array

- zFaust September 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinThreeDifferences
{
	public Class MinValues implements Comparable<MinValues>
	{
		int value;
		char arrayId;
		int idx;
		
		MinValues(int v,int index, char id)
		{
			value=v;
			idx=index;
			arrayId=id;
		}
		public int compareTo(MinValues mv)
		{
			return value-mv.value;
		}
	}



	public static MinValues[] findMinDifferences(int[] a,  int [] b, int[] c) throws NullPointerException
	{
		if(a==null ||b==null||c==null)
		{
			throw new NullPointerException();
		}
		//Sort the three arrays from which we will be pulling our values.
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		
		MinValues[] minDiffThree=new MinValues[3];//Array to store 3 values with min difference across a, b, and c
		
		//Store the minimum value from each of the three arrays (a,b,c)
		minDiffThree[0]=new MinValues(a[0],0,'a');
		minDiffThree[1]=new MinValues(b[0],0,'b');
		minDiffThree[2]=new MinValues(c[0],0,'c');
		int minDiff=Integer.MAX_VALUE();
		do
		{
			Arrays.sort(mindDiffThree);//Sort the array of values from a,b,c
			minDiff=Math.min(minDiff,minDiffThree[2].value-minDiffThree[0].value);//Find the minimum difference between the maximum and minimum value across all 3(a,b,c) arrays.If it's less then the current min difference, update minDiff.
			minDiffThree[0].idx++;//Point to the next highest value in the array containing the minimum value across all 3 arrays.
			int[] minArray=null;//Reference that will point to the array containing the min value.
			switch(minDiffThree[0].arrayId)//Identify the array containing the minimum value element.
			{
				case'a':
					minArray=a;
					break;
				case 'b':
					minArray=b;
					break;
				case 'c':
					minArray=c;
					break;
				case deafult:
					break;
				
			}
			
			
			
			
			
		}while(minDiffThree[0].idx<minArray.length)//If there are no more elements left in the minimum element array, stop.
		
		return minDiffThree;
	}

	//Create an array of random integers of size n
	private static int[] getArray(int n)
	{
		if(n<=0)
		{
			return null;
		}
		Random rnd=new Random();
		int[] arr=new int[n];
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=rnd.nextInt(101);
		}
	}
	
	public static void main(String[] args)
	{
		Random rnd=new Random();
		int[] a=MinThreeDifferences.getArray(rnd.nextInt(101));
		int[] b=MinThreeDifferences.getArray(rnd.nextInt(101));
		int[] c=MinThreeDifferences.getArray(rnd.nextInt(101));
		
		MinValues[] m= MinThreeDifferences.findMinDifferences(a,b,c);
		System.out.println(m[0].value, m[1].value,m[2].value);
		
	}
	
}

//Time complexity is O(nlogn), where this is the time taken to sort the largest array of the three. Space Complexity is O(1).

- divm01986 September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code fails for the following input
int[] a = new int[]{10, 15, 20};
int[] b = new int[]{5, 10, 25};
int[] c = new int[]{3, 5, 15};
it prints 3,5,10
Expected result is 10, 5, 5

- jvm September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

For each a, number in A
- find bSmall, largest number is less equal a in B
- find bBig, smallest number is greater equal a in B
- find cSmall, largest number is less equal a in C
- find cBig, smallest number is greater equal a in C
- calculate distance and find minimum: {a, bSmall, cSmall}, {a, bSmall, cBig}, {a, bBig, cSmall}, {a, bBig, cBig}

C++, O(n^2)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

const int MAX_INTEGER = 2147483646;

void compareDistance(int& a, int& b, int& c, int& minDistance, int A, int B, int C) {
	int t;

	t = abs(A - B) + abs(B - C) + abs(C - A);
	if (t < minDistance) {
		minDistance = t;
		a = A;
		b = B;
		c = C;
	}
}

void findMinDistanceInThreeArray(vector<int>& A, vector<int>& B, vector<int>& C) {
	int minDistance, t;
	int a, b, c;
	int i, j, k;
	bool foundSmallB, foundEqualB, foundBigB;
	bool foundSmallC, foundEqualC, foundBigC;

	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	sort(C.begin(), C.end());

	a = b = c = 0;
	minDistance = MAX_INTEGER;
	j = 0;
	k = 0;
	for (i = 0; i < A.size(); i++) {
		if (j < 0) j = 0;
		if (j < B.size()) {
			foundSmallB = false;
			foundEqualB = false;
			foundBigB = false;

			while (j < B.size() - 1 && B[j] < A[i]) j++;

			if (B[j] == A[i]) {
				foundEqualB = true;
			} else {
				if (B[j] > A[i] && j - 1 >= 0) j--;
				if (B[j] < A[i]) {
					foundSmallB = true;
					if (j + 1 < B.size() && B[j + 1] > A[i]) foundBigB = true;
				} else {
					foundBigB = true;
					j--;
				}
			}
		}

		if (k < 0) k = 0;
		if (k < C.size()) {
			foundSmallC = false;
			foundEqualC = false;
			foundBigC = false;

			while (k < C.size() - 1 && C[k] < A[i]) k++;

			if (C[k] == A[i]) {
				foundEqualC = true;
			} else {
				if (C[k] > A[i] && k - 1 >= 0) k--;
				if (C[k] < A[i]) {
					foundSmallC = true;
					if (k + 1 < C.size() && C[k + 1] > A[i]) foundBigC = true;
				} else {
					foundBigC = true;
					k--;
				}
			}
		}

		if (foundEqualB && foundEqualC) {
			minDistance = 0;
			a = A[i];
			b = B[j];
			c = C[k];
			break;
		} else if (foundEqualB) {
			if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
			if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k + 1]);
		} else if (foundEqualC) {
			if (foundSmallB) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
			if (foundBigB) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k]);
		} else {
			if (foundSmallB) {
				if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k]);
				if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j], C[k + 1]);
			}
			if (foundBigB) {
				if (foundSmallC) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k]);
				if (foundBigC) compareDistance(a, b, c, minDistance, A[i], B[j + 1], C[k + 1]);
			}
		}
	}

	cout << a << ", " << b << ", " << c << "\n";
}

int main(int argc, char* argv[]) {
	vector<int> A, B, C;

	A.push_back(1);
	A.push_back(5);
	A.push_back(100);

	B.push_back(1);
	B.push_back(45);
	B.push_back(75);

	C.push_back(1);
	C.push_back(100);
	C.push_back(200);

	findMinDistanceInThreeArray(A, B, C);

	return 0;
}

- kyduke September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my try. Complexity is O(n*log n). Correct me, if I'm wrong.

// Solution itself: |a-b| + |b-c| + |c-a| is actually equal to max(|a-b|,|a-c|,|c-a|)*2. 
// So, we must choose as closely placed set of numbers as possible.
// I walk through A and find as close values from B and C as possible.
// Solution complexity is O(sizeA*(log(sizeB)+log(sizeC)), it is O(n*log(n)) if all the sizes are roughly equal.

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <utility>

using std::vector;

struct Solution {
	int sum;
	int valueA;
	int valueB;
	int valueC;

	Solution() : sum(INT_MAX) {};

	Solution(int vA, int vB, int vC) : valueA(vA), valueB(vB), valueC(vC) {
		sum = abs(vA - vB) + abs(vA - vC) + abs(vB - vC);
	};
};

Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C);

int main()
{
	// vector<vector<int> > s = { { 10,20,30 }, { 1, 2, 3 }, { 1, 1, 1 } };
	vector<vector<int> > s = { { 2,2,2 },{ 1, 0, -1 },{ 3, 4, 5 } };

	Solution solution = findMinSet(s[0], s[1], s[2]);
	std::cout << "Sum: " << solution.sum << ", set is (" << solution.valueA << ", " << solution.valueB << ", " << solution.valueC << ")" << std::endl;

	return 0;
}

// returns couple of elements of sorted array, closest to given value.
// if the exact value present, it returns pair of this value
// if all elements in array is less, than value, then return pair of maximim values
// if all elements in array is more, than value, then return pair of minimum values
// if element is not present, then return pair of closest to value element from below and closest element from above.
std::pair<int, int> findClosestPair(const vector<int> & vec, int value) {
	assert(vec.size() > 0);
	size_t maxIndex = vec.size() - 1;
	size_t minIndex = 0;

	if (value <= vec[minIndex]) return std::make_pair(vec[minIndex], vec[minIndex]);
	if (value >= vec[maxIndex]) return std::make_pair(vec[maxIndex], vec[maxIndex]);

	while (maxIndex - minIndex > 1) {
		size_t testIndex = (maxIndex + minIndex) / 2;
		int testValue = vec[testIndex];
		if (testValue == value) return std::make_pair(testValue, testValue);
		if (testValue < value) minIndex = testIndex;
		else maxIndex = testIndex;
	}

	return std::make_pair(vec[minIndex], vec[maxIndex]);
}


Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C) {
	assert(A.size()>0);
	assert(B.size()>0);
	assert(C.size()>0);

	std::sort(B.begin(), B.end());
	std::sort(C.begin(), C.end());

	Solution s;

	for (auto i : A) {
		std::pair<int, int> pairB = findClosestPair(B, i);
		std::pair<int, int> pairC = findClosestPair(C, i);
		// possible variants: A-Bmin-Cmin, A-Bmin-Cmax, A-Bmax-Cmin, A-Bmax-Cmax
		Solution s1(i, pairB.first, pairC.first);
		if (s1.sum < s.sum) s = s1;
		Solution s2(i, pairB.first, pairC.second);
		if (s2.sum < s.sum) s = s2;
		Solution s3(i, pairB.second, pairC.first);
		if (s3.sum < s.sum) s = s3;
		Solution s4(i, pairB.second, pairC.second);
		if (s4.sum < s.sum) s = s4;
	}

	return s;
}

- Maxim September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Simplify the formula f = |a-b|+|b-c|+|c-a|, we get 6 scenarios:

a>b>c: f = 2a - 2c
a>c>b: f = 2a - 2b
b>a>c: f = 2b - 2c
b>c>a: f = 2b - 2a
c>a>b: f = 2c - 2b
c>b>a: f = 2c - 2a

It seems f = max(|a-b|,|a-c|,|c-a|)*2, but you may find the maximum result in case 1:
a>b>c: f = a-b+b-c+a-c = 2a - 2c. But what if you can't find b which satisfies a>b>c, this maximum value in fact is impossible to obtain. You erroneously get a max result.

- PoWerOnOff November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But I think you could correct your solution like this, each time you get a minimum value, check it before you use it. For example, if current minimum value comes from f = 2|a-c|, determine whether there is b satisfying a>b>c or c>b>a. If such a b doesn't exist, discard the result. Otherwise, save it.

- PoWerOnOff November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

// amazon-interview-questions
// Given three arrays A, B, C containing unsorted numbers.
// Find three numbers a, b, c from each of array A, B, C such that | a - b | +| b - c | +| c - a |  is minimum.


// Solution itself: |a-b| + |b-c| + |c-a| is actually equal to max(|a-b|,|a-c|,|c-a|)*2. 
// So, we must choose as closely placed set of numbers as possible.
// I walk through A and find as close values from B and C as possible.
// Solution complexity is O(n*log(n)) if all the sizes are roughly equal.

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <utility>

using std::vector;

struct Solution {
	int sum;
	int valueA;
	int valueB;
	int valueC;

	Solution() : sum(INT_MAX) {};

	Solution(int vA, int vB, int vC) : valueA(vA), valueB(vB), valueC(vC) {
		sum = abs(vA - vB) + abs(vA - vC) + abs(vB - vC);
	};
};

Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C);

int main()
{
	// vector<vector<int> > s = { { 10,20,30 }, { 1, 2, 3 }, { 1, 1, 1 } };
	// vector<vector<int> > s = { {1, 5, 100}, { 1,45,75 }, { 1,100,200 } };
	vector<vector<int> > s = { { 2,2,2 },{ 1, 0, -1 },{ 3, 4, 5 } };

	Solution solution = findMinSet(s[0], s[1], s[2]);
	std::cout << "Sum: " << solution.sum << ", set is (" << solution.valueA << ", " << solution.valueB << ", " << solution.valueC << ")" << std::endl;

	return 0;
}

// returns couple of elements of sorted array, closest to given value.
// if the exact value present, it returns pair of this value
// if all elements in array is less, than value, then return pair of maximim values
// if all elements in array is more, than value, then return pair of minimum values
// if element is not present, then return pair of closest to value element from below and closest element from above.
std::pair<int, int> findClosestPair(const vector<int> & vec, int value) {
	assert(vec.size() > 0);
	size_t maxIndex = vec.size() - 1;
	size_t minIndex = 0;

	if (value <= vec[minIndex]) return std::make_pair(vec[minIndex], vec[minIndex]);
	if (value >= vec[maxIndex]) return std::make_pair(vec[maxIndex], vec[maxIndex]);

	while (maxIndex - minIndex > 1) {
		size_t testIndex = (maxIndex + minIndex) / 2;
		int testValue = vec[testIndex];
		if (testValue == value) return std::make_pair(testValue, testValue);
		if (testValue < value) minIndex = testIndex;
		else maxIndex = testIndex;
	}

	return std::make_pair(vec[minIndex], vec[maxIndex]);
}


Solution findMinSet(vector<int> & A, vector<int> & B, vector<int> & C) {
	assert(A.size()>0);
	assert(B.size()>0);
	assert(C.size()>0);

	std::sort(B.begin(), B.end());
	std::sort(C.begin(), C.end());

	Solution s;

	for (auto i : A) {
		std::pair<int, int> pairB = findClosestPair(B, i);
		std::pair<int, int> pairC = findClosestPair(C, i);
		// possible variants: A-Bmin-Cmin, A-Bmin-Cmax, A-Bmax-Cmin, A-Bmax-Cmax
		Solution s1(i, pairB.first, pairC.first);
		if (s1.sum < s.sum) s = s1;
		Solution s2(i, pairB.first, pairC.second);
		if (s2.sum < s.sum) s = s2;
		Solution s3(i, pairB.second, pairC.first);
		if (s3.sum < s.sum) s = s3;
		Solution s4(i, pairB.second, pairC.second);
		if (s4.sum < s.sum) s = s4;
	}

	return s;
}

- Maxim September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step1: Sort all the three arrays

Step2: Scan the array of minimum length for each element , say ai in array A

Step3: Find the element bj in B using binary search such that | bj -ai | is minimun

Step4: Find the element ck1 in C using binary search such that | ck1 - bj | is minimum

Step5: Find the element ck2 in C using binary search such that | ck2 - ai | is minimum

Step6: temp_val = min{ |ai- bj| + |bj - ck1| +|ck1- ai| ,|ai- bj| + |bj - ck2| +|ck2- ai| }

Step7: if(temp_val < val) val=temp_val; store {a,b,c} //here {ai,bj,ck1} or {ai,bj,ck2} which gives minimum value of temp_val

Step8: Goto Step2

Step9: return{a,b,c}


Time Complexity: O(nlogn)

O(nlogn) => time to sort three array, where n is the size of largest array

O(nlogn) => for each elerment of minimum size array we are searching three times using binary search

so O(nlogn) +O(nlogn) =O(nlogn)

Space Complexity => O(1)

Here in Binary search to search any element x , we wil calculate the absolute difference of x with A[mid] ,A[mid-1] and A[mid +1] , if |x -A[mid]| == 0 than return A[mid] otherwise reduce the problem towards left or right half of the array which gives minimum difference with x, i.e if |x -A[mid-1]| < |x -A[mid +1]| move to left half. if |x -A[mid-1]| == |x -A[mid +1]| than check if x > A[mid] move to right half otherwise left half.

- Ravi September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

solution seems to be correct. But time complexity is O(n^2logn)
O(nlogn) to sort + we have to iterate each element in one array and for each element we do 3 binary searches so it is O(n^2logn)

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

The final result is sum of three terms. You think the minimum sum would come from 2 minimum terms + 1 term (no restriction on it). Is it possible that none of the three terms is minimum but their sum is minimum?

- PoWerOnOff November 17, 2015 | Flag
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| +|c-a| is minimum.
 * */

package com.rakshith.triplet;

import java.util.Arrays;

public class triplet1 {
int aa=0;int bb=0;int cc=0;
	void findTriplet(int a[],int b[],int c[]){
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		
		System.out.println(minVal(a,b)+minVal(b,c)+minVal(c,a));
	}
	
	int minVal(int arr1[],int arr2[]){
		
		int i=0;
		int min=Integer.MAX_VALUE;
		while(i<(arr1.length)){
		int j=0;
			while(j<(arr2.length)){
			if((Math.abs(arr1[i]-arr2[j]))<min){
				
				min=Math.abs(arr1[i]-arr2[j]);
			
			}
			
			j++;
		}
			i++;
			}
		System.out.println(min);
		return min;
		
		
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]={10,15,20};
		int b[]={5,10,25};
		int c[]={3,5,15};
		triplet1 trip = new triplet1();
		trip.findTriplet(a, b, c);
	}

}

- raksh September 17, 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| +|c-a| is minimum.
 * */

package com.rakshith.triplet;

import java.util.Arrays;

public class triplet1 {
int aa=0;int bb=0;int cc=0;
	void findTriplet(int a[],int b[],int c[]){
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		
		System.out.println(minVal(a,b)+minVal(b,c)+minVal(c,a));
	}
	
	int minVal(int arr1[],int arr2[]){
		
		int i=0;
		int min=Integer.MAX_VALUE;
		while(i<(arr1.length)){
		int j=0;
			while(j<(arr2.length)){
			if((Math.abs(arr1[i]-arr2[j]))<min){
				
				min=Math.abs(arr1[i]-arr2[j]);
			
			}
			
			j++;
		}
			i++;
			}
		System.out.println(min);
		return min;
		
		
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[]={10,15,20};
		int b[]={5,10,25};
		int c[]={3,5,15};
		triplet1 trip = new triplet1();
		trip.findTriplet(a, b, c);
	}

}

- raksh September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] findTripletWithMinDist(int[] arr, int[] brr, int[] crr)
	{
		int[] abcsum = new int[4];
		int minsum = Integer.MAX_VALUE;
		Arrays.sort(brr); // brr.length*O(brr.length); time
		Arrays.sort(crr);
		for (int i = 0; i < arr.length; i++) {
			int a = arr[i];
			int j = 0; int k = 0;
			int diff = Integer.MAX_VALUE; int prevDiff = Integer.MAX_VALUE;
			while (j < brr.length && k < crr.length) {
				diff = brr[j] - crr[k];
				if (diff <= prevDiff) {
					if (minsum >= Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a)) {
						minsum = Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a);
						prevDiff = diff;
						abcsum[0] = a;
						abcsum[1] = brr[j];
						abcsum[2] = crr[k];
					}
				}
				if (diff > 0) {
					k++;
				} else {
					j++;
				}
			}
		}
		abcsum[3] = minsum;
		return abcsum;
	}

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

public static int[] findTripletWithMinDist(int[] arr, int[] brr, int[] crr)
	{
		int[] abcsum = new int[4];
		int minsum = Integer.MAX_VALUE;
		Arrays.sort(brr); // brr.length*O(brr.length); time
		Arrays.sort(crr);
		for (int i = 0; i < arr.length; i++) {
			int a = arr[i];
			int j = 0; int k = 0;
			int diff = Integer.MAX_VALUE; int prevDiff = Integer.MAX_VALUE;
			while (j < brr.length && k < crr.length) {
				diff = brr[j] - crr[k];
				if (diff <= prevDiff) {
					if (minsum >= Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a)) {
						minsum = Math.abs(a-brr[j]) + Math.abs(brr[j] -crr[k]) + Math.abs(crr[k]-a);
						prevDiff = diff;
						abcsum[0] = a;
						abcsum[1] = brr[j];
						abcsum[2] = crr[k];
					}
				}
				if (diff > 0) {
					k++;
				} else {
					j++;
				}
			}
		}
		abcsum[3] = minsum;
		return abcsum;
	}

- Sort any two arrays if not sorted and iterate for third array. September 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort any two arrays if not sorted and iterate for third array.

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

I have an idea based on two pointers solution as follows. Please let me know if I miss any corner case

1. Sort each array
2. make 3 pointers all start from the beginning of each array
3. calculate the |a-b| + |b-c| + |c-a| based on those 3 pointers. If the value is less than the current minimum, update the minimum and save current a, b, c as result
4. compare all three integers pointed by pointers and only advanced the pointer which points to the minimum value
5. repeat step 3 and 4 until all 3 pointers can't be moved forwarded anymore

- chlin October 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a duplicate problem and refer to details here: cpluspluslearning-petert.blogspot.co.uk/2014/10/data-structure-and-algorithm-find-least.html

Here is the pseduo-code
    1. Combine the 3 arrays into one with data structure to indicate which array the value comes from
    2. Sort this big array (of data structure) with the value from A, B and C as key
    3. Assign minAbsSum,  prevA, prevB and prevC as invalid (to track last A, B and C visited so far)
    4. Go through each element in the big array.(Loop the big array)
        4.1 If curVal is from array A, pick curVal, prevB and prevC. Go to 4.4
        4.2 If curVal is from array B, pick curVal, prevA and prevC. Go to 4.4
        4.3 If curVal is from array C, pick curVal, prevA and prevB. Go to 4.4
        4.4 Calculate the sum of the absolute values of difference
              if prevB and prevC are valid in case of 4.1
              if prevA and prevC are valid in case of 4.2
              if prevA and prevB are valid in case of 4.3
        4.5 Update the minAbsSum if absSum < minAbsSum,
        4.6 Return if minAbsSum = 0, otherwise continue

// Test
//********************************************************************************
void testCase1()
{
    std::vector<int> aVec = { 9, 7, 5, 7, 4, 8, 12, 30, 50 };
    std::vector<int> bVec = { 30, 5, 9, 20, 35, 70, 50, 12 };
    std::vector<int> cVec = { 8, 10, 30, 21, 6, 3, 6, 10, 0 };

    ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
    assert(result.absSum == 0);
    assert(result.val[0] == 30);
    assert(result.val[1] == 30);
    assert(result.val[2] == 30);
}

void testCase2()
{
    std::vector<int> aVec = { 9, 7, 6, 8, 4, 5, 3, 1, 2 };
    std::vector<int> bVec = { 20, 10, 19, 12, 15, 17, 14, 12 };
    std::vector<int> cVec = { 30, 31, 21, 40, 25, 23, 36, 40, 50 };

    ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
    assert(result.absSum == 24);
    assert(result.val[0] == 9);
    assert(result.val[1] == 10);
    assert(result.val[2] == 21);
}

void testCase3()
{
    // 3 vectors has 4 and 9, this case should return 4
    std::vector<int> aVec = { 9, 7, 6, 8, 4, 5, 3, 1, 2 };
    std::vector<int> bVec = { 20, 4, 19, 2, 15, 17, 9, 12 };
    std::vector<int> cVec = { 3, 13, 9, 40, 25, 23, 6, 4, 5 };

    ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
    assert(result.absSum == 0);
    assert(result.val[0] == 4);
    assert(result.val[1] == 4);
    assert(result.val[2] == 4);
}

void testCase4()
{
    // 3 vectors has two sets result
    // (90, 89, 91) and (3, 4, 5)
    // in this case, it should return (3, 4, 5)
    std::vector<int> aVec = { 90, 3, 16, 28, 45, 35, 63, 71, 82 };
    std::vector<int> bVec = { 89, 4, 19, 26, 48, 37, 69, 72, 86 };
    std::vector<int> cVec = { 91, 5, 15, 29, 43, 33, 66, 74, 85 };

    ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
    assert(result.absSum == 4);
    assert(result.val[0] == 3);
    assert(result.val[1] == 4);
    assert(result.val[2] == 5);
}

void testCase5()
{
    std::vector<int> aVec = { 90, 83, 16, 28, 45, 35, 63, 71, 3 };
    std::vector<int> bVec = { 95, 88, 19, 26, 48, 37, 69, 72, 1 };
    std::vector<int> cVec = { 91, 85, 15, 29, 43, 33, 66, 74, 2 };

    ResultTuple result = CalculateLeastAbsSum(aVec, bVec, cVec);
    assert(result.absSum == 4);
    assert(result.val[0] == 3);
    assert(result.val[1] == 1);
    assert(result.val[2] == 2);
}

- peter tang October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

0) sort a, b, c
1) i,j,k = 0 to length
2) calculate X = |a[i] - b[j]|, Y = |b[j] - c[k]|, Z = |c[k] - a[i]|
3) max = maximum(X, Y, Z)
4) minimize max
- if max == X
a[i] > b[j]:
j++
else:
i++
- if max == Y
b[j] > c[k]:
k++
else:
j++
- if max == Z
c[k] > a[i]:
i++
else:
k++

public class MinimumSum {

    public int[] findMinimum(int[] a, int[] b, int[] c) {
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);

        int i = 0, j = 0, k = 0;

        long x = Math.abs(a[i] - b[j]);
        long y = Math.abs(b[j] - c[k]);
        long z = Math.abs(c[k] - a[i]);

        long minimum = x + y + z;
        int minI = i;
        int minJ = j;
        int minK = k;

        while (minimum != 0 && i < a.length && j < b.length && k < c.length) {
            // find max of x, y, z
            long max = Math.max(Math.max(x, y), z);
            // minimize max
            if (max == x) {
                if (a[i] > b[j]) {
                    j++;
                } else {
                    i++;
                }
            } else if (max == y) {
                if (b[j] > c[k]) {
                    k++;
                } else {
                    j++;
                }
            } else { // max == z
                if (c[k] > a[i]) {
                    i++;
                } else {
                    k++;
                }
            }

            if (i < a.length && j < b.length && k < c.length) {
                x = Math.abs(a[i] - b[j]);
                y = Math.abs(b[j] - c[k]);
                z = Math.abs(c[k] - a[i]);

                long current = x + y + z;
                if (current < minimum) {
                    minimum = current;
                    minI = i;
                    minJ = j;
                    minK = k;
                }
            } else {
                break; // stop searching
            }
        }

        return new int[]{a[minI], b[minJ], c[minK]};
    }

- zaitcev.anton October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int binarySearch(int target, vector<int> & array){
	
	int left = 0, right = array.size() - 1;
	
	while(left <= right){
		int mid = left + (right - left)/2;
		if(array[mid] == target){
			return target;
		}
		else if(array[mid] < target){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}		
	}
	
	if(right == -1){
		return array[left];
	}
	else if(right == array.size() - 1){
		return array[right];
	}
	else{
		return abs(array[right] - target) > abs(array[left] - target) ? array[left] : array[right];
	}	
}

bool check(vector<int> & array, int a, int b){
	
	if(a > b) swap(a, b);
	
	// find the ga >= a; find the lb <= b;
	// if(ga <= lb) return true;
	// else return false;
	
	int ga, lb;
	
	int left = 0, right = array.size() - 1;
	
	while(left <= right){
		int mid = left + (right - left)/2;
		if(array[mid] == a){
			ga = a;
			break;
		}
		else if(array[mid] < a){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}		
	}
	
	if(right == array.size() - 1){
		return false;
	}
	
	ga = array[right];
	
	int left = 0, right = array.size() - 1;
	
	while(left <= right){
		int mid = left + (right - left)/2;
		if(array[mid] == b){
			ga = a;
			break;
		}
		else if(array[mid] < b){
			left = mid + 1;
		}
		else{
			right = mid - 1;
		}		
	}
	
	lb = array[left];
	
	return ga <= lb;	
}

int findMinimum(vector<int> & a, vector<int> & b, vector<int> & c){
	
	int minSum = -1;	
		
	for(int i = 0; i < a.size(); i++){
		
		int numb = binarySearch(a[i], b);
		if(check(c, a[i], numb)){
			minSum = min(minSum, 2 * abs(a[i] - numb));
		}
		
		int numc = binarySearch(a[i], c);
		if(check(b, a[i], numc)){
			minSum = min(minSum, 2 * abs(a[i] - numc));
		}	
	}
	
	for(int i = 0; i < b.size(); i++){
		
		int numc = binarySearch(b[i], c);
		if(check(a, b[i], numc){
			minSum = min(minSum, s * abs(b[i] - numc));
		}		
	}
	
	return minSum;	
}

- PoWerOnOff November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.company;

import java.lang.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        int a[] = {1,5,100};
        int b[] = {1,45,75};
        int c[] = {1,100,200};
        Arrays.sort(a);
        Arrays.sort(b);
        Arrays.sort(c);
        int p = a.length;
        int q = b.length;
        int r = c.length;
        int diff = Integer.MAX_VALUE;
        int i=0,j=0,k=0;
        int[] arr = new int[3];
        while(i<p || j<q || k<r){
            int max_v = Math.max(a[i],Math.max(b[j],c[k]));
            int min_v = Math.min(a[i],Math.min(b[j],c[k]));
            int curr_diff = max_v - min_v;
            if(curr_diff < diff){
                diff = curr_diff;
                arr[0] = a[i];
                arr[1] = b[j];
                arr[2] = c[k];
            }
            if(curr_diff == 0) {
                break;
            }
            if(a[i] == min_v) i++;
            else if(b[j] == min_v) j++;
            else k++;
        }
        System.out.print(arr[0] + " " + arr[1] + " " + arr[2]);
    }
}

- quickuser May 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Fails for a simple case {1,5,100},{1,45,75},{1,100,200}

- Abhi September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry abt this. bad post.

- Abhi September 16, 2015 | Flag


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