Samsung Interview Question for Senior Software Development Engineers


Country: India




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

We are dealing with worst case. Or put another way we are going to make things difficult for the poor crow and it is not smart enough to figure out that we are being mean.
Let's assume the overflow numbers are all different. (this might also work if some are the same) .
We sort the pots such that the crow starts with the one that needs the most (poor crow )
He knows (this crow just happens to me male) the values so he will try to optimize things.
To find the first one the crow puts the smallest number of rocks in to each pot.
Let O[1] be the number of rocks needed to overflow the pot that needs the least and O[n] be the number that needs the most with O[i] being some pot in between. As we are being mean the crow starts with O[n] and after depositing O[1] in each gets to pot 1 and it over flows.
He has used n*O[1] rocks.
Now all the other pots have O[1] rocks in them so it will take O[2]-O[1] rocks to overflow pot 2.
Now the crow starts at pot n and puts O[2]-O[1] in each but he can stop at pot 2 as pot 1 is out of consideration.
This costs
(n-1) *( O[2]-O[1])
The next round costs
(n-2) *(O[3]-O[2])
And so on
(n-3)*(O[4] - O[3])
n*O[1] + (n-1) *( O[2]-O[1]) + (n-2) *(O[3]-O[2]) + (n-3)*(O[4] - O[3]) …… (n-k)(O[k]-O[k-1])
This is not all that fun to think about another way is to think about how things look when he has made k pots over flow.
The K smallest have been filled and the rest of have had O[k] added to them without result.
Just to make it easier lets rearrange the pots now with the smallest first.
So we can say that we get sum of O[1 to k inclusive] + (n-k) * O[k];
A smart crow which you are not allowed to have being the worst case might begin to see a pattern and suspect you have sorted things to make his life difficult and start working from the other end but we are analyzing the worst case so this is not allowed.
A stochastic crow (they are not found in this part of the country but we had them back east) would use different orders each time and get better results but this gives you the average case not the worst case and is much harder to calculate.

- Dr A.D.M. May 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This iteration:
(n-2) *(O[3]-O[2])
should be:
(n-2) *(O[3]-O[2]-O[1]), since in the 1st step O[1] was taken from O[3] already, and in the 2nd step also O[2] is subtracted. And so on.

- sk September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice explanation. But question could have been a bit clear about the knowledge of the crow about the overflow numbers.

- santakdalai90 October 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
 	int N = input2;
	int K = input3;
	int len = input1.Length;
	if((N < K || K < 1)||(N!=len))
	{
		return  -1;
	}
 	int i = 0;
	int j = 0;
	for(i = 0;i < N;i++)
	{
		if(input1[i] < 1)
		{
			return   -1;
		}
	}
	for(i = 0;i < N;i++)
	{
		for(j = 0;j < N - i - 1;j++)
		{
			if(input1[j] > input1[j + 1])
			{
				int temp = 0;
				temp = input1[j + 1];
				input1[j + 1] = input1[j];
				input1[j] = temp;
			}
		}
	}

int Out = 0;
int Val = input1[K-1];
int ValPrev = 0;
for(i = 0;i < K - 1;i++)
{
	if(input1[i] < Val)
	{
		Out += (input1[i] - ValPrev)*(N - i);
		ValPrev = input1[i];
	}
	else if((input1[i] == Val))
	{
		Out += input1[i] - ValPrev;
	}
}
for(i = K;i < N;i++)
{
	if(input1[i] > input1[K-1])
	{
		Out += input1[K-1] - ValPrev;
	}
}
Out += input1[K - 1] - ValPrev;

return Out;
}

- Jais74 May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didn't understand what algorithm to find here. You have the overflow numbers so you need to test it with each pot, with minimum first as you did in the example.

Sort the Overflow array. Worst case is : Overflow[0]*n. For the second overflow you will do (Overflow[1]-Overflow[0])*(n-1) in worst case as every pot has Overflow[0] rocks from last phase. If we continue this "k" times, we are done.

- maverick545 May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the algorithm should be to create a min heap of k size with all the pots in that and the heapify to be done based on the overflow number. In this way, after creating the heap all one has to do is pop the first element and print the number of stones needed to overflow it.

- Madhur May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to create a min heap of k size which will take O(n) and then after heap creation just pop all elements one by one and add the total number of stones needed to overflow each pot.

- madhur.eng May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I didnt understand the example,

"Let say two pots are there with overflow no.s {5,58}, and crow has to overflow one pot(k=1). So crow will put 5 stones in pot with overflow no.(58), it will not overflow, then he will put in pot with overflow no.(5), hence the total no. of stones to make overflow one pot is=10."

Why do you have put in (58) first and then in (5). Why not just in (5)

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

It's because the crow doesn't know which pot is which. So, the crow may get lucky and try the 5 pot first, but in the worst case he may get unlucky and try the 58 pot first. He would only know it's the 58 pot after depositing 5 stones in it and seeing that it has not overflowed. The problem asks about the minimum number of stones in the worst case. It's a much more difficult problem to determine the behavior of the crow to minimize the expected number of stones needed.

- eugene.yarovoi May 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am assuming that array is Sorted. Have a try

public static void main(String[] args)
{
int[] overflow = {5,8,10,15,17};
int n = 5;
int k = 3;
int result = 0;

for(int i=0 ; i<k ;i++)
{
int min = overflow[i];
for(int j=i; j<overflow.length; j++)
{
overflow[j] = overflow[j] - min;
result = result + min;
}
}

System.out.println(result);
}

- Mayank July 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am assuming that the Array is Sorted.

public static void main(String[] args)
{
int[] overflow = {5,8,10,15,17};
int n = 5;
int k = 3;
int result = 0;

for(int i=0 ; i<k ;i++)
{
int min = overflow[i];
for(int j=i; j<overflow.length; j++)
{
overflow[j] = overflow[j] - min;
result = result + min;
}
}

System.out.println(result);
}

- Mayank July 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am assuming that the Array is Sorted.

public static void main(String[] args) 
	{
		int[] overflow = {5,8,10,15,17};
		int n = 5;
		int k = 3;
		int result = 0;
		
		for(int i=0 ; i<k ;i++)
		{
			int min = overflow[i];
			for(int j=i; j<overflow.length; j++)
			{
				overflow[j] = overflow[j] - min;
				result = result + min;
			}
		}
		
		System.out.println(result);
}

- Mayank July 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int ThirstyCrowProblem(int[] input1, int input2)
{
int len = input1.Length;
int minStones = 0;
Array.Sort(input1);
if (input1 == null || input2 <= 0 || input2 > len || len <= 0)
{
return -1;
}
if(input2 == 1 && input1[0] != 0)
{
minStones = len * (input1[0]);
return minStones;
}
int strt = 0;
for (int i = 0; i < input2; i++)
{
if(input1[i] == 0)
{
strt++;

}
}
int s = 0; minStones = (len-strt) * (input1[strt]); int j = 0;
for (int i = strt; i < input2; i++)
{
if(i>strt)
{
//s = s + input1[i - 1]; j = j+input1[i] - s;
minStones = minStones + Math.Abs(input1[i] - input1[i-1]) * (len - i);
}
}
return minStones;
}

- SS June 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Just sort the overflow array and return the sum of first K elements.

- Unknown Factor May 06, 2015 | Flag Reply


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