## TATA Consultancy Services Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

The seven bags should have the gems distributed in the following way.
1, 2, 4, 8, 16, 32 & 37

The other part of the question where the teacher can put any number of gems in one purse and asking the student to distribute the rest is invalid. What if the teacher puts all of the 100 gems in one bag? In such a case the student will not be able to distribute the gems and will also not be able to give gems of the required number.

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

@Apostle: Question is not clearly written but I think after having a look at your answer the question becomes more clear.

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

Yes,question is not clearly written.

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

Many solutions work here since 2^7 can express 128 combinations and we need only 100 of those. For example, 50 25 13 6 3 2 1 (and many others) also works. For the above set, calling the bags B1 to B50 based on the value, we have:

C1= B1
C2= B2
C3= B3
C4= B3, B1
C5= B3, B2
C6= B6
C7 to C12 = B6 + C1 to C5
C13= B13
C14 to C24= B13+C1 to C11
C25= B25
C26-49= B25+C1 to C24
C50= B50
C51-C99= B50 + C1 to C49

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

For the second question, as Apostle pointed out, constraints are needed. Figuring out the constraints turns out to be an interesting problem.

One constraint is clear: if the Guru puts more than 50 gems in his bag no solution is possible. In that case, the remaining bags sum to less then 50 and the Guru's bag has 51 or more. So, we do not have a solution that adds up to 50.

Case 1: If 19 =< xg <= 32 then pick 5 coins as 16, 8, 4, 2 and 1 adding xg and 100-total. Note that for all cases we must have xg and 100-total. xg by definition (the guru pick) and 100-total in the 7th bag is the remaining gems which are needed to enumerate up to 100. So, we have a choice with 5 bags only.

If xg is less than 19 (say 18), then xg + 31 < 50, which means that 100-total is > 50 which leads to an infeasible solution.

For example, if xg = 20, then 1,2,4,8,16, 20 and 49. The first 5 coins can enumerate 1-31. With the 6th coin we can enumerate up to 51. Adding the last coin we can enumerate 1 to 100.

Case 2: by symmetry, if 19 <= 100-total =< 32 then xg can be 37 to 50

Corollary: In the range of 19-50, this leaves xg between 33--36 without a feasible configuration. In this range, the first 5 bags can enumerate up to 31, the remaining 2 bags are needed for xg and 100-total. In the range above, 100-total is between 33 and 36. This leaves the numbers 31 to xg that cannot be assembled.

Case 3: Lets now consider the range 10<= xg <= 16 where an alternative strategy may be used. Use the first 4 bags as 1, 2, 4, 8 which allows us to enumerate 1 to 15. The fifth coin is xg, allowing us to enumerate up to xg+15 (minimum of 25). Pick the sixth coin as 25 and the 7th coin as 50 allowing enumerating of the whole range.

Note that 17 and 18 cannot be used in this strategy as 16 cannot be composed leaving those values as infeasible. Similarly 9 cannot be used since 9 + 15 - 24. The sixth coin must be > 25 or the 7th coin would be > 50. If this is the case, then 25 cannot be assembled (the first 5 coins enumerate 1-24; the next coin is 26).

Case 4: 6<=xg<=8. Pick the first 3 bags as 1, 2 and 4 -- we can enumerate up to 7. Next comes xg which allows us to enumerate 8 to xg+7 (minimum 13). We are left with 3 coins. Pick the coins as 12, 25 and 50 allowing enumeration of the full range.

This leaves 5 as infeasible. xg of 1,2,3 and 4 are all feasible as we demonstrated above.

Summary: we can come up with a feasible distribution for a guru pick of any number less than or equal to 50 with the exception of the following numbers:
5, 9, 17, 18, 33, 34, 35, 36.

I probably made a few mistakes above :-)

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

1,2,4,5,13,26,49

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

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

int main(){
int maxNumber,gurunum,num=1,binlen=0;
cout<<"enter maxNumber\n";
cin>>maxNumber;

while(num < maxNumber){
num = (num << 1) + 1;
binlen++;
}

int distnum[binlen+1];	//distnum contains distinct maxNumbers by adding these we get any num between 0 to maxNumber(like 100).
cout<<"enter the maxNumber given by guru\n";
cin>>gurunum;

num = num>>1;
if(gurunum != (100 - num)){
num = 1;
while(num < gurunum)
num = (num<<1);

if(num != gurunum){
cout<<"not possible\n";
return 0;
}
}
num=1;
for(int i=0;i<binlen;i++){
//distnum[i] = num;
cout<<num<<"  ";
num = (num<<1);
}
num--;
num = 100 - num;
cout<<num<<endl;

return 0;

}``````

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

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

int main(){
int maxNumber,gurunum,num=1,binlen=0;
cout<<"enter maxNumber\n";
cin>>maxNumber;

while(num < maxNumber){
num = (num << 1) + 1;
binlen++;
}

int distnum[binlen+1];	//distnum contains distinct maxNumbers by adding these we get any num between 0 to maxNumber(like 100).
cout<<"enter the maxNumber given by guru\n";
cin>>gurunum;

num = num>>1;
if(gurunum != (100 - num)){
num = 1;
while(num < gurunum)
num = (num<<1);

if(num != gurunum){
cout<<"not possible\n";
return 0;
}
}
num=1;
for(int i=0;i<binlen;i++){
//distnum[i] = num;
cout<<num<<"  ";
num = (num<<1);
}
num--;
num = 100 - num;
cout<<num<<endl;

return 0;

}``````

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

There may not be a solution in all the cases. But if there exists, this code will print it out.

``````#define NUM_PURSES 7

void distribute( int total, int alreadyChosen )
{
int result[NUM_PURSES] = {0};
int currentTotal = 0;
int next_count = 1;
bool consumed = false;

for( int i = 0; i < NUM_PURSES; i++ )
{
if( ( !consumed ) && ( next_count >= alreadyChosen ) )
{
consumed = true;
}

if( ( next_count + currentTotal ) > total )
next_count = total - currentTotal;

result[i] = next_count;
currentTotal += result[i];
next_count = currentTotal + 1;
}

for( int i = 0; i < NUM_PURSES; i++ )
std::cout << result[i] << std::endl;
}``````

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

1, 2, 4,8,16,32,64

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.

### 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.

### 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.