Amazon Interview Question
Software Engineer in Testsa brute force approach would be create substrings of different lengths and
search for those substrings. code is
string repeted(string s){
string ret="";
for(int i=0;i<s.length();++i)
for(int j=1;j<s.length();++j){
string a=s.substr(i,j); //cout<<a<<"orig"<<endl;
int k=i+j; // if(k+j<=s.length()) cout<<s.substr(k,j)<<endl;
while(k+j<=s.length() && s.substr(k,j)==a) k+=j;
if(ret.length()<k-i-j) ret=s.substr(i,k-i);
}
return ret;
}
please correct me if im wrong
So how much time was given for complete coding? Bentley's programming pearl book has the simplest implementation (less than 15 lines code) which sort all suffix, and then check common prefix length among adjacent suffix. The time complexity is O(n^2logn) for sorting the suffix (which has avg length of O(n)). Using suffix array this can be done in O(nlogn) though which is bit complex to code. The most efficient method is using suffix tree I guess - which takes even longer to code.
5--10 minutes to code?
to build a suffix tree with error free code? maybe he expected you to copy your homework to him.
i think a decent solution would be to get all substrings of given string, sort them. Then compare consecutive ones and find the consecutive pair with largest match. The matching part of such a pair ll be longest substring repeated. From the coding perspective this is decent. But is it in terms of memory or computation?? :p
if it is the longest palindrome...then start at the middle of the string and go left and right at the same time...each time checking the characters match..when they dont match stop and return the left and right positions indexes and get the string...
excuse me if i understood the question entirely wrong.
Thanks
veeru
str1=rev(str); time 1 min
ans=LCS(str,str1) ; time 4-5 mins(copy from net)
Submit.
toal 7-8 minutes.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
int value;
struct node *child[256];
};
struct trie{
int count;
struct node *th;
};
struct node * createNode()
{
int i;
struct node *p=(struct node *)malloc(sizeof(struct node));
p->value = 0;
for(i=0;i<256;i++)
{
p->child[i] = NULL;
}
return p;
}
struct trie * initialize()
{
struct trie *p = (struct trie *)malloc(sizeof(struct trie));
p->th = createNode();
p->count = 0;
return p;
}
int insert(char *p,struct trie *t)
{
struct node *h = t->th;
struct node *q=NULL;
int level=strlen(p),index,c,i;
c=0;
if(!h)return -1;
for(i=0;i<level;i++)
{
index = (int)p[i];
if(h->child[index] !=NULL)
{
if(c==i)
c++;
}
else
{
q= createNode();
h->child[index] = q;
}
h= h->child[index];
}
t->count +=1;
return c;
}
int getLong(char *p)
{
int m=-1,c;
struct trie *t = initialize();
int i=0;
while(p[i] !='\0')
{
c = insert(p,t);
p++;
if(c>m)
m = c;
}
return m;
}
int main()
{
int i,n;
char p[2500];
scanf("%s",p);
printf("\n%d\n",getLong(p));
}
Assuming we are trying to compare three DNA sequences. We can first build a suffix tree that encompasses all three sequences. A suffix tree allows all suffices of all sequences to be represented simply by going down from the root (at the top) toward each of the leaves (the ends in the bottom). In the leaves are recorded where that particular suffix came from (e.g., sequences 1, 2 or 3).
a good solution is to create a suffix tree for the given word and then find the deepest internal node in that tree.. the prefix of that particular node will give the longest repeated substring
- Anonymous May 15, 2011