## Amazon Interview Question for Software Engineers

Team: Development
Country: India
Interview Type: In-Person

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

The correct algorithm would be to check all possibilities of picking K pots in worst case and picking the one with minimum stones among them. Trying to do the problem with any other algorithm is going to fail as there can be an input formed which would make the algorithm fail.

To check all possibilities, it is actually tweaked program of getting all possible kth subset.

The code goes here. Feel free to challenge with any input.

``````public static int ThirstyCrowProblem(int[] input1,int input2,int input3) {
int n = input2;
int k = input3;
int tempk = 0;

if(input1 == null || k < 0 || k > input1.length || n <= 0 || input1.length != n) {
return -1;
}

if(k==0) {
return 0;
}

for(int i = 0; i < n; i++) {
if(input1[i] < 0) {
return -1;
} else if (input1[i] == 0) {
if(++tempk==k) {
return 0;
}
}
}
Arrays.sort(input1);
return minStones(input1,k-tempk,tempk);
}

public static int minStones(int[] input, int k, int start) {
List<Integer> minStones = new ArrayList<Integer>();
minStones(input,k,start,0,minStones);
return minStones.get(0);
}
public static void minStones(int[] input, int k,int start, int stones, List<Integer> minStns) {

if(k==0) {
if(stones < minStns.get(0)) {
minStns.set(0, stones);
}
return;
}

int[] clone = null;
for(int i = start; i <= input.length-1-(k-1);i++) {
if(input[i] == 0) {
continue;
}
clone = input.clone();
//change clone
int stns = 0;
int tempk = 0;
for(int j = clone.length-1; j >= i;j--) {
if(clone[j] == 0) {
continue;
}
if(clone[j] <= clone[i]) {
stns+=clone[j];
clone[j] = 0;
if(++tempk == k) {
break;
} else {
continue;
}
}
stns+=clone[i];
clone[j] -= clone[i];
}
minStones(clone,k-tempk,i,stones+stns,minStns);
}
}``````

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

Need to modify. for(int i = start; i <= input.length-1-(k-1);i++) to for(int i = start; i <= input.length-k;i++)

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

Still you can improve this by saving few loop

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

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

Try this

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));

}
public static int getMinStones(final int a[], final int k) {

if ((a.length < k)) {
return -1;
}

Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
stones1 = 0;
stones2 = 0;

// Traverse until last repeated value of a[i]
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];

// Count number of stones from end of array
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}

//
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}``````

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

``````{

import java.util.Arrays;

public class CandidateCode {

public static int ThirstyCrowProblem(int[] input1, int input2, int input3) {
int no_of_pots = input2;
int no_of_pots_overflow = input3;
int temp_var = 0;

// Invalid Input Case
if (input1 == null || no_of_pots_overflow < 0
|| no_of_pots_overflow > input1.length || no_of_pots <= 0
|| input1.length != no_of_pots) {

System.out.println("Control is Here");
return -1;
}

//If Number of OverFlow Pots is Zero
if (0 == no_of_pots_overflow) {
return 0;
}

for (int i = 0; i < no_of_pots; i++) {

if (input1[i] < 0) {
return -1;
}else if (input1[i] == 0) {
if (++temp_var == no_of_pots_overflow) {
return 0;
}
}
}

//Valid Input
Arrays.sort(input1);
int final_array[] = new int[no_of_pots_overflow];

for(int j=0;j<final_array.length;j++){
final_array[j] = input1[j];
}

int n = final_array.length-1;

int min_stones = final_array[n]*(no_of_pots-no_of_pots_overflow+1);

for(int k=0;k<n;k++){
min_stones = min_stones + final_array[k];
}

return min_stones;
}

public static void main(String args[]){

int input1[] = {5,58};
int input2 = 2;
int input3 = 1;

int minStones = ThirstyCrowProblem(input1,input2,input3);

System.out.println("The Minimum Number Of Stones in Worst Case to Overfolw is ::" + minStones);
}
}``````

}

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

``````int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;

if(N < K || K < 1)
{
return -1;
}

int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}

for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}

for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}

int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}

int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}

for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}

iOut += input1[K-1] - iValPrev;

if(outTemp < iOut)
{
iOut = outTemp;
}

return iOut;
}``````

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

This algorithm fails for below case!

