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.

- navid May 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please eloborate your expression. for s(k,m)

- dummy May 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi May 25, 2014 | Flag
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.

- Brandy May 24, 2014 | Flag Reply
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.

- confused May 22, 2014 | Flag Reply
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;
	}
}

- Gurpreet Singh Makkar May 24, 2014 | Flag Reply
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.

- Anonymous May 22, 2014 | Flag Reply
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.

- Anonymous May 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Michael.J.Keating May 21, 2014 | 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