## Amazon Interview Question

- 1of 1 vote
Find the all the sequence from Unsorted array.

Example : {2,4,6,8,10,14,11,12,15,7} is the unsorted array. We have to find out possible sequences.

Output would be :

Seq 1 : {2,4,6,8,10,11,12,15}

Seq 2 : {2,4,6,8,10,14,15}

Note : if I pick any element in array than next element would be grater than the previous element.

**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 on April 23, 2012 Edit | Flag Reply