Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Interview question - any suggestions (http://www.velocityreviews.com/forums/t441615-interview-question-any-suggestions.html)

 denis_browne@hotmail.com 03-03-2006 10:53 AM

Interview question - any suggestions

Hi there,
I got a tough interview questions lately, and I would like to hear

An array of N chars is given
Write an efficient algorithm to find all the repeating substring with a

minimal size
of 2

f.e

ABCFABHYIFAB

sunstrings are:

"AB"
"FAB"

Any suggestions?

 Vladimir S. Oka 03-03-2006 11:11 AM

Re: Interview question - any suggestions

denis_browne@hotmail.com wrote:
> Hi there,
> I got a tough interview questions lately, and I would like to hear
>
> An array of N chars is given
> Write an efficient algorithm to find all the repeating substring with a
>
> minimal size
> of 2
>
> f.e
>
> ABCFABHYIFAB
>
> sunstrings are:
>
> "AB"
> "FAB"
>
> Any suggestions?

BTW, the way you state it, this is a question for comp.programming as I
don't see any reference to C.

 Robin Haigh 03-03-2006 12:01 PM

Re: Interview question - any suggestions

<denis_browne@hotmail.com> wrote in message
> Hi there,
> I got a tough interview questions lately, and I would like to hear
>
> An array of N chars is given
> Write an efficient algorithm to find all the repeating substring with a
>
> minimal size
> of 2
>
> f.e
>
> ABCFABHYIFAB
>
>
> sunstrings are:
>
>
> "AB"
> "FAB"
>
>
> Any suggestions?
>

FA is repeated as well. AB is different, because there's an additional AB
besides the ones that are part of FAB. These things tend to depend a lot on
the precise problem definition: clarification needed...

--
RSH

 Robin Haigh 03-03-2006 12:16 PM

Re: Interview question - any suggestions

"Robin Haigh" <ecl6rsh@leeds.ac.uk> wrote in message
news:du9b7h\$auf\$1@news6.svr.pol.co.uk...
>
> <denis_browne@hotmail.com> wrote in message
> > Hi there,
> > I got a tough interview questions lately, and I would like to hear
> >
> > An array of N chars is given
> > Write an efficient algorithm to find all the repeating substring with a
> >
> > minimal size
> > of 2
> >
> > f.e
> >
> > ABCFABHYIFAB
> >
> >
> > sunstrings are:
> >
> >
> > "AB"
> > "FAB"
> >
> >
> > Any suggestions?
> >

>
> FA is repeated as well. AB is different, because there's an additional AB
> besides the ones that are part of FAB. These things tend to depend a lot

on
> the precise problem definition: clarification needed...

I should also have asked about self-overlapping repeats -- does AAA contain
two instances of AA?

--
RSH

>

 selvinmani@gmail.com 03-03-2006 01:51 PM

Re: Interview question - any suggestions

Hai friend,
You can always refer to any algorithm books like Computer Algorithms by
Sara Base for any doubts regarding algorithms. I think the answer for
your question is definetly found under the topic String
Matching/Seraching.

 Vladimir S. Oka 03-03-2006 02:18 PM

Re: Interview question - any suggestions

selvinmani@gmail.com wrote:
> Hai friend,
> You can always refer to any algorithm books like Computer Algorithms by
> Sara Base for any doubts regarding algorithms. I think the answer for
> your question is definetly found under the topic String
> Matching/Seraching.

Please quote what and who you're replying to. Lurk a while in here
before posting.

 Keith Thompson 03-03-2006 07:57 PM

Re: Interview question - any suggestions

selvinmani@gmail.com writes:
> You can always refer to any algorithm books like Computer Algorithms by
> Sara Base for any doubts regarding algorithms. I think the answer for
> your question is definetly found under the topic String
> Matching/Seraching.