Microsoft Interview Question
Software Engineer / Developersfor in place -
use two indexes
P1 -> at the beginning of the string
P2 -> at the end of the string
now swap the corresponding elements
m move P1 forward and P2 backword
now the string will look like
"lawragA timA si eman yM "
now traverse the string and on finding the " " space print the string or replace ( for replacing complexity will break O(n*(no. of words in string))) or O(nk) but remains ~~ O(n) for small strings. space complexity is constant.
:)
The solution below is in C# but could be easily adapted to other languages...
public void reverseWordOrder(ref char[] strChrArray)
{
reverseString(ref strChrArray, 0, strChrArray.Length);
int lastIndex = 0;
for (int i = 0; i < strChrArray.Length; i++)
{
if (strChrArray[i].Equals(' '))
{
reverseString(ref strChrArray, lastIndex, i);
lastIndex = i + 1;
}
}
reverseString(ref strChrArray, lastIndex, strChrArray.Length);
}
public void reverseString(ref char[] strToReverse, int startIndex, int endIndex)
{
int halfStrLen = (endIndex - startIndex) / 2 - 1;
char tmpChar;
for (int i = 0; i <= halfStrLen; i++)
{
tmpChar = strToReverse[startIndex + i];
strToReverse[startIndex + i] = strToReverse[endIndex - 1 - i];
strToReverse[endIndex - 1 - i] = tmpChar;
}
}
int main(int argc, char* argv[])
{
char buffer[100];
int count = 0;
for(int i=1;i<argc;i++)
{
while( (buffer[count++] = *(argv[i]++)) != '\0');
buffer[count - 1] = ' ';
}
buffer[count++] = '\0';
char *pBuf = buffer;
char *pSt, *pEd;
char cTemp;
pSt = pBuf;
count = 0;
while(*pBuf != '\0')
{
if(*pBuf == ' ')
{
pEd = pBuf - 1;
while(pEd != pSt)
{
cTemp = *pSt;
*pSt = *pEd;
*pEd = cTemp;
if(pSt+1 == pEd)
break;
pSt++; pEd--;
}
pSt = pBuf + 1;
}
pBuf++;
count++;
}
for(int i = count; i>= 0; i--)
cout << buffer[i];
cout << '\n';
}
I am not sure about this but the result is correct
It would be O(2n) or O(3n) including printing. So, it is O(n)
If you think I am wrong, please reply
#include "stdafx.h"
bool Reverse(char* szData);
bool ReverseWord(char* szWord, int nCount);
int _tmain(int argc, _TCHAR* argv[])
{
char szData[1024] = {0};
printf("Enter the string\n");
gets(szData);
bool bRet = Reverse(szData);
if(bRet)
{
printf("%s", szData);
}
else
{
printf("Failed to reverse");
}
return 0;
}
bool Reverse(char* szData)
{
bool bRet = true;
char* szTemp = szData;
int nCount = 0;
if(szData)
{
while(*szData != '\0')
{
while((*szData != ' ') && (*szData != '\0'))
{
szData++;
nCount++;
}
if(false == ReverseWord(szTemp, nCount ))
{
bRet = false;
}
while(*szData == ' ')
{
szData++;
}
szTemp = szData;
nCount = 0;
}
}
return bRet;
}
bool ReverseWord(char* szWord, int nCount)
{
bool bRet = true;
char szSwap = '\0';
if(szWord)
{
for(int nIndex = 0; nIndex <(nCount/2); nIndex++)
{
szSwap = *(szWord + nIndex);
*(szWord + nIndex) = *(szWord + nCount - nIndex - 1);
*(szWord + nCount - nIndex - 1) = szSwap;
}
}
else
{
bRet = false;
}
return bRet;
}
/Following code will consider the extra white spaces found in the string
void ReverseWord(string &s){{
char *p1,*p2;
p1 = p2 = &s[0];
while(*p2 != '\0'){{
//space or '\0' suggests new word is found
if(*p2 == ' ' || *(p2 +1) == '\0'){{
//Contains first and last pointer of a word in string
char *t1,*t2;
t1 = p1;
//Check for last word in the string
if(*(p2 + 1) == '\0')
t2= p2;
else
t2 = p2-1;
int count = (t2 - t1) / 2;
//Reverse the word in the string
while(count--){
char temp(*t1);
*t1 = *t2;
*t2 = temp;
t1++;t2--;
}}
//Skip the white spaces
while(*(p2) == ' '){
p2++;
}}
//make p1 , p2 point to first char of next word in the string
p1=p2;
}}
p2++;
}}
}}
A c# soln.
public static class Strings
{
public static string ReverseWords(string text)
{
char[] arr = text.ToArray();
int start = 0;
int cur=0;
while (cur < arr.Length)
{
while (cur < arr.Length && arr[cur] == ' ') cur++;
start = cur;
while (cur < arr.Length && arr[cur] != ' ') cur++;
int end = cur - 1;
ReverseStringChars(arr, start, end);
cur++;
}
return new string(arr);
}
private static void ReverseStringChars(char[] chars, int start, int end)
{
for (int i = start; i <= start + (end - start) / 2; i++)
{
char temp = chars[i];
chars[i] = chars[end - (i - start)];
chars[end - (i - start)] = temp;
}
}
}
let input string be “i like this program very much”.
Algorithm:
1) Reverse the individual words, we get the below string.
"i ekil siht margorp yrev hcum"
2) Reverse the whole string from start to end and you get the desired output.
"much very program this like i"
#include<stdio.h>
/* function prototype for utility function to
reverse a string from begin to end */
void reverse(char *begin, char *end);
/*Function to reverse words*/
void reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */
/*STEP 1 of the above algorithm */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */
/*STEP 2 of the above algorithm */
reverse(s, temp-1);
}
/* UTILITY FUNCTIONS */
/*Function to reverse any sequence starting with pointer
begin and ending with pointer end */
void reverse(char *begin, char *end)
{
char temp;
while (begin < end)
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}
/* Driver function to test above functions */
int main()
{
char s[] = "i like this program very much";
char *temp = s;
reverseWords(s);
printf("%s", s);
getchar();
return 0;
}
to reverse the string in O(n) time and with out additional space complexity ??
- king October 20, 2009IN SPACE - if you mean what ?? the string itself has to be reversed in place or without using the extra space i.e just to display and the original string remains same ??