CareerCup

Thanks for the solutions .. My solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;


int* findMinAbsSum(vector<int> &a, vector<int> &b, vector<int> &c)
{
	sort(begin(a), end(a));
	sort(begin(b), end(b));
	sort(begin(c), end(c));
	
	int i = 0, j = 0, k = 0;
	
	int *min = new int[3];
	
	int mn = INT_MAX;
	
	while(i < a.size() && j < b.size() && k < c.size())
	{
		int sm = abs(a[i] - b[j]) + abs(b[j] - c[k]) + abs(c[k] - a[i]);
		if(sm < mn)
		{
			mn = sm;
			min[0] = a[i];
			min[1] = b[j];
			min[2] = c[k];
		}
		
		int *idx = &i;
		int local_mn = a[*idx];
		if(local_mn > b[j])
		{
			local_mn = b[j];
			idx = &j;
		}
		if(local_mn > c[k])
		{
			idx = &k;
		}
		(*idx)++;
	}
	
	return min;
	
}



int main()
{
	vector<int> a = {90, 83, 16, 28, 45, 35, 63, 71, 3 };
	vector<int> b = {95, 88, 19, 26, 48, 37, 69, 72, 1 };
	vector<int> c = { 91, 85, 15, 29, 43, 33, 66, 74, 2};
	
	int *min = findMinAbsSum(a, b, c);
	
	for(int i = 0; i < 3; ++i)
	{
		cout << min[i] << " ";
	}
	return 0;
}

1. merge the three arrays into one array.
2. sort
3. scan from left to right, get the min.

TC: O(nlgn) n is the total length of the three arrays.

public class MS_MinAbsSum {
    class Node implements Comparable<Node> {
        int v;
        int arrId;
        Node(int v, int arrId)
        {
            this.v = v;
            this.arrId = arrId;
        }

        public int compareTo(Node node) {
            return this.v - node.v;
        }
    }

    int[] findMinAbsSum(int[] a, int[] b, int[] c)
    {
        Node[] d = new Node[a.length + b.length + c.length];
        int j=0;
        for(int i=0; i < a.length; ++i)
            d[j++]= new Node(a[i], 0);
        for(int i=0; i< b.length; ++i)
            d[j++] = new Node(b[i], 1);
        for(int i=0; i<c.length; ++i)
            d[j++] = new Node(c[i], 2);

        Arrays.sort(d);
        int[] marks = new int[3];
        for(int i=0; i< marks.length; ++i)
            marks[i] = -1;

        int count = 0;
        int min = Integer.MAX_VALUE;
        int[] mins = new int[3];
        for(int i=0; i<d.length; ++i)
        {
            if(marks[d[i].arrId] == -1) {
                marks[d[i].arrId] = i;
                count ++;
            }
            else
            {
                marks[d[i].arrId] = i;
                for(j=0; j<marks.length; ++j)
                {
                    if(j != d[i].arrId && marks[j] != -1)
                    {
                        if(marks[j] < i) {
                            marks[j] = -1;
                            count--;
                        }
                    }
                }
            }

            if(count == 3)
            {
                int sum = Math.abs(d[marks[0]].v - d[marks[1]].v) +
                        Math.abs(d[marks[0]].v - d[marks[2]].v) +
                        Math.abs(d[marks[2]].v - d[marks[1]].v);
                if(sum < min) {
                    min = sum;
                    mins[0] = d[marks[0]].v;
                    mins[1] = d[marks[1]].v;
                    mins[2] = d[marks[2]].v;
                }
            }
        }

        return mins;
    }
}

Sort three arrays...initialize three iterators on three arrays to position 0, cal diff of three and now keep on advancing iterator to curr min of three values ...and ans is smallest diff...time comlexity is onlogn.
.have u given interview in Pine...how many rounds ...how was your experience ?

Thanks for the solutions .. My solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;


int* findMinAbsSum(vector<int> &a, vector<int> &b, vector<int> &c)
{
	sort(begin(a), end(a));
	sort(begin(b), end(b));
	sort(begin(c), end(c));
	
	int i = 0, j = 0, k = 0;
	
	int *min = new int[3];
	
	int mn = INT_MAX;
	
	while(i < a.size() && j < b.size() && k < c.size())
	{
		int sm = abs(a[i] - b[j]) + abs(b[j] - c[k]) + abs(c[k] - a[i]);
		if(sm < mn)
		{
			mn = sm;
			min[0] = a[i];
			min[1] = b[j];
			min[2] = c[k];
		}
		
		int *idx = &i;
		int local_mn = a[*idx];
		if(local_mn > b[j])
		{
			local_mn = b[j];
			idx = &j;
		}
		if(local_mn > c[k])
		{
			idx = &k;
		}
		(*idx)++;
	}
	
	return min;
	
}



int main()
{
	vector<int> a = {90, 83, 16, 28, 45, 35, 63, 71, 3 };
	vector<int> b = {95, 88, 19, 26, 48, 37, 69, 72, 1 };
	vector<int> c = { 91, 85, 15, 29, 43, 33, 66, 74, 2};
	
	int *min = findMinAbsSum(a, b, c);
	
	for(int i = 0; i < 3; ++i)
	{
		cout << min[i] << " ";
	}
	return 0;
}

/*
*
* @author Addy
*
* Algorithm:
* 1. Sort the individual arrays.
* 2. Place three fingers on the values of the three arrays starting from the 0th location on all three.
* 3. Calculate (abs(a-b) + abs(b-c) + abs(c-a)) with a,b and c being the values at the three fingers
* respectively and compare it with the variable "min".
* 4. Compare the values at the three fingers at each iteration and increment the value of the
* finger carrying the smallest value out of the three.
*/
import java.util.Arrays;
public class one {

public int[] findTheMin(int[] a,int[] b,int[] c){
Arrays.sort(a);
Arrays.sort(b);
Arrays.sort(c);
int Min_absoluteSum = Integer.MAX_VALUE;
int[] minArray = new int[3];
int i=0,j=0,k=0,absolute_sum=0;
int MinOutOfTheThree;
while(i<a.length && j<b.length && k<c.length){
if(absolute_sum < Min_absoluteSum){
absolute_sum = Math.abs(a[i]-b[j]) + Math.abs(b[j]-c[k]) + Math.abs(c[k]-a[i]);
if(absolute_sum < Min_absoluteSum){
Min_absoluteSum = absolute_sum;
minArray[0] = a[i];
minArray[1] = b[j];
minArray[2] = c[k];
}
}
MinOutOfTheThree = a[i];
//Here we increment the index of the array containing the element with the smallest value
if(MinOutOfTheThree > b[j]){
MinOutOfTheThree = b[j];
j++;
} else if(MinOutOfTheThree > c[k]){
MinOutOfTheThree = c[k];
k++;
} else {
i++;
}
}
return minArray;
}

Get Min and Max from each array and check what combination will have minimum sum result.