## Amazon Interview Question Software Engineer / Developers

• 0

Print all combinations of M members of a set of N elements in a sequence such that each set can be obtained from the previous set by deleting one member and adding one member.

Country: India
Interview Type: In-Person

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

in the first go, it looks like a simple modification to the subsetsum problem with a constraint on the number of items rather than the sum.

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

Say the set N =3 { 1,2,3}
Combinations are {1,2} {2,3} {1,3}

Say the set N= 4 {1,2,3,4}
Combinations are {1,2,3 }, {1,2,4}, {1,3,4}, {2,3,4}

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

picking sets 'such that each set can be obtained from the previous set by deleting one member and adding one member.'
this statement simplifies to picking sets of m elements of n total elements.

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

1. generate/choose m from n items in nCm ways (using combinations)
2. choose 1 item from set generated in step 1 in m ways (for loop)
3. choose 1 item from remain n-m items in n-m ways (for loop)
4. replace item selected in step 2 with item selected in 3

Looks like there will be repititions in this way. Still thinking of a clean way to implement the same.

Total complexity = nCm * (m * n-m)

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

hi

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

hey! i thought of something similar to your idea..but i think we dont need to take nCm combinations. Since we are replacing an element in the set with every possible number later..here is some code to explain what i mean..

``````start=0;
end=m-1;
while(start!=0)
{
for(int i=0,j=start;i<m;i++,j++)
{
set[i]=list[j];
cout<<set[i]<<" ";
}
cout<<endl;
for(j=end+1;j!=start;j=(j+1)%n)
{
for(i=0;i<m;i++)
{
set_func(i,j,set,list);
}
}

void set_func(int i,int j,int set[],int list[])
{
set[i]=list[j];
for(int k=0;k<m;k++)
cout<<set[i]<<" ";
cout<<endl;
}``````

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

oops!! in my previos comment..i forgot to change certain things..firstly! it is a do while loop..then before checking the condition we have
start++;
end=(end+1)%n;

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

A little bit complex. Mark for later consideration.

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

I think first we can generate/choose m from n items in nCm ways (using combinations).
Then find all the LCS(longest common subsequence), with length M-1.
Finally rearrange them, making neighbouring sets with LCS length M-1.

I think it is workable without considering the time complexity.
Anyone has better ideas?

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

what is i here dude ??? how do you actually call this ??

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

``````int N;//no of elements in the set
int count=0;
select_set(char * set,int i,int count)
{
if(count==m)
return 1;
else if(i==N)
return 0;
if(i!=-1)
set[count]=arr[i]+48;
int b=(select_set(set,-1,count)&&select_set(set,i+1,count+1));
}
//this will give all the possible set of m length  i have not done in the way of deleting one and adding one..``````

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

The idea here is to use the Grey code.

In Short Grey Code is: The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit (copied from the wiki).

So by description Grey code is exactly what we need - each Grey Code number is representation of one set . So in place of the bits we put the elements from the set.

Here is a sample:
Decimal Binary Gray code
0 0000 0000
1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000

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

yups Gray code seems to be a perfect viable solution to this problem.

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

lol.

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

Gray code is right.

"You're kidding me right" is an idiot.

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

Can anyone elaborate on how to use grey code for this problem...

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

this prints combinations of size 3 and can be generalized ...

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

void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
cout<<dest<<endl;}
else{
if(!a.empty() && dest.length() < 3 ){
combination(a.substr(1,a.length()),dest+a[0]);}
if(!a.empty() && dest.length() <= 3 ){
combination(a.substr(1,a.length()),dest);}
}

}

int main(){
string demo("abcd");
combination(demo,"");
return 0;
}``````

}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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