Microsoft Interview Question
Software Engineer in TestsCountry: United States
Code : Thsi will work for white space
public static void ReverseString()
{
try
{
string str = "this is a pen";
char[] strReverse = str.ToCharArray(0, str.Length);
//char[] str = new char[] { "this is a pen" };
int i = 0;
int j = strReverse.Length - 1;
while (i <= j)
{
char temp = strReverse[i];
strReverse[i] = strReverse[j];
strReverse[j] = temp;
i++;
j--;
Console.WriteLine();
foreach (char strPrint in strReverse)
{
Console.Write(strPrint);
}
}
}
catch(Exception e)
{
Console.WriteLine(e.ToString());
}
}
OutPut:
nhis is a pet
neis is a pht
neps is a iht
nep is asiht
nep ais siht
nep a si siht
nep a si siht
It is very simple to reverse the whole string. But if wang to reverse string and keep every word unchanged, need addition code.
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
// Reverse characters within lpszStart .. lpszEnd.
void ReverseString(char* lpszStart, char* lpszEnd)
{
if (lpszStart >= lpszEnd)
{
return;
}
char* l = lpszStart;
char* r = lpszEnd;
while (l < r)
{
char ch = *l;
*l = *r;
*r = ch;
++l;
--r;
}
}
// Reverse the whole sentence, but every word is not reversed.
void ReverseSentence(char* lpszSentence)
{
if (lpszSentence == NULL)
{
return;
}
char* lpszStart = lpszSentence;
char* lpszEnd = lpszSentence + strlen(lpszSentence) - 1; // Exclude the null terminator.
ReverseString(lpszStart, lpszEnd);
// Then search word and reverse every word.
lpszStart = lpszSentence;
lpszEnd = lpszSentence;
while (true)
{
// Forward search blank character.
while (*lpszEnd != ' ' && *lpszEnd != '\0')
{
++lpszEnd;
}
// Now lpszEnd should point to a blank or null terminator.
ReverseString(lpszStart, lpszEnd-1);
if (*lpszEnd == '\0')
{
break;
}
else
{
lpszStart = ++lpszEnd;
}
}
printf(lpszSentence);
}
void main()
{
char sz[] = "hello world";
ReverseSentence(sz);
getch();
}
what do you mean by
char* lpszStart = lpszSentence;
char* lpszEnd = lpszSentence + strlen(lpszSentence) - 1;
can you explain?
Actually the lpszStart points to the first character while lpszEnd points to the last character (not the null termintaor). Here is a bug, if the sentence's first character is blank, it cannot work, and if there are more than one blanks between each word, also cannot work.
I was asked this question today in MSFT interview.
string rev(string s)
{
string res = "";
string cur = "";
for(int i=s.size()-1;i>=0;i--)
{
if(!isspace(s[i]))
{
cur = cur + s[i];
}
else
{
res = res + s[i]; // inorder to push the space character to the result
for(int j=cur.size()-1;j>=0;j--)
{
res = res + cur[j];
}
cur = "";
}
}
}
#include<iostream>
#include<string.h>
using namespace std;
int find_end(char* arr,int start)
{
int i;
for(i=start; *(arr+i)!=' ' && *(arr+i)!= '\0' ;i++)
return i;
}
void reverse(char* arr,int start, int end)
{
while(start<end)
{
char temp;
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}
int main()
{
char arr[]="Abhishek Gupta";
int start,end;
for(start=0;*(start+arr)!='\0' && start<strlen(arr); )
{
end=find_end(arr,start);
if(start==end)
break;
reverse(arr,start,end-1);
start=end+1;
}
cout<<arr<<endl;
return 0;
}
private static void ReverseString(char[] input)
{
if(input == null || input.Length < 2)
return;
var spaces = new Queue<int>();
spaces.Enqueue(0);
for (int i = 0; i < input.Length; i++)
{
if(input[i] == ' ')
{
spaces.Enqueue(i-1);
spaces.Enqueue(i+1);
}
}
spaces.Enqueue(input.Length - 1);
while (spaces.Count > 0)
{
var left = spaces.Dequeue();
var right = spaces.Dequeue();
while (left < right)
{
var temp = input[left];
input[left] = input[right];
input[right] = temp;
++left;
--right;
}
}
}
You could use split:
public static String reverseWords(String input){
String output = "";
String[] inputList = splitWords(input," ");
for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";
return output;
}
and the implementation of Split:
public static String reverseWords(String input){
String output = "";
String[] inputList = splitWords(input," ");
for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";
return output;
}
You could use split:
public static String reverseWords(String input){
String output = "";
String[] inputList = splitWords(input," ");
for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";
return output;
}
and the implementation of Split:
public static String reverseWords(String input){
String output = "";
String[] inputList = splitWords(input," ");
for(int i = inputList.length-1; i>=0; i--)
output = output + inputList[i] + " ";
return output;
}
public static String[] splitWords(String s, String d){
int count = 0;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i)==d.toCharArray()[0])
count++;
}
String[] output = new String[count+1];
int occurence = 0;
int first = 0;
int last = 0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)==d.toCharArray()[0] && occurence < count){
last = i;
output[occurence] = s.substring(first, last);
first = i + 1;
occurence++;
}
else if(occurence == count){
output[occurence] = s.substring(i,s.length());
break;
}
}
return output;
}
public void ReverseSentence(string input)
{
if (string.IsNullOrEmpty(input))
throw new Exception("String Empty");
char[] cArray = input.ToCharArray();
int i = 0;
int j = 0;
while (true)
{
while (j < cArray.Length && cArray[j] == ' ')
j++;
if (j == cArray.Length)
break;
i = j;
while (j < cArray.Length && cArray[j] != ' ')
j++;
ReverseWord(i, j - 1, cArray);
}
}
public void ReverseWord(int start, int end, char[] inputWord)
{
char temp;
while (start < end)
{
temp = inputWord[start];
inputWord[start] = inputWord[end];
inputWord[end] = temp;
start++;
end--;
}
}
in-place version:
void word_reverse()
{
string str = " a Hello World! another_word! ab c ";
char[] array = str.ToCharArray();
int word_start = 0;
int word_end = 0;
for (word_end = 0; word_end < array.Length; word_end++)
{
if (str[word_end] == ' ')
{
Reverse(ref array, word_start, word_end - 1);
word_start = word_end + 1;
continue;
}
else if (word_end == array.Length - 1 && array[word_end] != ' ')
{
Reverse(ref array, word_start, word_end);
break;
}
}
}
void Reverse(ref char[] array, int start, int end)
{
while (end >= start)
{
char tmp = array[end];
array[end] = array[start];
array[start] = tmp;
end--;
start++;
}
}
You don't have to worry abt spaces. Just reverse the entire string.
- Say March 06, 2012