Microsoft Interview Question for Software Engineer Interns


Country: United States
Interview Type: In-Person




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

The idea is to first reverse the whole sentence, letter by letter, and then reverse each word. e.g.,

INPUT: "This is a sentence"
->Reverse sentence: "ecnetnes a si sihT"
->Reverse words: "sentence a is This", which is the expected output

Simple C code:

//Reverse a word
void ReverseWord(char* word, int n){
	char tmp;
	for(int i = 0; i< n/2; ++i){
		tmp = word[i];
		word[i] = word[n-i-1];
		word[n-i-1] = tmp;
	}
}

void ReverseString(char* str, int n){
	//Reverse the whole string first
	ReverseWord(str,n);
	int i = 0;
	for(int j = 0; j < n+1; ++j){
		if(str[j] == ' ' || str[j] == '.' || str[j] == '\0'){
			ReverseWord(str+i, j-i);
			while(str[++j] == ' '); // Skip continous white spaces
			i = j;
		}
	}
}


int main()
{
	char str[30] = "This is a sentence.";

	ReverseString(str,18);

	printf("%s",str);

	return 0;
}

- Zerofans October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

Quick one-liner in JavaScript.
Thinking it should be O(n) as most of these built-in JS functions are either O(1) or O(n), but would have to check to make sure.

function reverseSentence(sentence) {
  // 1: remove period if present
  // 2: convert to array by separating with ' '
  // 3: reverse array
  // 4: convert to string by joining array elements with ' '
  // 5: append period if present
  return sentence.replace('.', '').split(' ').reverse().join(' ') + ((sentence.indexOf('.') !== -1) && '.' || '');
}

- borg6783 October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice job! This is the cleanest algorithm I have seen so far. JS can be handy sometimes.

- dark_knight October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Simple Java Solution

public String reverseTheWords(String str){
        if (str == null || str.isEmpty())
            throw new IllegalArgumentException("String can't be null or empty");
        boolean hasPeriod = str.endsWith(".");
        if (hasPeriod) str = str.substring(0, str.length()-1);
        String[] array = str.split(" ");
        int upperBound = array.length - 1;
        StringBuilder sb = new StringBuilder("");
        for (int i = upperBound; i > 0; i--){
            sb.append(array[i] + " ");
        }
        sb.append(array[0]);
        return (hasPeriod)? sb.append(".").toString() : sb.toString();
    }

- Upendra Dhakal October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if There is a dot, reduce size of string by 1.
Reverse the whole string.
For each x to x+n, s.t. x+n+1 is space or a dot, replace by swapping n/2 characters.
done.
O(2n) => O (kn) => O(n)

- Joshi of Vatsa October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is python implementation.

def ReverseString(inputstring):
        if inputstring is None:
            return

        hasperiod = False
        if inputstring[-1] == ".":
            hasperiod = True
            inputstring = mystring[:-1]

        words = inputstring.split(" ")
        words.reverse()
        outputstring = " ".join(words)
        if hasperiod:
            outputstring +=  "."

        return outputstring

It has time complexity of O(length if input string).

- GNA October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String reverse(String input) {

        if(input == null || input.isEmpty())
                   throw IllegalArgumentException ("Invalid Input");

       if(input.length == 1)
                   return input;

      String [] splitted = input.split(" ");
      boolean containsPeriod = false;

      if(splitted[splitted.size()].contains(".")) {
               splitted[splitted.size()] = splitted[splitted.size()].replace(".", "");  
               containsPeriod = true;
      }
 
      StringBuilder result = new StringBuilder();
	
      for(int i = splitted.size(); i > 0; i--) {
		result = result  + splitted[i] + "  ";				
      }

      if(containsPeriod == true) {
              result = result + ".";
      }

      return result;
   }

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

Hey,

Was also looking in from the java side, this pretty close to what I got, however there's a couple of things we could maybe improve:

- I don't think you need to explicitly check if the length is 1 and return; doesn't make any substantial runtime difference to the function.

