Amazon Interview Question SDE-2s
Country: India
Interview Type: In-Person
The code will work because.
all three array are sorted in increasing order.
we get first all 0th positions diff in mindiff.
after that we will found the minimum element in all three element and increase that.
so next time diff will be next diff and possibley miminum.
1. initialize smallest_range as MAX_INT
2. keep 3 pointers/index p1, p2 and p3 which points to the first elements of lists L1, L2 and L3 respectively.
3. get the sum of minimum difference using pointed/indexed by p1, p2 and p3
4. compare it with smallest_range and update it, if found smaller.
5. increment the pointer/index of min value found in step 3.
6. repeat step 3 to 5 until the pointer/index of min value is in range.
The diff value is simply 2 times the different between the largest and the smallest num of the three.
So a naive way to do this is move the pointer of array correspond to the smallest num of the three upward by one, and update, till we reach the top or find three identical number.
condition that need to be taken care of is when there is two equal number, then compare and find the smaller one of the two number which are next to the equal number in corresponding array, and update that pointer.
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define INF 9999999
int diff(int a, int b, int c)
{
return abs(a-b)+abs(b-c)+abs(c-a);
}
void mindiff(int a[], int b[], int c[], int n)
{
int i=0, j=0, k=0;
int mindiff = INF;
do
{
mindiff = min(mindiff, diff(a[i], b[j], c[k]));
if(a[i] <= b[j] && a[i] <= c[k])
i++;
else if(b[j] <= a[i] && b[j] <= c[k])
j++;
else k++;
}while(i < n && j < n && k < n);
printf("mindiff: %d\n", mindiff);
}
/**
* Given 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
* The simple way has complexity O(n^3). However, we use the knowledge that, if a[i]=min(a[i],b[j],c[k]), then the best possible step is i++. By doing this way, the complexity is O(n) or more exactly O(3n)
*/
public static void minDifference(int [] arr1, int []arr2, int []arr3)
{
if (arr1==null || arr1.length<1 || arr2==null || arr2.length<1 || arr3==null || arr3.length<1)
{
System.out.println("Illegal input");
return;
}
long min=Long.MAX_VALUE;
long tmp;
int i, ii, j, jj, k, kk;
i=0;
j=0;
k=0;
ii=0;
jj=0;
kk=0;
while(i<arr1.length && j<arr2.length && k<arr3.length)
{
// check the best until now
tmp=(long) Math.abs(arr1[i]-arr2[j])+Math.abs(arr2[j]-arr3[k])+Math.abs(arr1[i]-arr3[k]);
if (min>tmp)
{
min=tmp;
ii=i;
jj=j;
kk=k;
}
// this is the best of possible
if (tmp<=0)
{
break;
}
// find next step
// we know that, if a[i]=min(a[i],b[j],c[k]), then the best possible step is i++
if (i<arr1.length-1 && arr1[i]<=arr2[j] && arr1[i]<=arr3[k])
{
i++;
}
else if (j<arr2.length-1 && arr2[j]<=arr1[i] && arr2[j]<=arr3[k])
{
j++;
}
else if (k<arr3.length-1 && arr3[k]<=arr1[i] && arr3[k]<=arr2[j])
{
k++;
}
else
{
// though it should never be reached
break;
}
}
System.out.println("The sum of the minimum differences is "+min+": a["+ii+"]="+arr1[ii]+", b["+jj+"]="+arr2[jj]+" and c["+kk+"]="+arr3[kk]);
}
package com.java.datastructue;
import java.util.Arrays;
/*
Given 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
where a, b, c are the elements from each array.
diff = |a-b| + |b-c|+|c-a|
complexitiy: worst case O(n)
*/
public class Problem1 {
public int getSum(int[]i,int[]j,int[]k,int n)
{
int min1,min2,min3,min=0 ;
int[] minArray =new int[n];
for (int p=0;p<n;p++)
{
if(i[p]>=j[p])
{
min1=i[p]-j[p];
}
else
{
min1=j[p]-i[p];
}
if(j[p]>=k[p])
{
min2=j[p]-k[p];
}
else
{
min2=k[p]-j[p];
}
if(k[p]>=i[p])
{
min3=k[p]-i[p];
}
else
{
min3=i[p]-k[p];
}
min=min1+min2+min3;
System.out.println(min);
if(min==0)
{
break;
}
minArray[p]=min;
for(int temp:minArray)
{
if(temp<min)
{
min=temp;
}
}
}
return min;
}
public static void main(String [] args)
{
Problem1 p1= new Problem1();
int[]i ={1,2,4,6,8};
int[]j={3,6,9,10,14};
int[]k={4,7,8,10,13};
int sum =p1.getSum(i, j, k,5);
System.out.println("Sum is :"+sum);
}
}
package com.java.datastructue;
import java.util.Arrays;
/*
Given 3 Arrays of integer sorted in ascending order, get the sum of minimum difference using one element from each array.
where a, b, c are the elements from each array.
diff = |a-b| + |b-c|+|c-a|
complexitiy: worst case O(n)
*/
public class Problem1 {
public int getSum(int[]i,int[]j,int[]k,int n)
{
int min1,min2,min3,min=0 ;
int[] minArray =new int[n];
for (int p=0;p<n;p++)
{
if(i[p]>=j[p])
{
min1=i[p]-j[p];
}
else
{
min1=j[p]-i[p];
}
if(j[p]>=k[p])
{
min2=j[p]-k[p];
}
else
{
min2=k[p]-j[p];
}
if(k[p]>=i[p])
{
min3=k[p]-i[p];
}
else
{
min3=i[p]-k[p];
}
min=min1+min2+min3;
System.out.println(min);
if(min==0)
{
break;
}
minArray[p]=min;
for(int temp:minArray)
{
if(temp<min)
{
min=temp;
}
}
}
return min;
}
public static void main(String [] args)
{
Problem1 p1= new Problem1();
int[]i ={1,2,4,6,8};
int[]j={3,6,9,10,14};
int[]k={4,7,8,10,13};
int sum =p1.getSum(i, j, k,5);
System.out.println("Sum is :"+sum);
}
}
#include<iostream> using namespace std; int Abs(int x) { return x>0?x:-x; } int diff(int a, int b) { return Abs(Abs(a)-Abs(b)); } int min(int a, int b) { return a<b?a:b; } int mindiff(int a[], int b[], int c[], int n) { int i=0,j=0,k=0,mindiff; mindiff= diff(a[0],b[0])+diff(b[0],c[0])+diff(c[0],a[0]); while(1) { if(mindiff==0) break; if( a[i]<=b[j] && a[i] <= c[k] ) i++; else if( b[j] <= a[i] && b[j] <= c[k] ) j++; else k++; if(i<n&&j<n&&k<n) mindiff=min(mindiff,diff(a[i],b[j])+diff(b[j],c[k])+diff(c[k],a[i])); else break; } cout<<mindiff<<"\n "<<i<<j<<k; } int main() { int a[]={1,2,13,15,18}; int b[]={3,5,10,12,13}; int c[]={2,4,6,12,13}; mindiff(a,b,c,5);}
- gupta.abhishek849 August 11, 2013