Microsoft Interview Question
Software Engineer InternsCountry: United States
Interview Type: In-Person
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) && '.' || '');
}
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();
}
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).
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;
}
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!
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;
}
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();
}
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.
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)
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)
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;
}
O(n). C# solution
public static string Reverse(string str)
{
return string.Join(" ", str.Split().Reverse()) + (str.EndsWith(".") ? "." : "");
}
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:
- Zerofans October 18, 2015