Input : {1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,8,11} , K=2, Actual Ans: 8, This Prog Ans: 19 !!!

Algorithm should look at all possibilities and then decide the minimum one

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

Why is answer 8 in your example, what if the crow put the 8 into the pot with overflow number of 11?

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

"Why is answer 8 in your example, what if the crow put the 8 into the pot with overflow number of 11?"
is that the crow is intelligent enough to know that if he puts 2 stones in 4 pots, he would at least overflow 2 pots.

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

Try this

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));

}
public static int getMinStones(final int a[], final int k) {

if ((a.length < k)) {
return -1;
}

Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
stones1 = 0;
stones2 = 0;

// Traverse until last repeated value of a[i]
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];

// Count number of stones from end of array
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}

//
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}``````

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

int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;

if(N < K || K < 1)
{
return -1;
}

int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}

for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}

for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}

int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}

int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}

for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}

iOut += input1[K-1] - iValPrev;

if(outTemp < iOut)
{
iOut = outTemp;
}

return iOut;
}

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

1. Sort Oi..
2. Try median of the first K Oi's to split the pots into two sub sets that overflow vs that doesn't..
2. Try recursively the sub problem.. of identifying K/2 pots from the overflow sub problem.. and remaining K/2 from (N-k/2) pots.

3. The algorithm should take nlogn steps..

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

``````public static int getMinStones(final int a[], final int k) {

if ((a.length < k)) {
return -1;
}

Arrays.sort(a);

// approach 1:
final int mid = a[k - 1];
int res1 = (mid * (a.length - k));
for (int i = 0; i < k; i++) {
res1 += a[i];
}

// approach 2
int res2 = 0;
for (int i = a.length - 1; i > (k - 1); i--) {
res2 += a[i];
}
System.out.println("Approach 1 = " + res1 + " Approach 2 = " + res2);
return Math.min(res1, res2);
}``````

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

Don't you mean

``````// approach 2
int res2 = 0;
for (int i = a.length - 1; i > a.length - k - 1; i--) {``````

i.e. randomly picking k pots and assuming worst case

I think this is the best solution so far - a choice between focusing on one pot at a time assuming it is the worst (vertical approach) and hedging your bets to get all the pots you need overflowing at the same time (horizontal approach).

It's not clear to me however if maybe the choice of approach could be adapted dynamically to produce a better result.

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

Algorithm fails for the below inputs

input : {2,4,7,7,7,7,7,7,7} , K = 3, Actual Ans: 21 , This algo ans : 42
input : {1,2,6,6,6,6,6,6,6,10} , K = 2, Actual Ans: 16 , This algo ans : 19
input : {1,2,3,3,4,4,6,6,6,11} , K = 2, Actual Ans: 17 , This algo ans : 19
input : {1,2,3,4,5,5,6} , K = 3, Actual Ans: 16 , This algo ans : 18

As you can see, it has a whole lot of failing cases.

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

Yes, this is due to the silly bug as pointed out by Omri Bashari above. Thanks Omri Bashari for pointing out this bug.

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

Algorithm fails for the below input

input: {1, 2, 2, 3, 3, 3, 3, 3, 5, 9, 9, 11}, K = 5, Actual Ans: 27. This algo ans: 32

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

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));

}
public static int getMinStones(final int a[], final int k) {

if ((a.length < k)) {
return -1;
}

Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];
stones1 = 0;
stones2 = 0;
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}

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

Input/Output Specifications Input Specification:
1) A array 0 corresponding to 0-value of N pots {01, 02, On}
2) Number of pots
3) K -value ( number of pots which the crow wants to overflow}

Solution:
1. Sort 0-values
2. Get first K of 0-values from sorted list at 1.
3. MinNumber=Min(K)*(N-K+1) + Min(1)+Min(2)+...+Min(K-1)
where Min(K) - O-value of index K in sorted at 2.

So lets input was:
1) Given 0-values: 23,12,34,45,67,21,7
2) total number of pots is 7
3) Need overflow at least 3 pots

Solutions will be:
1) Sort - 7,12,21,23,34,45,67
2) First 3 values are 7,12,21
3) Min number of stone is 21*(7-3+1)+7+12 = 124

So, all what you need to do is just sort and calculate as above
I think it is not so difficult to prove that it is minimum number.

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

