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