- The for loop, you need to check

for(int i = splitted.size(); i >= 0; i--) {

otherwise you miss the first (or last in the reversed string) word.

- Since you used a StringBuilder, you'd have to

return result.toString();

otherwise I think it would return a StringBuilder and not a String (I think (: )

This is the code that I had:

String reverse (String sent) {
    //check empty or null
    if (sent == null || sent.isEmpty() ) {
        // Just chose to return an empty string       
        return "";
    }

    String[] splitS = sent.split(" ");

    // Period check
    if ( sent.indexOf(".") > -1) {
        splitS[splitS.length-1] = splitS[splitS.length-1].replace(".", "");

        // Add the period to the first word since that would be last in the new string
        splitS[0] += ".";
    }

    StringBuilder revString = new StringBuilder();

    for( int i = splitS.length - 1; i > -1; i-- ) {
        revString.append(splitS[i]);
        revString.append(" ");
    }

    return revString.toString();
}

Do let me know if I maybe overlooked something!

- ammarj965 October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

c++, O(n^2): Loop is O(n) and substr is O(n)

string reveseWords(string inStr) {
	string outStr;
	int start, end;
	bool period;

	outStr = "";
	end = inStr.size();
	if (end == 0) return outStr;

	end--;
	if (inStr[end] == '.') {
		period = true;
		end--;
	} else {
		period = false;
	}

	for (start = end; start >= 0; start--) {
		if (inStr[start] == ' ') {
			outStr.append(inStr.substr(start + 1, end - start));
			outStr.append(" ");
			end = start - 1;
		}
	}
	outStr.append(inStr.substr(start + 1, end - start));
	if (period == true) outStr.append(".");
	
	return outStr;
}

- kyduke October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

fdsafawer1

- fdsafewqrewq October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple

- #Robot October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript code for this:

function wordRevers(str){
        return str.split(" ").reverse().join(" ")
    }
    console.log(wordRevers("This is a sentence"))

- javascript Novice October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String reverseTheWords(String str){
        if (str == null || str.isEmpty())
            throw new IllegalArgumentException("String can't be null or empty");
        boolean hasPeriod = str.endsWith(".");
        if (hasPeriod) str = str.substring(0, str.length()-1);
        String[] array = str.split(" ");
        int upperBound = array.length - 1;
        StringBuilder sb = new StringBuilder("");
        for (int i = upperBound; i > 0; i--){
            sb.append(array[i] + " ");
        }
        sb.append(array[0]);
        return (hasPeriod)? sb.append(".").toString() : sb.toString();
    }

- Upendra Dhakal October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mi code in C/C++ for this:

char *reverse(const char *str){
	int len = strlen(str);
	char* cpy = (char*)malloc(sizeof(char)*len);
	strcpy(cpy, str);
	char* ptr1;
	char* ptr2 = ptr1 = cpy;
	char temp;

	ptr2 = ptr2 + (len - 1);
	if (*ptr2 == '.')	//ignore '.' (doesn't reverse it)
		ptr2--;

	while (ptr1 <= ptr2){	//reverse str
		temp = *ptr1;
		*ptr1 = *ptr2;
		*ptr2 = temp;
		ptr1++;
		ptr2--;
	}

	ptr1 = ptr2 = cpy;
	while (*ptr2){
		char *auxPtr;
		while (*ptr2 != ' ' && *ptr2 && *ptr2 != '.')
			ptr2++;
		auxPtr = ptr2;
		ptr2--;

		while (ptr1 <= ptr2){	//reverse word
			temp = *ptr1;
			*ptr1 = *ptr2;
			*ptr2 = temp;
			ptr1++;
			ptr2--;
		}
		ptr2 = auxPtr;
		if (*auxPtr)	//if doesn't point to '\0'
			ptr2++;
		ptr1 = ptr2;
	}
	return cpy;
}

As it copy the str and then reverse it in time n/2, we have n+n/2, at every word looks for the next ' ' (tokenizing words every loop) visits every member of the str, and with every token (word) reverse them, the worst case would be then when the sentence has only words of lenght one, having n/2 words and n/2 spaces, in that case it would waste 5 instructios movin' in the same place every letter, so we'll have 5(n/2), then it would do it on n/2(searching for ' ' skipping them) + 5(n/2) = 3n, so final time would be 4n+n/2, so the algorithm would be O(n), I think.

- Alder Matus October 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In python, this should run in O(n) time because the built in functions run in O(n) or O(1)

def ReverseSentence(input_sentence=None):
	# If no input, return
	if input_sentence is None:
		return
	# Does it have a period at the end of the sentence?
	if input_sentence[len(input_sentence)-1:len(input_sentence)] == '.':
		input_sentence = input_sentence[0:len(input_sentence)-1]
		period = '.'
	else:
		period = ''

	# Reverse the sentence
	input_sentence = input_sentence.split(' ')
	output = ' '.join(list(reversed(input_sentence)))
	print output+period

	# Time complexity: n-time

input_sentence = 'This is a sentence'
ReverseSentence(input_sentence) 
input_sentence = 'This is a sentence.'
ReverseSentence(input_sentence)

- mh October 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are good solutions mentioned here but most are in O(n^2)
Following is an approach which works in O(n) time.
- Create a new char array
- Split the string with spaces, this results in String[]
- Now, starting from last element we copy each char from String[] to char[], we skip the '.' char and then add a space char.
- If '.' exists we add it to the last element of char array.
- Finally, we convert the char array to string and return it.
So, T = O(n) and S = O(n)

- justaguy October 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String reverse(String str)
        {
            bool havePoint = false; 

            string[] words = str.Split(' ', '.');

            String newString = "";

            for (int i = words.Length - 1; i >= 0; i--) {
                newString += words[i];
            }

            if (words[words.Length - 1].Contains("."))
                havePoint = true;

            if (havePoint)
                newString += ".";

            return newString;

}

- Cristi October 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n). C# solution

public static string Reverse(string str)
        {
            return string.Join(" ", str.Split().Reverse()) + (str.EndsWith(".") ? "." : "");

        }

- neelskye October 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn not take care of the "." at the end of the original sentence. I would do this tiny modification:

return string.Join(" ", str.Substring(0,str.Length-1).Split().Reverse()) + (str.EndsWith(".") ? "." : "");

Other than that, it's a really nice algorithm! ^_^

- DavidG October 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DemoRevWord {

public static void main(String arg[]){
String str="this is a sentence";
String str1[]=str.split(" ");
String finalstr=" ";
int l = str1.length-1;
for(int i=l;i>=0;--i)
{
finalstr+=str1[i]+" ";
}
System.out.println(finalstr);
}
}

- Akhilesh kashyap October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DemoRevWord {

public static void main(String arg[]){
String str="this is a line";
String str1[]=str.split(" ");
String finalstr=" ";
int l = str1.length-1;
for(int i=l;i>=0;--i)
{
finalstr+=str1[i]+" ";
}
System.out.println(finalstr);
}
}

- Akhilesh kashyap October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sentence: " It is a beautiful day."
My idea is: Store the words in an ArrayList.
words= {It, is, a beautiful, day}
Use StringBuilder to append in front while going thorigh each word in ArrayList.
p = p.append(0, word);
Append . to p in the end.

- Anonymous November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Reverse()
        {
            List<string> l = new List<string>();
            string str = "This is a sentence";
            foreach (string s in str.Split(' '))
            {
                l.Add(s);
            }

            for (int i = l.Count-1; i >= 0; i--)
            {
                Console.WriteLine(l[i]);
            }
        }

- Srinivas May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Reverse()
{List<string> l = new List<string>();string str = "This is a sentence";foreach (string s in str.Split(' ')){l.Add(s);}for (int i = l.Count-1; i >= 0; i--){Console.WriteLine(l[i]);}}

- Anonymous May 03, 2016 | 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