Friday, 29 June 2012

InterviewStreet Find Strings Solution C++

InterviewStreet Find Strings Solution C++



Declare a set<string> which will contain strings lexicographically ordered.
For each input string
     generate all its substrings one by one and add them  to set
For each query
     move pointer to require index in set and return the string
     if query no is greater than size of set, print Invalid.



If you know better solution please post it in comments section.
//4 out of 7 test cases passed
typedef unsigned long long int big;
using namespace std;

int main() {

int n,i;
cin >> n;

set<string> s;
set<string>::iterator it;

string s1,temp;
for(i=0;i<n;i++) {   
    cin >> s1;
    int len = s1.length();
    int j,k;
        for(k=len-j;k>0;k--) {
            temp = s1.substr(j,k);

int curr = 1;
int q;
cin >> q;
big k, len;
len = s.size();
cout << len;
for(i=0;i<q;i++) {
    cin >> k;
    if(k>len) {
       cout << "INVALID\n";
    if(curr+(len/2) < k) {
      it = s.end();
      curr = len;
    if(curr-(len/2) > k) {
       it = s.begin();
       curr = 1;
    if(k>curr) {
        int j= k-curr;
        while(j) { it++; j--; }
        cout << *it << endl;
        curr = k;
    else if(k<curr) {
        int j=curr-k;
        while(j) { it--; j--;}
        cout << *it << endl;
        curr = k;
    else cout << *it << endl;

cin >> i;


  1. This comment has been removed by the author.

  2. My algorithms is : create a BST of elements of generated substrings, apply the same double for loop, and whenever we create a new substring, we insert it into BST, and, we do the then for other strings also we insert their substrings into the same bst, after all these, we same them in a array by reading inorderly, give output directly by accessing the indexes..!!!
    the complexity of this algorithm is : O(N^2*M*log(M*N)) where N is the maximum length of a string, and M is number of strings