Input/Output Specifications Input Specification:
1) A array 0 corresponding to 0-value of N pots {01, 02, On}
2) Number of pots
3) K -value ( number of pots which the crow wants to overflow}

Solution:
1. Sort 0-values
2. Get first K of 0-values from sorted list at 1.
3. MinNumber=Min(K)*(N-K+1) + Min(1)+Min(2)+...+Min(K-1)
where Min(K) - O-value of index K in sorted at 2.

So lets input was:
1) Given 0-values: 23,12,34,45,67,21,7
2) total number of pots is 7
3) Need overflow at least 3 pots

Solutions will be:
1) Sort - 7,12,21,23,34,45,67
2) First 3 values are 7,12,21
3) Min number of stone is 21*(7-3+1)+7+12 = 124

So, all what you need to do is just sort and calculate as above
I think it is not so difficult to prove that it is minimum number.

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

public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
/* Worst Case can happen only when the pots are arranged in descending order of their O value and their o value is distinct. Crow starts from first minimum traversing till last and for n number of pots required
* n passes will be required.
*
*/
if (input1 == null || input3 < 0 || input3 > input1.length
|| input2 <= 0 ) {
return -1;
}
Arrays.sort(input1);
int stones = 0;

int min = 0;
int prevMin = 0;
for (int i = 0; i < input3; i++) {
min = input1[i] - prevMin;
stones += input2 * min;
input2--;
prevMin = input1[i];

}

return stones;

}
Whats wrong in this?
I sorted in reverse order and checked for first, second , and third minimum and so on

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

The answer is a straightforward summation that can be written in a formula like below:

No. of stones = ∑ (N-i)*[ x_i+1 - ∑ ( x_j) ]

First ∑ runs from i=0 to K
Second ∑ runs from j=1 to i
Underscore means subscript, to indicate "i"th value in an array "x".

Logic and formulation:
1. Create an ascending array "x". This is number of stones required to fill all N pots.
2. K is the number of pots crow wants to fill
3. The crow will start with x_1 in all the pots one by one and as it has the "worst luck", will find the correct pot only in the Nth try. So, number of stones required if K=1 is N*K
4. Now the crow knows that it has wasted (N-1)*K in all the wrong pots. So now all the remaining pots required K less stones to overflow. So the array "x" changes, such that all the values will be x_1 less. This is the crucial part. Changing of the array is taken care of in second summation.
5. Now repeat for the next pot from step 3 from second pot with new array.

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

``````/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
int[] integerArray = {1,2,3,4,5,5,6};
System.out.println(getMinStones(integerArray, 3));

}
public static int getMinStones(final int a[], final int k) {

if ((a.length < k)) {
return -1;
}

Arrays.sort(a);
int i, last, stones1, stones2,stones, count;
for (i = k; i < a.length && a[k - 1] == a[i]; i++);
last = a[i - 1];
stones1 = 0;
stones2 = 0;
for (i = 0; i < k; i++)
{
stones1 += a[a.length - 1 - i];
}
for (i = 0, count = 0; count < k; i++)
{
if ((a[a.length - i - 1] > last) )
{
stones2 += last;
}
else
{
stones2 += a[a.length - i - 1];
count++;
}
}
stones = Math.min(stones1, stones2);
return stones;
}
}``````

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

import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}

int result = (input2-input3)*input1[input3-1]+sumval;
return result;

}
else{
return -1;
}
}
}

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

``````import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}

int result = (input2-input3)*input1[input3-1]+sumval;
return result;

}
else{
return -1;
}
}
}``````

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

import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}

int result = (input2-input3)*input1[input3-1]+sumval;
return result;

}
else{
return -1;
}
}
}

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

``````import java.io.*;
import java.util.Arrays;
public class CandidateCode
{
public static int ThirstyCrowProblem(int[] input1,int input2,int input3)
{
if(input1.length==input2 && input2 >= input3)
{
Arrays.sort(input1);
int sumval=0;
for(int i=0;i<input3;i++){
sumval += input1[i];
}

int result = (input2-input3)*input1[input3-1]+sumval;
return result;

}
else{
return -1;
}
}``````

}

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

Guys try this your code will be solved.

