Monday, June 20, 2011

WAP to Find Maximum Windows of Matching Character , You Given two Sequences

Given two sequences of length N, how to find the max window of matching patterns. The patterns can be mutated.

For example, seq1 = "ABCDEFG", seq2 = "DBCAPFG", then the max window is 4. (ABCD from seq1 and DBCA from seq2)

Data Structure :Hash Table

Algorithm:

INDEX:01234567
SEQ1 = "ABCDEFGK";
SEQ2 = "ZGEDFBAP";

here the expected answer is window of size 4
DEFG
GEDF

we use a map to store the characcters indices of SEQ1
then we search for windows of matching characters from SEQ2
only when the window size is >1, we need to use an temporary array...
we push the indices of the matchin chars from SEQ1 into this array...
here we hav arr = 6 4 3 5 1 0
sort this array, 0 1 3 4 5 6
test for maximum window in this array
3 4 5 6 of size 4


Working Code:

#include
#include
#include
#include
#include

using namespace std;

int main()
{
char seq1[] = "ABCDEFGK";
char seq2[] = "ZGEDFBAP";

map m;
map::iterator iter;
vector arr;
int n1,n2;
n1 = strlen(seq1);
n2 = strlen(seq2);

for(int i = 0;isecond);

}
if(count > 0 && (iter==m.end() || i==n2-1))
{

window = 1;
if(count >1)
{
sort(arr.begin(),arr.end());

//check if the characters in SEQ1 lie in the window of size = count
for(int j=1;j maxwindow) maxwindow = window;
}
}
else maxwindow = 1;
count =0;
arr.empty();

}
}
cout<<"Window of max size is "< getchar();
return 0;
}


Time Complexity O(N^2*logn)
Space Complexity O(1)
Source http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-about-strings-11

Posted by Unknown at 8:00 AM
Labels:Data

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )