## 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 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 in each gets to pot 1 and it over flows.
He has used n*O rocks.
Now all the other pots have O rocks in them so it will take O-O rocks to overflow pot 2.
Now the crow starts at pot n and puts O-O in each but he can stop at pot 2 as pot 1 is out of consideration.
This costs
(n-1) *( O-O)
The next round costs
(n-2) *(O-O)
And so on
(n-3)*(O - O)
n*O + (n-1) *( O-O) + (n-2) *(O-O) + (n-3)*(O - O) …… (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.

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

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

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

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

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

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*n. For the second overflow you will do (Overflow-Overflow)*(n-1) in worst case as every pot has Overflow rocks from last phase. If we continue this "k" times, we are done.

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.

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.

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)

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

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.

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

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

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

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)
{
minStones = len * (input1);
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;
}

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

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

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.