Microsoft Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
java Test ' abbbb cd ee '
' abbbb cd ee '
' eedc bb bba '
====================
java Test 'q abbbb xc cd ee q'
'q abbbb xc cd ee q'
'q eedc cx bb bba q'
==========
Summary, there is some flaw.
If the in put contains more than 1 consecutive spaces then there a flaw, please handle, i.e. skip i & j until next char is not white space
public class StringSvc
{
public String reverse(String s)
{
if(s==null)
{
throw new NullPointerException("input string cannot be null");
}
StringBuilder sb=new StringBuilder();
int i=0;
int j=a.length()-1;
while(i<a.length() && j>=0)
{
if(s.charAt(i)==' ')
{
sb.append(' ');
}else{
while(s.charAt(j)==' ')
{
j--;
}
sb.append(s.charAt(j--));
}
i++;
}
return sb.toString();
}
}
public static void main(String[] args)
{
String s= " a b "//should return " b a "
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s=" a"//should return " a"
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s= " ab c"//should return (" cb a")
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
}
}
//Ignore previous solution, I misread the question.
public class StringSvc
{
public String reverse(String s)
{
if(s==null)
{
throw new NullPointerException("input string cannot be null");
}
StringBuilder sb=new StringBuilder();
int i=0;
int j=a.length()-1;
while(i<a.length() && j>=0)
{
if(s.charAt(i)==' ')
{
sb.append(' ');
}else{
while(s.charAt(j)==' ')
{
j--;
}
sb.append(s.charAt(j--));
}
i++;
}
return sb.toString();
}
}
public static void main(String[] args)
{
String s= " a b "//should return " b a "
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s=" a"//should return " a"
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
s= " ab c"//should return (" cb a")
System.out.println("start: " + s);
s=StringSvc.reverse("result: " + s);
}
}
public static String reverseString(String str)
{
char[] arr = str.toCharArray();
char temp;
int i = 0;
int j = str.length() - 1;
while(i < j)
{
while(Character.isWhitespace(arr[i]))
i++;
while(Character.isWhitespace(arr[j]))
j--;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
return new String(arr);
}
public static String reverseString(String str)
{
char[] arr = str.toCharArray();
char temp;
int i = 0;
int j = str.length() - 1;
while(i < j)
{
while(Character.isWhitespace(arr[i]))
i++;
while(Character.isWhitespace(arr[j]))
j--;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
return new String(arr);
}
public static String reverseString(String str)
{
char[] arr = str.toCharArray();
char temp;
int i = 0;
int j = str.length() - 1;
while(i < j)
{
while(Character.isWhitespace(arr[i]))
i++;
while(Character.isWhitespace(arr[j]))
j--;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
return new String(arr);
}
public static String reverseNoSpace(String inputString) {
if(inputString == null) throw new NullPointerException("Input can not be null");
if(inputString.length() == 0) return inputString;
char[] chars = inputString.toCharArray();
StringBuilder sb = new StringBuilder();
int j = 0, i = chars.length - 1;
char temp;
while(i > j) {
if(chars[i] == ' '){
i--;
continue;
}
if(chars[j] == ' '){
j++;
continue;
}
temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
i--;
j++;
}
return sb.append(chars).toString();
}
public static String reverseNoSpace(String inputString) {
if(inputString == null) throw new NullPointerException("Input can not be null");
if(inputString.length() == 0) return inputString;
char[] chars = inputString.toCharArray();
StringBuilder sb = new StringBuilder();
int j = 0, i = chars.length - 1;
char temp;
while(i > j) {
if(chars[i] == ' '){
i--;
continue;
}
if(chars[j] == ' '){
j++;
continue;
}
temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
i--;
j++;
}
return sb.append(chars).toString();
}
public static String reverseNoSpace(String inputString) {
if(inputString == null) throw new NullPointerException("Input can not be null");
if(inputString.length() == 0) return inputString;
char[] chars = inputString.toCharArray();
StringBuilder sb = new StringBuilder();
int j = 0, i = chars.length - 1;
char temp;
while(i > j) {
if(chars[i] == ' '){
i--;
continue;
}
if(chars[j] == ' '){
j++;
continue;
}
temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
i--;
j++;
}
return sb.append(chars).toString();
}}
Java Code:
public static String reverse(String string){
char[] charArray = string.toCharArray();
for(int start=0,end=charArray.length-1; start<end; start++,end--){
while(start<charArray.length && charArray[start]==' '){
start++;
}
while(end>-1 && charArray[end]==' '){
end--;
}
if(start<end){
char temp = charArray[start];
charArray[start] = charArray[end];
charArray[end] = temp;
}
}
return new String(charArray);
}
public class ReverseString {
public static void main(String[] args) {
StringBuffer str = new StringBuffer();
StringBuffer strReverse = new StringBuffer();
str = str.append("This is a red flower");
String[] strArray = str.toString().split("\\s");
for (int i=0;i<strArray.length;i++){
StringBuffer strStore = new StringBuffer();
strStore.append(strArray[i]);
strStore.reverse();
strArray[i] = strStore.toString();
strReverse.append(strArray[i]);
strReverse.append(" ");
}
System.out.println(strReverse);
}
}
this one whill work
public static String reversed2(String test)
{
char[] revers= new char[100]; int j=0;
char[] revers2 = new char[100];
for(int i =(test.length()-1);i>=0;i--)
{
if(test.charAt(i) != ' ')
revers[j++] = test.charAt(i);
}
System.out.println(new String(revers));
j=0;
int k =0;
for(int i =0;i<test.length();i++)
{
if(test.charAt(i)==' ')
{
revers2[j++]=test.charAt(i);
}
else
{
revers2[j++]= revers[k++];
}
}
return new String(revers2);
}
With Python:
""" Reverse string except spaces. A string has mix of alphabets and spaces.
Your task is to reverse the string, but preserve the positions of spaces.
For example, reverse of " a if" is " f ia"."""
def reverse_string(input_str):
return input_str[::-1]
def reverse_string_space_check(input_str):
out_str,low_index = "",0
for id,ch in enumerate(input_str):
if ch == " ":
if low_index == id:
# This check will reduce the number of calls of reverse_string function
# code will work fine even without the if check and just keeping whatever
# in else part
out_str = out_str + " "
else:
out_str = out_str + reverse_string(input_str[low_index:id]) + " "
low_index = id+1
else:
out_str = out_str + reverse_string(input_str[low_index:])+" "
return out_str
With Python:
def reverse_string(input_str):
return input_str[::-1]
def reverse_string_space_check(input_str):
out_str,low_index = "",0
for id,ch in enumerate(input_str):
if ch == " ":
if low_index == id:
# This check will reduce the number of calls of reverse_string function
# code will work fine even without the if check and just keeping whatever
# in else part
out_str = out_str + " "
else:
out_str = out_str + reverse_string(input_str[low_index:id]) + " "
low_index = id+1
else:
out_str = out_str + reverse_string(input_str[low_index:])+" "
return out_str
#include<iostream>
#include<string>
using namespace std;
void ReverseStringWithoutSpaces(string org)
{
char temp;
int len = org.length();
for(int i=0, j=len-1; i<=j;)
{
//cout << "\n INFO: Iteration " << org[i] << " Compare with " << org[j];
if(org[i] != ' ' && org[j] != ' ')
{
temp = org[i];
org[i] = org[j];
org[j] = temp;
i++;
j--;
}
else
{
if(org[i] == ' ')
{
i++;
}
if(org[j] == ' ')
{
j--;
}
}
}
cout << "\n";
cout << "INFO:"<< org;
}
int main()
{
string s= "";
cout << "\n Enter a string for reversal ";
getline(cin, s);
ReverseStringWithoutSpaces(s);
return 0;
}
#include<iostream>
#include<string>
using namespace std;
void ReverseStringWithoutSpaces(string org)
{
char temp;
int len = org.length();
for(int i=0, j=len-1; i<=j;)
{
//cout << "\n INFO: Iteration " << org[i] << " Compare with " << org[j];
if(org[i] != ' ' && org[j] != ' ')
{
temp = org[i];
org[i] = org[j];
org[j] = temp;
i++;
j--;
}
else
{
if(org[i] == ' ')
{
i++;
}
if(org[j] == ' ')
{
j--;
}
}
}
cout << "\n";
cout << "INFO:"<< org;
}
int main()
{
string s= "";
cout << "\n Enter a string for reversal ";
getline(cin, s);
ReverseStringWithoutSpaces(s);
return 0;
}
public static String reverseString(String str)
{
System.out.println(str);
String reversedString = "";
char arr[] = str.toCharArray();
int length = arr.length;
int j = length-1;
for(int i=0; i<length; i++){
if(arr[i] == ' '){
System.out.print(" ");
}else{
if(j>=0)
{
while(arr[j] == ' '){
j--;
}
System.out.print(arr[j]);
j--;
}
}
}
return reversedString;
}
Here's a Java function:
public static String reverseString(String str)
{
System.out.println(str);
String reversedString = "";
char arr[] = str.toCharArray();
int length = arr.length;
int j = length-1;
for(int i=0; i<length; i++){
if(arr[i] == ' '){
System.out.print(" ");
}else{
if(j>=0)
{
while(arr[j] == ' '){
j--;
}
System.out.print(arr[j]);
j--;
}
}
}
return reversedString;
}
Here's a Java code
public static String reverseString(String str)
{
System.out.println(str);
String reversedString = "";
char arr[] = str.toCharArray();
int length = arr.length;
int j = length-1;
for(int i=0; i<length; i++){
if(arr[i] == ' '){
System.out.print(" ");
}else{
if(j>=0)
{
while(arr[j] == ' '){
j--;
}
System.out.print(arr[j]);
j--;
}
}
}
return reversedString;
}
public static String reverseString(String str)
{
char[] arr = str.toCharArray();
char temp;
int i = 0;
int j = str.length() - 1;
while(i < j)
{
while(Character.isWhitespace(arr[i]))
i++;
while(Character.isWhitespace(arr[j]))
j--;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
return new String(arr);
}
public static String reverseString(String str)
{
char[] arr = str.toCharArray();
char temp;
int i = 0;
int j = str.length() - 1;
while(i < j)
{
while(Character.isWhitespace(arr[i]))
i++;
while(Character.isWhitespace(arr[j]))
j--;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
return new String(arr);
}
public class ReverseString {
public static void main(String[] args) {
String input = " the quick brown fox jumps over the lazy dog";
char[] c = input.toCharArray();
int i = 0;
int j = c.length - 1;
while (i <= j) {
while (c[i] == ' ') {
i++;
}
while (c[j] == ' ') {
j--;
}
char k = c[i];
c[i] = c[j];
c[j] = k;
i++;
j--;
}
System.out.println(new String(c));
}
}
In C/C++, the solution code for this could be as follows:
include<string.h>
char* reverseSpecial(char* str){
int len = strlen(str);
char* res = (char*) malloc(sizeof(char)*len);
strcpy(res, str);
char* left = res;
char* right = res + ( len - 1 );
while (left <= right){
Boolean hadSpace = false;
if (*left == ' '){
left++;
hadSpace = true;
}
if (*right == ' '){
right++;
hadSpace = true;
}
if (hadSpace)
continue;
char temp = *left;
*left = *right;
*right = temp;
left++;
right--;
}
return res;
}
The complexity of this algorithm would be O(n/2) = O(n).
- Dinesh Kumar July 22, 2015