Amazon Interview Question
SDE1sCountry: India
We can prove that if there is a run of consecutive horses of the same color, it is always optimal to place them into the same stable. Suppose there is some arrangement of horses violating this constraint. Consider these two horses and their two respective stables. If one of the two stables has fewer horses of the opposite color, the function we're optimizing would be increased by having both horses there. If the two stables have equally many horses of the opposite color, transferring one of the horses to the other stable does not change the value of the function. Therefore, we need not consider breaking up consecutive runs of horses of the same color, and we can reduce the N in the O(K *N^2) runtime to just the number of runs of horses of the same color.
Let the horses are numbered from 1 to n with total k stables. We will calculate C(i,j) which is the minimum sum of products for i stables and j horses.
The recursive relation would be:
C(i, j) = min { P(k,j) + C(i-1, k-1) }
where,
i ranges from 1 to k
j ranges from 1 to n
k ranges from j to i
P(k,j) is the product of black and white horses in range k to j, when put in one stable.
import java.util.Arrays;
public class HorsesInStablesProblem {
public static void main(String[] args) {
//int horses[]={0,1,1,1,0,1,1,0,1,1,1};
int horses[]={-1, 0,1,1,1,0,1};
Integer []whitesUptoI=getHorses(horses, 1);
System.out.println(Arrays.asList(whitesUptoI));
Integer []blacksUptoI=getHorses(horses,0);
System.out.println(Arrays.asList(blacksUptoI));
int stables=4;
int sum=getOptimalSum(stables, whitesUptoI, blacksUptoI);
System.out.println();
System.out.println(sum);
}
private static int getOptimalSum(int stables, Integer whites[], Integer black[]) {
int sum[][]=new int[stables+1][whites.length];
for(int i=1;i<whites.length;i++){
sum[1][i]=whites[i]*black[i];
System.out.print(sum[1][i]+"\t");
}
for(int i=2;i<sum.length;i++){
for(int j=i;j<whites.length;j++){
int min=Integer.MAX_VALUE;
for(int p=i-1;p<j;p++){
int prod=(whites[j]-whites[p])*(black[j]-black[p]);
System.out.println("prod:"+prod);
int val=sum[i-1][p]+prod;
System.out.println("sum("+(i-1)+","+p+")= "+val);
min=Math.min(min,val );
}
sum[i][j]=min;
System.out.println("sum["+i+"]["+j+"]= "+min);
}
}
return sum[stables][whites.length-1];
}
private static Integer[] getHorses(int[] horses, int horseId) {
Integer till[]=new Integer[horses.length];
int horsesCount=0;
for(int i=1;i<horses.length;i++){
if(horses[i]==horseId){
horsesCount++;
}
till[i]=horsesCount;
}
return till;
}
}
What constraint do we have about the number of horses of each type in the stables? If there is none, we can keep a single type of horse in each stable by satisfying the first two conditions. This will result the product in 3 to be zero, hence minimum.
It seems like a dynamic programming, you need to save s(k,m) which is the minimum sum you get from k stable and the horses of 1 to m.
- navid May 21, 2014The relation is
s(k,m) = min over all j's of s(k-1,i)+number of black horses in [j,m]* number of white horses in [j,m]
The solution seems to be O(kn^2) time and o(n) space (by windowing over the table). I am really interested if someone has a better solution with lower time complexity.