Microsoft Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

to reverse the string in O(n) time and with out additional space complexity ??

IN 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 ??

- king October 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for 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.

:)

- xmagics October 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correct :)

- Anonymous November 24, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
            }
        }

- Anonymous October 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this one gets the wrong result.

- Anonymous June 30, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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';
}

- Taesung October 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Taesung October 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Explain your algorithm first. Just giving code is useless.

- AARGH October 28, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sure,
It makes 'My name is Amit Agarwal' -> 'ym eman si timA lawragA'
And prints them reversely.

- Taesung October 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

shall we use cstring? use strtok() to split the whole string into several tokens first, then reverset the order

- elfenlied November 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

write a reverse function for a string
and send every string in the sentence to reverse function
and then reverse the whole sentence

- srujan November 07, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. reverse the whole string in O(n)
2. traverse the string and store the index of the spaces in an array in O(n)
3. Now reverse the string between every 2 consecutive indexes.(O(n))

please let me know if it will work ???

- saurabhroongta2 November 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;		
}

- Abhishek December 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main(void)
{
char str[100],*rev,temp[50];
gets(&str);

rev = strrev(str);
rev[strlen(rev)] = ' ';

int i=0,j=0;
while(rev[i] != '\0')
{
if(rev[i] != ' ')
{
temp[j] = rev[i];
j++;
}
else
{
temp[j] = '\0';
j=0;
printf("%s",strrev(temp));
printf(" ");
}
i++;
}
return 0;
}

- vinay December 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/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++;
}}

}}

- sachin February 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
            }
        }
    }

- Anonymous February 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- mohit January 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

we just have to use the first part of the algo for the given question.
i have given an extended algo for possible question.

- mohit January 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
main()
{
char *s="hello world";
char *s1,*s2;
int k,i;
k=strlen(s)-1;
s=s+k;
while(k!=-1)
{
*s1=*s;
printf("%c",*s1);
s1++;
s--;
k--;
}
getch();
}

- Anonymous April 02, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More