I Am Not Myself

Bills.Pay(Developer.Skills).ShouldBeTrue()

Reverse a String with No Loops

    class Program
    {
        static void Main(string[] args)
        {
            var input = "this is a stupid interview question";
            var output = new string(new Stack<char>(input).ToArray());

            Console.WriteLine(output);
            Console.ReadKey();
        }
    }

Was stuck in my head, so I had to get it out.

Zames pointed out in the comments for this post that the title should be “Reverse a String with No Explicit Loops” and he is absolutely correct. There are at least two places in the code that are potentially using using loops behind the scene.

The first is my conversion from string to a stack. In my code I simply pass the constructor of stack the string, but what does the constructor do with that string to make it a stack? Using the Resharper decompiler, we can check.

    public Stack(IEnumerable<T> collection)
    {
      if (collection == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
      ICollection<T> collection1 = collection as ICollection<T>;
      if (collection1 != null)
      {
        int count = collection1.Count;
        this._array = new T[count];
        collection1.CopyTo(this._array, 0);
        this._size = count;
      }
      else
      {
        this._size = 0;
        this._array = new T[4];
        foreach (T obj in collection)
          this.Push(obj);
      }

The specific constructor that I was using simply copies the underlying array if the IEnumerable passed in happens to also be an ICollection otherwise it for loops the collection.

The second place this implementation hides a loop is in the ToArray method.It’s implementation looks like this:

    public T[] ToArray()
    {
      T[] objArray = new T[this._size];
      for (int index = 0; index < this._size; ++index)
        objArray[index] = this._array[this._size - index - 1];
      return objArray;
    }

And we have another loop. Ryan Farley points out in the comments that this puzzle could be accomplished by using the Reverse method found on Array. He provides an example as well. It is interesting that the ToArray method does not use Array.Reverse. Looking at the rest of the stack class, the CopyTo method does use Array.Reverse. I wonder why there is a difference. Both methods create new arrays.

But does Array.Reverse actually have some magic implementation that avoids a loop?

    public static void Reverse(Array array, int index, int length)
    {
      if (Array.TrySZReverse(array, index, length))
        return;
      int index1 = index;
      int index2 = index + length - 1;
      object[] objArray = array as object[];
      if (objArray != null)
      {
        for (; index1 < index2; --index2)
        {
          object obj = objArray[index1];
          objArray[index1] = objArray[index2];
          objArray[index2] = obj;
          ++index1;
        }
      }
      else
      {
        for (; index1 < index2; --index2)
        {
          object obj = array.GetValue(index1);
          array.SetValue(array.GetValue(index2), index1);
          array.SetValue(obj, index2);
          ++index1;
        }
      }
    }

Looks like it uses some loops as well. But what about the TrySZReverse method? What is that about? Class is starting, I’ll have to dig in later.

6 responses to “Reverse a String with No Loops

  1. Ryan Farley October 5, 2011 at 10:44 am

    You can do this using an array too, although a couple more lines than yours 🙂

    originalString = “this is a stupid interview question”;

    char[] charArray = originalString.ToCharArray();
    Array.Reverse(charArray);
    string reversedString = new string(charArray);

    Using the Stack is pretty clever.

  2. Yaz October 5, 2011 at 4:18 pm

    Funny, I had a similar interview question. Try and reverse an array without making a copy of the array or using any of the .Net library.

  3. zames October 6, 2011 at 7:24 am

    Well of all, it should be “Reverse a String with No EXPLICIT Loops”. Just because you hid the loop doesn’t mean it’s not there.

    @Ryan, funny — just yesterday, I was on a job interview. They asked me that exact question and that was my exact answer. (and I got the job)

  4. Thomas Eyde October 6, 2011 at 8:30 am

    Recursion works, too:

    private static string Reverse(string text, int reverseOffset = 1)
    {
    var index = text.Length – reverseOffset;
    if (index >= 0)
    {
    return text[index] + Reverse(text, reverseOffset + 1);
    }
    return “”;
    }

  5. Sam September 8, 2012 at 10:11 pm

    void
    reverse(char *str, int len)
    {
    if (len < 2) {
    return;
    }

    char t = str[0];
    str[0] = str[len – 1];
    str[len – 1] = t;
    reverse(str + 1, len – 2);
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: