## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

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)

any Comments or optimizations here?

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

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?

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

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

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

}

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.

- mr August 03, 2012