Amazon Interview Question


Country: India




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

This code is running fine, I have kept the printf intact as it helped me in finding solution

#include <stdio.h>
#include <stdlib.h>

int N=5;
int count=0;
//int A[N]={0};

void sumKN(int k, int n, int r) {
    if ( n < 0 ){
         printf("sum going less than 0\n");
         return;
    }
    
    if (n==0 && r !=0 ){
             printf("sum is zero but still number of choices left\n");
             return;
    }
    
    if ( k== N && n !=0 ) {
          printf("no solution for this choice\n");
          return;
    }
    
    if( n == 0 && r==0) {
        printf("got one solution \n");
        count++;
        return;
    }
    if ( r <= 0 ){
         printf("already taken given number of objects\n");
         return;
    }
    
    sumKN(k+1,n,r); //not choosing k
    sumKN(k+1,n-k,r-1); //choosing k
     
}

int main(){
 
     sumKN(1,6,3);
     printf("count is=%d\n",count);
     getchar();
     return 0;   
    
}

- Anonymous July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

For N=10, k=3 this is giving output as 0 . It should be 4. Please check1

- words&lyrics July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry for the last comment! Its working Thanks!

- words&lyrics July 14, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi,

Could someone explain me the significance of the variables used in the program...

int N=5; // what is N ?
int count=0; // What is count...?

void sumKN(int k, int n, int r) // and most chiefly on what is k,n,r..?

sumKN(1,6,3); // why is this 1, 6 ,3...? Where does this 6 came from...?

Slightly confusing for me and many Thanks in advance.

- gdsrinivasan July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int n; // target
int ans = 0;
void get_cnt(int *a, int i, int sum, int num)
{
     if (num == 0 && sum == n )  {ans++; return;}
     if ( i < 0 || num < 0 || sum < 0 ) return;
     
    get_cnt(a, i-1, sum-a[i], num-1);
    get_cnt(a, i-1, sum, num);
}

- diaosi July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

To understand the solution more clearly, you can watch this wonderful video
youtu.be/B9C-UntuQ7c

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u tell what is sum,num and i....in function get_cnt??? with example...

- dollcy July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I kind of burst into laugh. For those non-Chinese guys, the replier of this question's ID is "diaosi", which in Chinese internet means: un-redemptable loser, hahah, u r funny, dude.

- IsaacIto July 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

diaosi has potential to be an excellent programmer,lol

- Vincent September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well, it is an appropriate name.

The question asks for number of ways, and diaosi enumerates them and maintains a count.

Consider a different question: How many even numbers are there, less than 2^64.

diaosi's solution is similar to enumerating all the even integers and adding one to the count!

- Anonymous September 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class KNumSumToN {

	public static int count(int k, int[] numbers, int n) {
		return count(k, numbers, numbers.length-1, n);
	}

	public static int count(int k, int[] numbers, int index, int n) {
		if (k == 0 && n == 0 || (k == 1 && index == 0 && n - numbers[0] == 0)) {
			return 1;
		} else if (index <= 0 || k < 0 || n < 0) {
			return 0;
		} else {
			return count(k - 1, numbers, index - 1, n - numbers[index - 1])
					+ count(k, numbers, index - 1, n);
		}
	}

	public static void main(String[] args) {
		int[] arr1= new int[] { 3,1,2,2,0,4,0};
		System.out.println(count(2, new int[] { 1, 1, 0 }, 3));
		System.out.println(count(2,arr1, 4));
	}
}

- gadolin July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Liked your answer

- Anonymous July 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- Anonymous July 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def sum_to_n(n):
    count = 1 

    # Edge case.
    if n == 1:
        return 1

    for k in range(2, n+1):
        # Loop over the starting points.
        for start in range(1, n - k + 1): 
            # This ending point will leave out the last value.
            end = start + k - 1 

            # If there are trailing values, then permute them.
            for value in range(end, n+1):
                # Check for success.
                if n == sum(range(start, end) + [value]):
                    count += 1

    return count

print sum_to_n(5)

- llvllatrix July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution -

It is redundant to pass in an array from 1-n, so the main function f() just takes n and k.

void f(int n, int k)
{
   int *a = new int[k]; // for print the combinations
   f1(n, k, 1, a, 0)
}


void f1(int n, int k, int min, int* buf, int cur)
{
    if(n==0 && k==0)
    {
        print(buf, cur); // print the combination from 0 to cur.
        return;
    }

    if(k>0)
    {
        for(int i=min; i<n+1;++i)
        {
            buf[cur]=i;  
            f1(n-i, k-1, i+1, buf, cur+1);
        }  
    }      
}

