CareerCup

String reverse (String inString) {

Char[] ret= inString.toCharArray();
int length = inString.length;
for (int i = 0; i < length/2; i++){
char temp = ret [length-1-i];
ret [length-1-i] = ret [i];
ret [i] = temp;
}

return ret.toString();
}


Complexity: O(N)

Two pointer, one pointing to the top and one pointing the bottom. TopPtr moving downwards and BottomPtr moving upwards. Each time swap the char until TopPtr and BottomPtr meets. O(n/2)

public static String reverse (String st) {
String result = "";
int size = st.length();
for (int i = 1; i <= size; i++)
result += st.charAt( size - i);
return result;

}

A C# recursive function to reverse an input string
public string Reverse(string input)
{
if (input.Length == 1)
{
return input;
}
else
return string.Concat(input[input.Length-1], Reverse(input.Substring(0,input.Length-1)));
}

I think a follow up question to ask would be if there are any restrictions such as only reversing words etc. for example he may be asking to produce a result for a given input "what is your name" as "name your is what".

If this is the case I would split the string first into 2 dimensional array and then merge them back in reverse order.

There can be a better solution.
If you get to store the list in a doubly linked list, then you can reverse it in O(1).

You might understand what I said if you have studied Linked List from Thomas H Cormen's book. There is a problem there for reversing a linked list in O(1). The solution can apply here as well.

Complexity O(n)


void main()
{
int len;
char *p,*ptr="Hello John!!!! How are yUo..";
len=strlen(ptr);

for(p=ptr+len;p>=ptr;p--)
printf("%c",*p);
}

void reverse(char a[ ])
{
int s,e;
s=0;
e=strlen(a)-1;
while(s<e)
{
char t;
t=a[s];
a[s]=a[e];
a[e]=t;
++s;
--e;
}

char* reverse(char * str){
if ( str == null){
return null;
}
char * end = str;
char temp;

while(end){
end++;
}
end--;
while(str < end){
temp = *end;
*end = *str;
*str = temp;
}
return str;
}

See through a mirror.
Complexity : simple.

void ReverseString(char* str, unsigned int length)
{
    int left = 0;
    int right = length - 1;
    
    while( left < right )
    {
        str[left] ^= str[right];
        str[right] ^= str[left];
        str[left] ^= str[right];
        
        left++;
        right--;
    }
}

void reverse(char arr[], int beg, int end) {
if(beg > end)
return;

reverse(arr, beg+1, end-1);

char t = arr[beg];
arr[beg] = arr[end];
arr[end] = t;

return;

}