VMWare Inc Interview Question Member Technical Staffs
-2of 2 votesReverse a string in place
Country: United States
Interview Type: Phone Interview
Using recursion as:
#include <string.h>
#include <stdio.h>
#include <conio.h>
void stringRev(char str[],int i,int n)
{
static int j;
if(i<n)
{
char ch=str[i];
stringRev(str,i+1,n);
str[j]=ch;
printf("%c",str[j]);
j=j+1;
}
str[j]='\0';
}
int main()
{
char str[]="asd cdfv gfd";
int n=sizeof(str)/sizeof(str[0]);
stringRev(str,0,n);
}
In place basically means that you dont have to use any extra memory like you should make the changes using only local variable. The complexity would be O(n) because you have to call reverse for every character in the string. Same is the case while swapping the characters of the integers.
@vgeek:
In-place means that you should update the original string rather than creating a new one.
In your recursive call every time creating new string "char str[] "
Its simple just swap begin with end chars
void reverse_in_place(char a[],int n) {
for(i=0; i< n/2 ; i ++)
swap(a[i], a[n-i]);
}
I know that this one could be done by swapping too. That is why i mentioned earlier in my comment. But i am just using a single local variable to reverse the changes. I am not creating the entire string. Its not char str[]. Its char c. And further in swap also you use a local variable like temp to swap the characters. I am using local variable here to store the previous character. Its the same as every time when you call swap function then also a local variable is created to do the required operation.
@vgeek:
1) recursive call takes huge stack memory
2) your recursive function stringRev(char str[],int i,int n)
which every time creates new string and str points to the beginning of string
@Venkatesh
str points to the character in the string. I know that there will be recursion stack space. But at every step one condition is being checked and that condition is put to the stack. So the condition is checked n-1 times so n-1 different allocation frames will be there in the stack. Thats I think the same as that of the for loop as there also the code is moving in the loop n times. Correct me if i am wrong
//Swapping a string inplace
public static String reverse(String input)
{
char[] inputChars = input.toCharArray();
int len = input.length();
for(int i = 0; i < len/2 ; i++)
{
inputChars[i] = (char)((int)inputChars[i] ^
(int)inputChars[len - i - 1]);
inputChars[len - i - 1] = (char)((int)inputChars[i] ^
(int)inputChars[len - i - 1]);
inputChars[i] = (char)((int)inputChars[i] ^
(int)inputChars[len - i - 1]);
}
return new String(inputChars);
}
Solution based on swap function
- LinhHA05 July 24, 2013void reverse(std::string& s){ int i, j; for (i=0, j = s.length() - 1; i < j ; ++i, --j) swap(s[i], s[j]); }