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.add(Integer.MAX_VALUE);
         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);
      }
    }

- asenthilkumargce May 06, 2015 | Flag Reply
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++)

- Vishnu May 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Still you can improve this by saving few loop

- vishnu May 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

can you please explain your solution in detail ??

- gagan June 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

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
                {
                                // your code goes here
                                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;
    }
}

- anirudh3.kumar October 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

{

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

}

- Sainath October 28, 2015 | Flag
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;
}

- Anonymous April 29, 2015 | Flag Reply
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

- asenthilkumargce May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon May 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The answer to the question
"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.

- anirudh3.kumar October 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
                {
                                // your code goes here
                                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;
    }
}

- anirudh3.kumar October 28, 2015 | Flag
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;
}

- Anonymous April 29, 2015 | Flag Reply
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..

- Chris April 29, 2015 | Flag Reply
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);
  }

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

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.

- Omri Bashari May 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- asenthilkumargce May 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- JayDee May 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anirudh3.kumar October 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

/* 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
{
// your code goes here
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;
}
}

- anirudh3.kumar October 28, 2015 | Flag
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.

- Anonymous May 20, 2015 | Flag Reply
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.

- Mger May 20, 2015 | Flag Reply
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

- Bharat June 13, 2015 | Flag Reply
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.

- Bonney July 22, 2015 | Flag Reply
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
	{
		// your code goes here
		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;
    }
 }

- anirudh3.kumar October 28, 2015 | Flag Reply
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;
}
}
}

- manu July 22, 2016 | Flag Reply
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;
        } 
    }
}

- manu July 22, 2016 | Flag Reply
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;
}
}
}

- manu July 22, 2016 | Flag Reply
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;
        } 
    }

}

- manu July 22, 2016 | Flag Reply
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;
}
}

- Sathish July 26, 2016 | Flag Reply
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] != 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;
}

- Sayani Sur June 22, 2017 | 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;
}

- Sayani Sur June 22, 2017 | 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; }

- Sayani Sur June 22, 2017 | Flag Reply
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;
}

- Ahmed Moharram June 27, 2017 | Flag Reply
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[0];
} 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;
}

- Vamsi July 26, 2017 | Flag Reply
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);

- ziabadar4991 February 14, 2018 | Flag Reply
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;
}

- Too_lazy August 23, 2018 | Flag Reply
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;
}

- Too_lazy August 23, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I believe it could be solved using greedy strategy.

- abhishek08aug April 29, 2015 | Flag Reply
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;
}

- Manu April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 votes

Correct answer is 11 I think.

- Arpit May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- akm May 03, 2015 | Flag
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;

- Anon May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

Ans is 6 for K=1

- asenthilkumargce May 06, 2015 | Flag
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. :)

- Anonymous April 29, 2015 | Flag Reply
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.

- nobody April 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- puncaz May 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous May 03, 2015 | Flag
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.

- Samar May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- anon May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Is it a puzzle or a coding problem??

- Sanjay May 03, 2015 | Flag Reply
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[0] * N;
    for (int i = 1; i < k; ++i) {

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

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

- stillmilking April 30, 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