## Amazon Interview Question for SDE1s

Country: India

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

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.

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

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

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.

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

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.

Comment hidden because of low score. Click to expand.
0
of 2 vote

Can somebody help me understand this problem with examples? I could not understand 3rd condition.

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

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

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

If you can make sure in each stable, only one type of horse [black/white] is stored, then the product will be Zero. This will lead to total sum of products to Zero which will be minimal.
One possible approach is the have white horse in odd locations and black in even locations.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

I think the issue comes when you have many horses in frequently alternating colors and fewer stables.

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.

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