Is there a Better Algorithm for this problem?

[Kenji4861]

At an interview one time, I was told to write a function that will take in a string and reverse the order and return it.

One way I *tried* to do it is

1. find out the size of the string
2. create new array the same size,
3. Make the size of the string a counter counting down and enter every newstring[counter] = string[endcounter];

Maybe there was a more creative way to do this since they asked me to do it. Maybe somehow use recursion? ANyone know?

 

[crystal]

print reverse split (/\s+/,$sting);

Hahaha... Just joking with you.

 

[CSoup]

Yes, you can definitely do it with recursion or an explicit stack.

 

[Rallispec]

try this:

void reverse (char *s)
{
if (s[0] == \0)
return
else {
reverse (&s[1]);
putchar(s[0]);
}
}



(this is in C... but the same thing could be converted to any other language.. its just simple recursion)


hope this helps...

 

[Tracer]

Another thing you can try is reverse the string in place. This way you don't use double the amount of memory.

 

[gopunk]

i'm not quite sure recursion is any faster per se, though it might be easier to write.

what are explicit stacks? maybe i know, but there's a different term for them?

 

[CSoup]

<< i'm not quite sure recursion is any faster per se, though it might be easier to write.

what are explicit stacks? maybe i know, but there's a different term for them? >>



What I mean is that you can use the stack data structure. Using recursion you are essentially using an implicit stack through the call stack of the recursion.

 

[gopunk]

<<

<< i'm not quite sure recursion is any faster per se, though it might be easier to write.

what are explicit stacks? maybe i know, but there's a different term for them? >>



What I mean is that you can use the stack data structure. Using recursion you are essentially using an implicit stack through the call stack of the recursion. >>



ah gotcha.

 

[BlackOmen]

Given language choice I'd use C++.

char letter;
stack<char> reverse
while( cin.peek() )
{
cin.get >> letter;
reverse.push(letter);
}
while( !reverse.empty() )
{
cout << reverse.top();
reverse.pop();
}

 

[Kenji4861]

<< Another thing you can try is reverse the string in place. This way you don't use double the amount of memory. >>



Wouldn't this make the code harder to read and performance to go down?

 

[Tracer]

<<
<< Another thing you can try is reverse the string in place. This way you don't use double the amount of memory. >>

Wouldn't this make the code harder to read and performance to go down? >>

Performance should actually be better. Anyways here's one way to do it.. I'll be a little harder to read, but more effcient, I think.


char *
string_reverse (char *str)
{
char *pFront = str;
char *pBack;
char cTemp;

if (str == NULL || str[0] == '\0') // Make sure string isn't empty or NULL
return str;

pBack = str + strlen (str) - 1;

while (pFront < pBack)
{
cTemp = *pFront;
*pFront = *pBack;
*pBack = cTemp;
pFront++;
pBack--;
}
return str;

}

Tracer

 

[arcain]

You know.. I always thought this problem was a trick question, because it always seemed so straightforward to me.

You want to reverse it in place to avoid unnecessary memory usage (including instantiation of stack objects, think of all the code being executed when a handful of lines will do it).

void
reverse(char *str)
{
int i;
char temp;
for (i = 0; i < strlen(str)/2; ++i)
{
temp = str[ i ];
str[ i ] = str[strlen(str) - i - 1];
str[strlen(str) - i - 1] = temp;
}

return;
}

You could store strlen(str) to a variable if you want, but the compiler should be smart enough to keep it in a register.

If you want to use even less memory, you can get rid of "char temp;" and use 3 XORs (left as an exercise for the reader). Performance is probably actually slower though, because the "char temp;" can reside in a register, and XORs are relatively slow operations, though I've not looked that closely.

 

[Calin]

Arcain, XOR is a hardware operation (a microprocessor instruction) who execute in the same time as
anyone of OR, AND. Usually takes the same time as a integer addition

Calin

 

[singh]

By far, the best method is in-place reversal. The fastest and most efficient way to do it.