Joe Crobak's answer is very good and complete. S/He considers many
possible situations and analyze the time complexity. I do not think
there is any other faster algorithm consuming less memory exists.
Basically this is a very easy problem and you do not have many
possible trick to do. All involved are basic algorithm operation such
as hashing, sorting, binary search. Surprising that MS gives such
cheap question.
On Aug 9, 2:19 am, Joe Crobak <[EMAIL PROTECTED]> wrote:
> For me, the easiest way to accomplish this is to have a "reader" index
> and a "writer" index. At each iteration, increment the reader. If
> the character at the position of the reader is NOT in the pattern,
> then write that character to the writer position and increment the
> writer.
>
> i.e.
>
> int len=strlen(subject);
> int writer=0, reader=0;
> while (reader < len) {
> if (subject[reader] "not in pattern") {
> subject[writer]=subject[reader];
> writer++;
> }
> reader++;
>
> }
>
> The interesting part, to me, is how to implement "not in pattern." In
> this case, the alphabet is at most 256 characters. So one can create
> an int array, where array[i] = 1 if (char)i is in the alphabet, and 0
> ow.
>
> i.e.
> int *p_array = (int*)calloc(256,sizeof(int));
> int p_len = strlen(pattern);
> int i;
> for (i=0; i<p_len; i++) {
> p_array[ (int)(pattern[i]) ]=1;
>
> }
>
> to implement "not in pattern" you just check
> p_array[ subject[ reader ] ]. This approach takes O(n + c) where
> n=len of subject and c is the size of the alphabet (a constant).
>
> If you are not allowed to allocate more memory (or the alphabet is too
> big), then sort pattern, so that you can do a binary search to
> implement "not in pattern." This approach takes O(n *log(m)), where
> n=len of subject and m=len of pattern. If you don't have a sorting
> routine, and don't feel like writing one, then implement the "not in
> pattern" via a sequential search of the pattern, for a O(n*m) running
> time.
>
> Another approach is to use a hash table...
>
> Joe
>
> On Aug 8, 10:11 am, "Manish Garg" <[EMAIL PROTECTED]> wrote:
>
> > i think there is only one and srtaight forwad way to do this...
>
> > i m writing C code for that.....if any one can do it with less
> > complexity....plz reply..
>
> > int flag;
> > do{
> > flag=0;
> > for(int i =0;subject[i] !='\0';i++)
> > {
> > if(subjcet[i]==pattern[0]){
> > for(int
> > j=i,k=1;pattern[k]!='\0'&&subject[j]==pattern[k];j++,k++);
> > if(pattern[k]=='\0'){
> > while(subject[i+k]!='\0')
>
> > subject[i]=subject[i+k];
> > break;
> > flag=1;
> > }
> > }
> > }while(flag==1);
>
> > On 8/8/07, Arulanandan P <[EMAIL PROTECTED]> wrote:
>
> > > This was asked to me in Microsoft interview
>
> > > On 8/7/07, Abhi <[EMAIL PROTECTED]> wrote:
>
> > > > Is this your college assignment?
>
> > > > On Aug 7, 9:00 pm, "Arulanandan P" <[EMAIL PROTECTED]> wrote:
> > > > > You have to write a function whose prototype is given bellow. this
> > > > function
> > > > > will accept two char * named subject and pattern. for example
> > > > > subject="abracadbra"
> > > > > and pattern="bca".now it should check occurrences of all chars of
> > > > string
> > > > > pattern in subject . If any match occurs then it will remove that char
> > > > from
> > > > > subject . so finally , as in our example
> > > > > at end subject ="rdr"
>
> > > > > void fun(char *subject,char *pattern)
> > > > > {
> > > > > // write your code here}
>
> > --
> > With Best Regards...
> > ---------------------
> > Manish
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
