Microsoft Interview Question

reverse a sentance

Interview Answer

Anonymous

Feb 6, 2013

This question relies on a trick: 1) reverse the sentence entirely (this will give us the words in correct, reversed order, but the letters in each word will also be reversed) e.g. "i like you" ==> "uoy ekil i" 2) Now, parse through the sentences and reverse each individual word (let's assume the words are separated by spaces only, no punctuation) e.g. "uoy ekil i" ==> "you like i" Code: void reverseWord(string& word) { int size = word.size(); int mid = size/2; char temp; for (int i = 0; i < mid; ++i) { temp = word[i]; word[i] = word[size-i-1]; word[size-i-1] = temp; } } void reverseSentence(string& sent) { // 1. reverse the sentence reverseWord(sent); // 2. reverse each individual word in the sentence int i(0); while (i < sent.size()) { // assume words are separated by spaces, no punctuation int j = i; while (j < sent.size() && sent[j] != ' ') ++j; // reverse current word and replace it in the sentence string word = sent.substr(i, j-i); reverseWord(word); sent.replace(i, j-i, word); // advance i i += j+1; } }

1