Amazon Interview Question
Country: India
Interview Type: Phone Interview
This question is not well posed. For instance, the comments of OP do not match the expected output given in the question.
Why don't people put in some thought before posting the question?
In any case, in the worst case, there are \Theta(2^n) possible sequences. Does the guy want all of them?
What about using an iterative approach like they use in the book... Using combinatorics we can think of the array as binary representation. Either 1, it's in the subset, or 0, it's not (2^n possibilities). Therefore we just need to generate an array of subsets that represent the binary representation of the current iteration.
Ex: {1,2,3,4,5,6,7} we step through and the current iteration is 0101101... well, using bitwise shifting we can include all the numbers in the 1's position rendering {2,4,5,7} as the subset.
This makes the problem really easy and iterative! We may be able to speed this up by a factor of 2 by taking the 2's compliment each time and only iterating 2^(n-1) times. But still is O(2^n).
Let me know what you think
// calling convention Sequence(input, 100, 0, temp, 0);
void Sequence(int input[ ], int n, int index, int temp[ ] , int TIndex )
{
if( n < 1 || tIndex < 0 )
{
printf("\n invalid input \n");
return ;
}
else if( n == index )
{
// print temp[] array elements;
}
for (; index < n; index++)
{
if( (Tindex == 0 ) || temp[Tindex -1 ] < input[index] )
{
Sequence(input, n, index + 1, temp, Tindex );
temp[ Tindex++] = input[ index ] ;
Sequence(input, n, index + 1 , temp, Tindex );
}
}
}
I guess each seq must have at least one unique element.
void PrintAllSeq(int start,vector<int>& seq)
{
if (start == n) {
PrintSeq(seq);
return;
}
while((!seq.empty()) && (A[seq.back()] > A[start])) {
seq.pop_back();
}
for (int i = start; i <n;++i) {
if (seq.empty() || (A[seq.back()] < A[i])) {
seq.push_back(i);
} else {
vector<int> newSeq = seq;
PrintAllSeq(i, newSeq);
}
}
PrintSeq(seq);
}
// we need to keep track of the uniqueness
void PrintSeq(vector<int>& seq)
{
if (seq.empty()) return;
bool hasUnique = false;
for(int i =0; i<seq.size(); ++i) {
if (!isPrinted[seq[i]]) {
hasUnique = true;
break;
}
}
// this seq already subseq of some other seq
if (!hasUnique) return;
for(int i =0; i<seq.size(); ++i) {
isPrinted[seq[i]] = true;
cout << A[seq[i]] << ", ";
}
cout << endl;
}
2 4 6 7 .. can be a seq. also .
- Anon April 23, 2012