tough interview question

D

denis_browne

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

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?
 
V

Vladimir S. Oka

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

<snip... repeated post>

This is Usenet, an asynchronous, decentralised and distributed system,
not a chat room. After posting a question, wait for at least 24 hours
before assuming you didn't get any replies.
 
P

pete

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

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?

/* BEGIN new.c output */

The string is "ABCFABHYIFAB"
substring 1 is "AB"
substring 2 is "FAB"

substring 1, "AB", is at "ABCFABHYIFAB" + 0
ABCFABHYIFAB

substring 1, "AB", is at "ABCFABHYIFAB" + 4
ABHYIFAB

substring 1, "AB", is at "ABCFABHYIFAB" + 10
AB

substring 2, "FAB", is at "ABCFABHYIFAB" + 3
FABHYIFAB

substring 2, "FAB", is at "ABCFABHYIFAB" + 9
FAB

/* END new.c output */

/* BEGIN new.c */

#include<stdio.h>
#include<string.h>

#define STRING ABCFABHYIFAB
#define SUB_1 AB
#define SUB_2 FAB
#define str(s) # s
#define xstr(s) str(s)

int main(void)
{
char *ptr;
char *sun[] = {xstr(SUB_1), xstr(SUB_2)};
const char *const string = xstr(STRING);
unsigned n;

puts("/* BEGIN new.c output */\n");
puts("The string is \"" xstr(STRING) "\"");
puts("substring 1 is \"" xstr(SUB_1) "\"");
puts("substring 2 is \"" xstr(SUB_2) "\"\n");
for (n = 0; n != sizeof sun / sizeof *sun; ++n) {
ptr = strstr(string, sun[n]);
while (ptr != NULL) {
printf("substring %u, \"%s\", is at \"%s\" + %d\n",
n + 1, sun[n], string, (int)(ptr - string));
puts(ptr);
putchar('\n');
ptr = strstr(ptr + 1, sun[n]);
}
}
puts("/* END new.c output */");
return 0;
}

/* END new.c */
 
R

Rod Pemberton

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

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?

ROFL! Hilarious!

Someone actually asked you to write an LL(1) parser as part of your job
interview?

Seriously, the key problem here is: do you know what the substrings are in
advance? If not, some complexity is added to determine the substrings.
But, once you know the substrings, you only need an LL(1) parser, which you
can implement with two loops and an if. Unfortunately, the last time I
wrote one was twenty years ago...


Rod Pemberton
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top