function ThirstyCrowProblem(input1,input2,input3)
{
if(input1.length==input2 && input2 >= input3)
{
input1 = input1.sort(function (a, b) {
return a - b;
});
var sumval=0;
for(var i=0;i<input3;i++){
sumval += input1[i];
}
var result = (input2-input3)*input1[input3-1]+sumval;
return result;
}
else{
return -1;
}
}

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

Hi,

I used the below code:
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.
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.
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.
0
of 0 vote

``````// This is a C++ code, but I do not think it will be a problem
// It covers both scenarios (If the crow wants any pots, or pots with different
// Os
int ThirstyCrowProblem(vector < int > input1, int input2)
{
int size = (int)input1.size();

// It is impossible to have a number of pots that is negative or above the number of all pots
if (input2 > size || input2<1) return -1;

int result = 0;

// We need to know the lowest number of stones
// This means the pots with the least Os
// So, we start by sorting Os, to pick the lowest N (where N is input2)
sort(input1.begin(), input1.end());
int max = input1[input2 - 1];
int lastmax = 0;
for (int t = 1;t<size;t++)
if (input1[t] == input1[t - 1])
input1[t - 1]--;

int skip = 0;

#ifdef HoneyAndMilk
// if what we need is the specific pot (like pots with number 1 have honey while pots with number 2 have milk...)
for (int t = 0;t < size && input1[t] < max;t++) { skip++; result += input1[t]; }
for (int t = skip;t < size;t++) result += max;
#else
// if it is ok to have any pot, and the crow knows that all next left pots are of
// the same O, then it does not need to move back to the first pot in case a smaller
// amount of stones is required to make a closer pot start overflowing
for (skip = size - 1;skip > 0 && input1[skip] >= max;skip--)
result += max;
for (int t = skip;t > skip - input2;t--)
result += input1[t];

#endif
return result;
}``````

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

public static int ThirstyCrowProblem(int[] input1, int input2) {
int stones = -1;
if (input2 < 1 || input1 == null || input1.length < 1 || input1.length < input2) {
stones = -1;
} else if ( input1.length == 1) {
stones = input1;
} else {
Arrays.sort(input1);
int previous = 0;
stones = 0;
for(int i=0;i<input2;i++) {
stones += (input1[i]-previous) * (input1.length - i);
previous = input1[i];
}
}
return stones;
}

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

// overflow is k here

sort(array); //ascending order

int lastindex = array.length-1;
int sum = 0;
for(int i=lastindex; i >= lastindex - (overflow - 1); i--)
sum += array[i];

int minsum = sum;
for(int i=lastindex-1; i >= overflow - 1; i--)
{
sum -= array[i+1];
sum += array[i-overflow] + array[i]*(lastindex - i);

if(sum < minsum)
minsum = sum;
}

print(minsum);

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

#include <iostream>

using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++) /* To check all possibilities*/
{
int i=n-count;
int minvalue=A[i]; /* min among all values in that subarray*/
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}

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

#include <iostream>

using namespace std;
void merge(int A[],int l,int h,int m)
{
int mid=(l+h)/2;
int n1=m-l+1;
int n2=h-m;
int X1[n1],X2[n2];
for(int i=0;i<n1;i++)
{
X1[i]=A[l+i];
}
for(int i=0;i<n2;i++)
{
X2[i]=A[m+i+1];
}
int x1=0,x2=0,i=l;
while(x1<n1&&x2<n2)
{
if(X1[x1]<=X2[x2])
{
A[i]=X1[x1];
x1++;
}
else
{
A[i]=X2[x2];
x2++;
}
i++;
}
while(x1<n1)
{
A[i]=X1[x1];
x1++;
i++;
}
while(x2<n2)
{
A[i]=X2[x2];
x2++;
i++;
}
}
void mergesort(int A[],int l,int h)
{
int mid=(h+l)/2;
if(l<h)
{
mergesort(A,l,mid);
mergesort(A,mid+1,h);
merge(A,l,h,mid);
}
}
int main() {
int n,k;
cin>>n>>k;
int A[n];
for(int i=0;i<n;i++)
{
cin>>A[i];
}
mergesort(A,0,n-1);
int count;
int ans=32000;
for(count=k;count<=n;count++)
{
int i=n-count;
int minvalue=A[i];
int sum=0,c=0;
for(;i<n;i++)
{
if(c<k)
{
sum+=A[i];
c++;
}
else
sum+=minvalue;
}
if(ans>sum)
ans=sum;
}
cout<<ans<<endl;
}

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

