Hi,

Could someone tell me if there's a better way of doing this? I was asked this question in an interview and I wrote a piece of code of O(n2).

``````// This function returns a new string of the common alphabets found in a and b
char* intersection(char*a, char* b)
{
static char temp[20];
int i = 0;
if ( (a==NULL) || (b==NULL))
exit(0);
else
{
while ( a != NULL)
{
if(strchr(b, *a))
{
temp[i] = *a;
i++;
a++;
}
}
}

return temp;
}
``````

Thanks,
Tina

Edited by mike_2000_17: Fixed formatting

2
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by Jammie

If the two strings are not sorted, the 'best' way depends on what trade off you want to make. If you want to have a small memory footprint but slower algorithm your way is fine. If you want to have a faster algorithm at the cost of more memory, two histogram tables is a good way:

``````define sa as array[0..CHAR_MAX] = {0}
define sb as array[0..CHAR_MAX] = {0}

// build the histograms
for x = 0 to a.length
++sa[a[x]]
loop

for x = 0 to b.length
++sb[b[x]]
loop

// print the unique intersection
for x = 0 to CHAR_MAX
if sa[x] <> 0 and sb[x] <> 0 then
print x as char
end if
loop``````

In C that comes out to about a 10 line function and it has O(n) time complexity.

Yes, I agree. Your code takes more memory and runs faster. I still need to figure out if there are other options. I'll give it another try.

Thanks a lot.

Tina

I still need to figure out if there are other options.

There are other options, but not for two unsorted strings. Most intersection algorithms assume that both sets are sorted and use an algorithm that is both fast and uses little or no extra memory.