Interview Question

Senior Software Design Engineer Interview Seattle, WA

Reverse a sentence but keep the individual words in the

  same order
Answer

Interview Answer

2 Answers

0

Complexity is O(n).
Note. string is immutable object so I used stringbuilder for inplace reversal.

class ReverseWords
    {

        public static void Reverse(ref StringBuilder strInput)
        {
            //Reverse the entire sentence
            Reverse(ref strInput, 0, strInput.Length - 1);

            //Reverse the words withing reverse sentence
            int startIndex = 0;
            int endIndex = 0;
            while (endIndex < strInput.Length)
            {
                if (endIndex == strInput.Length - 1)
                {
                    Reverse(ref strInput, startIndex, endIndex);
                    startIndex = endIndex + 1;
                }
                else if (strInput[endIndex] == ' ')
                {
                    Reverse(ref strInput, startIndex, endIndex - 1);
                    startIndex = endIndex + 1;
                }
                endIndex++;
            }
        }

        private static void Reverse(ref StringBuilder strInput, int startIndex, int endIndex)
        {
            for (int i = startIndex; i <= (endIndex + startIndex)/ 2; i++)
            {
                char temp = strInput[i];
                strInput[i] = strInput[endIndex + startIndex - i];
                strInput[endIndex + startIndex - i] = temp;
            }
        }
    }

Praveen Chettypally on Jan 30, 2011
0

What data structure solution has order 1 look up and is always sorted?

Anon on Feb 18, 2011

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up