I believe it could be solved using greedy strategy.

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

``````int ThirstyCrowProblem(int input1[],int input2,int input3)
{
int N = input2;
int K = input3;

if(N < K || K < 1)
{
return -1;
}

int it = 0;
int jt = 0;
for(it=0;it<N;it++)
{
if(input1[it] < 0)
{
return -1;
}
}

for(it=0;it<N;it++)
{
for(jt=0;jt<N-it-1;jt++)
{
if(input1[jt] > input1[jt+1])
{
int temp = 0;
temp = input1[jt+1];
input1[jt+1] = input1[jt];
input1[jt] = temp;
}
}
}

for(it=0;it<N;it++)
{
printf("%d,", input1[it]);
}

int outTemp = 0;
for(it=0;it<K;it++)
{
outTemp += input1[N-it-1];
}

int iVal = input1[K-1];
int iValPrev = 0;
int iOut = 0;
for(it=0;it<K-1;it++)
{
if(input1[it] < iVal)
{
iOut += (input1[it] - iValPrev)*(N-it);
iValPrev = input1[it];
}
else if((input1[it] == iVal))
{
iOut += input1[it] - iValPrev;
}
}

for(it=K;it<N;it++)
{
if(input1[it] > input1[K-1])
{
iOut += input1[K-1] - iValPrev;
}
}

iOut += input1[K-1] - iValPrev;

if(outTemp < iOut)
{
iOut = outTemp;
}

return iOut;
}``````

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

Correct answer is 11 I think.

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

Code fails for [3,4,10] with K=2
The program outputs 9 while correct answer is 8.
Greedy approach won't work here
---------------------------------------------
How it would be 8 ?? could you please explain ?

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

Code fails at {2,4,10} ans definitely 8; for K=1;

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

"Code fails at {2,4,10} ans definitely 8; for K=1;"

Ans is 6 for K=1

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

Maybe I'm missing something but I think it's much simpler than the above solutions.

The main observation is to see that the number of stones in each cell after each "round" where a round ends when a pot overflows.

Input: ov = [3, 1, 5]

Let cs = sorted(ov, reverse=True) --> [1, 3, 5]

Round 0: [0, 0, 0]
Round 1: [1, 1, 1] --> first pot overflows
Round 2 :[x, 1+2, 1+2] --> [x, 3, 3] --> second pot overflows
...and so on until all K pots overflow

[c1, c2, c3, ...c_K, c_K, c_K....]

for a total of

sum(cs[:k]) + (N-K) * c[K-1]

The first term is the sum of the stones for the K pots and the remaining are the stones in the partially filled pots.

The runtime is O(N log N) for the sort. :)

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

Consider this case [3,5,5,5,5,5,5,5,5,5] and the task is to overflow one pot.
If we will start putting 3 stones in each pot then the worst case scenario is 3*10=30. Correct answer is 5.

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

As mentioned, 0-value is known but information regarding association of 0-value with pots is lost. In that scenarios, how can you rearrange pots (sort) where you do not know the 0-value of pot.

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

Isn't the wost case when crow will find it after using 30 stones instead of 5?

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

Of course O-value is known, but crow cannot know, so it can start filling each pot with 1 stone at a time. after filling 3 stones in each one overflow will happen and total used stone will be 30 in worst case. How 5 can be answer in this case.

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

No matter what pot he puts the 5 into he gets an overflow.

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

Is it a puzzle or a coding problem??

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

Greedy: Sort the array, and then place the smallest amount of rocks in all pots, 1 will overflow, remove that pot, repeat till k pots overflow.

``````#include <iostream>
#include <algorithm>
using namespace std;

int const N = 5;
int const k = 3;
int overflow[N] = {5,58,13,7,6};

int main() {

// nlogn sort
sort(overflow, overflow + N);

int rocks = overflow * N;
for (int i = 1; i < k; ++i) {

int potsRemaining = (N - i);
rocks += (overflow[i] - overflow[i-1]) * potsRemaining;
}

cout << "Rocks: " << rocks << endl;
}``````

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.