Zynga Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
I have come up with a code in java which involves character by character computation in the same string. But String being immutable I am doubtful whether it is in place reversal or not. Can someone please verify this:
public class ReverseWordsInStringInPlace {
public static void revInPlace(String s)
{
int sLength=s.length();
int j=0;
int beginIndex=0;
for(int i=0;i<(sLength)/2;i++)
{
s=inPlaceSwap(s,i);
}
while(j<s.length())
{
if(s.charAt(j)==' ')
{
s=indexSwap(s,beginIndex, j-1);
beginIndex=j+1;
}
if(j==s.length()-1)
{
s=indexSwap(s,beginIndex, j);
}
j++;
}
System.out.println(s);
}
public static String indexSwap(String s,int beginIndex,int endIndex)
{
System.out.println(s);
char temp;
StringBuilder sb=new StringBuilder(s);
for(int i=beginIndex;i<=(endIndex+beginIndex)/2;i++)
{
temp=s.charAt(endIndex);
System.out.println(temp);
sb.setCharAt(endIndex,s.charAt(i));
sb.setCharAt(i, temp);
endIndex--;
}
s=sb.toString();
System.out.println(s);
return s;
}
public static String inPlaceSwap(String s,int index)
{
char temp;
int sLength=s.length();
temp=s.charAt(s.length()-1-index);
StringBuilder sb=new StringBuilder(s);
sb.setCharAt(s.length()-1-index, s.charAt(index));
sb.setCharAt(index, temp);
s=sb.toString();
return s;
}
public static void main(String[] args)
{
revInPlace("where are you");
}
}
But the given input is a string. If we make a StringBuffer and make changes to get the result and again convert to a string using the toString() method in the StringBuffer. The string that we finally obtain and the string that was given as input would still be different strings due to their immutable nature. Can we still call such a computation an in-place one?
void swap( char &a, char &b )
{
char temp = a;
a = b;
b = temp;
}
void reverse( char *beg, char *end )
{
end--;
while( end > beg )
{
swap( *beg, *end );
beg++;
end--;
}
}
void reversesentence( char *str )
{
char *beg = str;
char *end = &str[ strlen(str) ];
//First Pass
reverse( beg, end );
//Second Pass: Now reverse each word using space as delimiter
while( 1 )
{
end = beg;
while( *end != ' ' )
{
if( *end == '\0' )
{
break;
}
end++;
}
reverse( beg, end );
if( *end == '\0' )
{
break;
}
else
{
beg = end+1;
}
}
}
int main()
{
char str[] = "Is Love to Play";
cout << str << endl;
reversesentence( str );
cout << str << endl;
}
public class ReverseWord {
public static void main(String[] args){
String test1[] = {"I am word reverser code", "code reverser word am I"};
if (wordReverse(test1[0]).equals(test1[1])){
System.out.println("Success");
}else{
System.out.println("Failed");
}
}
/**
* Reverses the word recursively.
* @param String word
* @return String
*/
public static String wordReverse(String word){
if (word.indexOf(' ') == -1 ){
return word;
}
else{
String temp = "";
for(int i=0 ; i < word.length() ; i++){
if (word.charAt(i) != ' '){
temp += String.valueOf(word.charAt(i));
}else{
break;
}
}
String wrd = word.substring(temp.length());
return wordReverse(wrd.trim()) + " " + temp;
}
}
}
Would this work ?
function revsen(str) {
var str1='';
var temp='';
var temp1='';
for(i=str.length;i>=0;i--)
{
if(str[i]===' ')
{
for(j=temp.length-1;j>=0;j--)
{
str1+=temp[j];
}
str1+=' ';
temp='';
} else if(str[i] != undefined ){
temp+=str[i];
}
if(i===0 && temp.length != 0) {
for(j=temp.length-1;j>=0;j--)
{
str1+=temp[j];
}
}
}
return str1;
}
void swap(char &a, char &b)
{
if(a == b)
return;
a = a + b;
b = a - b;
a = a - b;
}
void reverseStr(string &str)
{
int sz = str.size();
int p1 = 0, p2 = sz - 1, p3 = 0, p4 = 0;
while(p1 < p2)
swap(str[p1++], str[p2--]);
p1 = 0;
while(1)
{
while(p1 < sz && str[p1] == ' ')
p1++;
if(p1 == sz)
return;
p2 = p1 + 1;
while(p2 < sz && str[p2] != ' ')
p2++;
p2--;
p3 = p1;
p4 = p2;
while(p3 < p4)
swap(str[p3++], str[p4--]);
p1 = p2 + 1;
}
}
/*Reverse words : "I love to play" becomes "play to love I" in place.*/
public class ReverseWords {
public char[] reverse(char[] input) {
reverseWord(input, 0, input.length);
int start = 0;
int end = 0;
while (end < input.length) {
if (input[end] == ' ') {
reverseWord(input, start, end);
start = end + 1;
}
end++;
}
reverseWord(input, start, end);
return input;
}
public char[] reverseWord(char[] input, int start, int end) {
int init = start;
int mid = (start + end) / 2;
for (int i = start; i < mid; i++) {
char temp = input[i];
input[i] = input[end - 1 - (i - init)];
input[end - 1 - (i - init)] = temp;
}
return input;
}
public static void main(String[] args) {
ReverseWords rw = new ReverseWords();
char[] output = rw.reverse("all love to play".toCharArray());
String print = String.valueOf(output);
System.out.println(print);
}
}
import java.util.StringTokenizer;
public class reverseWords {
public static void main(String args[])
{
String input = "i like to play";
String output ="";
StringTokenizer tokens = new StringTokenizer(input," ");
while(tokens.hasMoreTokens())
{
output =tokens.nextToken()+" "+output;
}
System.out.println(output);
}
}
Here is some code
- Yoda July 08, 2012char A[]="I love peace"; void revString(int l, int r ) { if (l>=r) return; while(l< r) { SWAP(A[l], A[r]); l++; r--; } } void reverseSentence(int n)//n is length { revString(0,n-1); int i=0; int l=0; while(i<n) { if(A[i]==' ')//assumeing breaking only on space { revString(l,i-1); l=i+1; } i++; } }