Apple Microsoft Interview Question
Software Engineer / Developers Software Engineer in TestsNope, that won't work. Consider having the same character. Then, if you xor any two characters, you would get a 0 since xor only returns 1 if one of the other is different. So, 00 returns 0, 11 returns 0. 01 returns 1 and 10 returns 1
Simple, just add a special case for characters that are equal. If so, do nothing. Otherwise, flip em with xor.
XOR does work, no need to check duplicated characters:
public class ID62240
{
public void reverse(char[] string)
{// swap two numbers without temp variables
int n=string.length;
int left=0;
int right=n-1;
while (left<right)
{
// swap
string[left]=(char)(string[left]^string[right]);
string[right]=(char)(string[left]^string[right]);
string[left]=(char)(string[left]^string[right]);
// next
left++;
right--;
}
}
public static void main(String[] args)
{
ID62240 wpd=new ID62240();
String input="abcdefg12a";
char[] string=input.toCharArray();
wpd.reverse(string);
for (char c: string)
System.out.print(c);
System.out.println();
}
}
#include <stdlib.h>
#include <stdio.h>
void reverse(char* str)
{
int i, j, len;
char temp;
i=j=len=temp=0;
j=strlen(str) - 1;
while(i < j)
{
str[i] = str[i] ^ str[j];
str[j] = str[i] ^ str[j];
str[i] = str[i] ^ str[j];
i++;j--;
}
}
int main()
{
char str[]="hello world";
reverse(str);
printf("%s",str);
getch();
}
void swap (char &a, char &b){a = a ^ b;b = a ^ b;a = a ^ b;}
void reverse(string &s){for(int i=0;i<s.length()/2;i++)swap(s[i],s[s.length()-i-1]);}
int main()
{
string s;cin>>s;
reverse(s);
cout<<s<<endl;
system("pause");
}
//inplace reverse
#include<iostream>
using namespace std;
void main()
{
int length=0;;
char str[7]= "abcdef";
while(str[length] != '\0')
length++;
int i=0;
while(i<length/2)
{
str[i] = str[i] + str[length - i-1];
str[length -i-1] = str[i]- str[length - i-1];;
str[i] = str[i] - str[length -i-1];
i++;
}
cout<<str;
}
void reverse( char *s) {
int i,n=strlen(n);
char *p=s+n-1;
for (i=0;i<n/2; i++) {
*s = *s ^ *p;
*s = *s ^ *p;
*s = *s ^ *p;
s++; p--;
}
}
Generally, with this question the interviewer wants to see how you deal with recursion. For extra marks, you should modify it to the tail-recursive version (Google "tail recursion").
For Java engineers, here's mine - I convert to char array to avoid multiple substring calls ... and to make the tail recursion easier:
public String reverse(String text) {
return reverseHelper(text.length() - 1, text.toCharArray());
}
private String reverseHelper(int index, char[] text) {
return index < 0? "" : text[index] + reverseHelper(index - 1, text);
}
How about:
#include <stdio.h>
#include <string.h>
void reverse(char *stringToReverse);
int main (int argc, const char * argv[]) {
char str[] = "fours";
reverse(str);
printf("%s", str);
return 0;
}
void reverse(char *stringToReverse) {
int start = 0;
int temp = strlen(stringToReverse);
int end = temp - 1;
while (end >= start) {
stringToReverse[temp] = stringToReverse[start];
stringToReverse[start] = stringToReverse[end];
stringToReverse[end] = stringToReverse[temp];
start++;
end--;
}
stringToReverse[temp] = '\0';
}
<pre lang="" line="1" title="CodeMonkey52687" class="run-this">public class ReverseString {
public static void main(String args[])
{
String str = "";
String reversedStr = "";
Scanner input = new Scanner(System.in);
input.useDelimiter(System.getProperty("line.separator"));
System.out.println("Enter a string to reverse: ");
str = input.next();
if(str != null && str.trim().length()!=0)
{
reversedStr = reversedStr.concat(str.substring(str.length()-1));
for(int i=str.length()-2; i>=0; i--)
{
System.out.println(reversedStr);
reversedStr = reversedStr.concat(str.substring(i, i+1));
}
}
System.out.println(reversedStr);
}
}</pre>
Java code Eg: revString("Submit".toCharArray(), 0, 5)
public static void revString(char[] charArr, int start , int end){
while(start < end){
if(charArr[start] != charArr[end]){
charArr[start] = (char) (charArr[start] + charArr[end]);
charArr[end] = (char) (charArr[start] - charArr[end]);
charArr[start] = (char) (charArr[start] - charArr[end]);
}
start++;
end--;
}
}
class ReverseString
{
public static void main(String args[])
{
String original, reverse = "";
Scanner in = new Scanner(System.in);
System.out.println("Enter a string to reverse");
original = in.nextLine();
int length = original.length();
for ( int i = length - 1 ; i >= 0 ; i-- )
reverse = reverse + original.charAt(i);
System.out.println("Reverse of entered string is: "+reverse);
}
}
}
public class ReverseRec {
public static void main(String[] args){
String str=new String();
str="greetings";
ReverseRec rev=new ReverseRec();
String newstr=new String();
System.out.print(rev.reverseRec(str));
}
String reverseRec(String str){
if(str.length()==1){
return str;
}
else {
str= reverseRec(str.substring(1)) + str.charAt(0);
}
return str;
}
}
Java solution:
String reverseString(String s)
{
int size=s.length();
boolean isEven;
char[] myCharAry=s.toCharArray();
if(size%2==0)
{
isEven=true;
}
else
{
isEven=false;
}
if(isEven)
{
for(int i=0; i<(size/2); i++)
{
char temp;
//right side
temp=myCharAry[(size/2)+i];
//swap
myCharAry[(size/2)+i]=myCharAry[(size/2)-1-i];
myCharAry[(size/2)-1-i]=temp;
}
}
else
{
int indexOfMid=size/2;
for(int i=0; i<(size/2); i++)
{
char temp;
//right side
temp=myCharAry[size/2+1+i];
myCharAry[(size/2)+1+i]=myCharAry[(size/2)-1-i];
myCharAry[(size/2)-1-i]=temp;
}
}
return new String(myCharAry);
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static StringBuffer sbf = new StringBuffer("Hello");
public static void main (String[] args) throws java.lang.Exception
{
int high=sbf.length()-1;
int low =0;
while(low<high)
reverse((int)sbf.charAt(low),low++,(int)sbf.charAt(high),high--);
System.out.println(sbf.toString());
}
static void reverse(int a,int i,int b,int j)
{
a = a+b;
b = a-b;
a = a-b;
sbf.setCharAt(i,(char)a);
sbf.setCharAt(j,(char)b);
}
}
}
public static void main(String args[]) {
char[] s = {'s','t','r','n','g'};
int len = s.length;
int j = len;
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[i]- s[len - i - 1]);
}
for (int i = (len%2==0)?(len/2):(len/2+1); i < len; i++) {
s[i] = (char) (s[i] + s[len - i - 1]);
}
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[len - i - 1] - s[i]);
}
for (int i = 0 ; i < len ; i++) {
System.out.println (i+":"+s[i]);
}
}
public static void main(String args[]) {
char[] s = {'s','t','r','n','g'};
int len = s.length;
int j = len;
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[i]- s[len - i - 1]);
}
for (int i = (len%2==0)?(len/2):(len/2+1); i < len; i++) {
s[i] = (char) (s[i] + s[len - i - 1]);
}
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[len - i - 1] - s[i]);
}
for (int i = 0 ; i < len ; i++) {
System.out.println (i+":"+s[i]);
}
}
code
public static void main(String args[]) {
char[] s = {'s','t','r','n','g'};
int len = s.length;
int j = len;
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[i]- s[len - i - 1]);
}
for (int i = (len%2==0)?(len/2):(len/2+1); i < len; i++) {
s[i] = (char) (s[i] + s[len - i - 1]);
}
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[len - i - 1] - s[i]);
}
for (int i = 0 ; i < len ; i++) {
System.out.println (i+":"+s[i]);
}
}
public static void main(String args[]) {
char[] s = {'s','t','r','n','g'};
int len = s.length;
int j = len;
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[i]- s[len - i - 1]);
}
for (int i = (len%2==0)?(len/2):(len/2+1); i < len; i++) {
s[i] = (char) (s[i] + s[len - i - 1]);
}
for (int i = 0; i < len/2; i++) {
s[i] = (char) (s[len - i - 1] - s[i]);
}
for (int i = 0 ; i < len ; i++) {
System.out.println (i+":"+s[i]);
}
}
Use recursive function
*sPtr is the pointer to the input string
void reverse(char *sPtr)
{
if (*sPtr[0]!='\0')
{
reverse(&sPtr[1]);
printf("%c",*sPtr[0]);
}
else
{
return;
}
}
Just use the swap utility function without using a temp variable, for swapping two characters on wither end of the string ..
void swap (char a, char b)
{
a = a + b;
b = a - b;
a = a - b;
}
use the XOR
- Colin February 16, 2009try this
int a = 'a', b = 'b';
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
a = a^b;
System.out.println(Integer.toBinaryString(a));
b = a^b;
System.out.println(Integer.toBinaryString(b));
a = a^b;
System.out.println(Integer.toBinaryString(a));