- jiangok2006 July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#include <stdio.h>

int findCount(int n,int k)
{

int count=0,sum=0;
int i=1;
int sumk=k*(k-1)/2;
while(i <= n/2)
{
sum=(i*k)+sumk;
if(sum < n)
{
if(n-sum+(i+k-1)<n)
count=count+k;
}
else
break;
i++;
}
return count;
}

int main()
{
int n,k;
scanf("%d",&n);
scanf("%d",&k);
int count=findCount(n,k);
printf("Count = %d\n",count);
return 0;
}

- Water July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void F(int Last, int CurrSum, int N, int Expect, int &Count, int CurrLevel, int K)
{

if(CurrSum == Expect && K == CurrLevel)

{

++Count;

}

else if(CurrSum < Expect && CurrLevel < K)

{

for(int i = Last; i < N; ++i)

{

F(i, CurrSum + i, N, Expect, Count, CurrLevel + 1, K);

}

}
}

void Entry(int N, int K)
{

int Count = 0;

F(0, 0, N, N, Count, 0, K);
}

- tester July 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

consider n=5, then no. of ways to select nos. from 1 to 5 are
{5},{4,1},{3,2} => no. of ways=3.
similarly for n=10
{10},{9,1},{8,2},{7,3},{7,2,1},{6,4},{6,3,1},{5,3,2},{5,4,1} => no. of ways=9

similarly for n=11,
{11},{10,1},{9,2},{8,3},{8,2,1},{7,4},{7,3,1},{6,5},{6,3,2},{6,4,1},{5,4,2},{5,3,2,1} => no. of ways=12.

Note- no number between 1 to n must be repeated

source code-

#include<stdio.h>
int ways(int n)
{
    int wayn=0;
    if(n<3)return 1;
    int i;    
    int way[n+1];
    way[1]=1;
    way[2]=1;
    for(i=1;i<=(n+1)/2;i++)
    {
      wayn+=ways(i);                    
    }
    if(n%2&& n>=5)
    way[n]=wayn-1;
    else
    way[n]=wayn;
    return way[n];
}
int main()
{
  int n;    
  scanf("%d",&n);
  printf("%d\n",ways(n));
  getch();
  return 0;    
}

- Ankit July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The number of ways of selecting k numbers that add up to n is C(n-1,k-1) : choose k-1 for n-1

- notbad July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sum-subset problem (count the answers):
en.wikipedia.org/wiki/Subset_sum_problem

- Anonymous July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{

#include <iostream>
#include <stdio.h> 

bool checkForSum(int k, int n, int size, int* A, int start)
{
    if(k == 0 && n == 0)
        return true;
    if(k == 0 && n > 0)
        return false;
    if(n < 0 ) 
        return false; 
    if(start >= size)
        return false;    
    
    printf("\n n %d k %d start %d  A[start] %d \n", n, k, start, A[start]);
    
    if(checkForSum(k-1, n- A[start], size, A, start +1))
    {   
        printf("\n %d \n", A[start] );
        return true;
    }   
    else
    {   
         return checkForSum(k,n, size, A, start+1);
    }   
}

int main()
{
    int A[5] = {4, 1, 2, 0, 1}; 
    checkForSum(3, 4, 5, A, 0 );
    return 1;
}

}

- radhika.nitk July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Another simple code :

#include<iostream>
using namespace std;
int c=0,n;
int sum_set(int sum,int i,int k)
{      if(i>n+1)       return 0;
       if(k<0)         return 0;
       if(k==0)
       {  if(sum==0) { c++; return 0; }
          else       return 0;
       }
       sum_set(sum-i,i+1,k-1);
       sum_set(sum,i+1,k); 
}
main()
{   int k;
    scanf("%d %d",&n,&k);
    sum_set(n,1,k);
    printf("%d\n",c);
    system("pause");
    return 0;

}

- singhsourabh90 July 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Exhaustive backtracking approach:

void foo(int* arr,int k,int* res,int depth,int N,int sum,int dec)
{
        int i;
        if(sum>N) return;
        if(depth==k)
        {
                if(sum==N)
                        print(res,N);
        }
        else
        {
                if(dec<N)
                {
                        if(!res[dec])
                        {
                                res[dec]=1;
                                foo(arr,k,res,depth+1,N,sum+arr[dec],dec+1);
 
                                res[dec]=0;
                                foo(arr,k,res,depth,N,sum,dec+1);
                        }
                }
        }
}

Complete code here: ideone.com/BeAnJ

- Aashish July 21, 2012 | 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