ReverseString, a C# interview-question

Question

I had an interview question that asked me for my 'feedback' on a piece of code a junior programmer wrote. They hinted there may be a problem and said it will be used heavily on large strings.

public string ReverseString(string sz)
{
    string result = string.Empty;
    for(int i = sz.Length-1; i>=0; i--)
    {
      result += sz[i]
    }
    return result;
}

I couldn't spot it. I saw no problems whatsoever. In hindsight I could have said the user should resize but it looks like C# doesn't have a resize (i am a C++ guy).

I ended up writing things like use an iterator if its possible, [x] in containers could not be random access so it may be slow. and misc things. But I definitely said I never had to optimize C# code so my thinking may have not failed me on the interview.

I wanted to know, what is the problem with this code, do you guys see it?

-edit-

I changed this into a wiki because there can be several right answers. Also i am so glad i explicitly said i never had to optimize a C# program and mentioned the misc other things. Oops. I always thought C# didnt have any performance problems with these type of things. oops.

Answer 1

Since strings are immutable, each += statement will create a new string by copying the string in the last step, along with the single character to form a new string. Effectively, this will be an O(n²) algorithm instead of O(n).

A faster way would be (O(n)):

// pseudocode:
static string ReverseString(string input) {
    char[] buf = new char[input.Length];
    for(int i = 0; i < buf.Length; ++i)
       buf[i] = input[input.Length - i - 1];
    return new string(buf);
}

Answer 2

Most importantly? That will suck performance wise - it has to create lots of strings (one per character). The simplest way is something like:

public static string Reverse(string sz) // ideal for an extension method
{
    if (string.IsNullOrEmpty(sz) || sz.Length == 1) return sz;
    char[] chars = sz.ToCharArray();
    Array.Reverse(chars);
    return new string(chars);
}

Answer 3

The problem is that string concatenations are expensive to do as strings are immutable in C#. The example given will create a new string one character longer each iteration which is very inefficient. To avoid this you should use the StringBuilder class instead like so:

public string ReverseString(string sz)
{
    var builder = new StringBuilder(sz.Length);
    for(int i = sz.Length-1; i>=0; i--)
    {
      builder.Append(sz[i]);
    }
    return builder.ToString();
}

The StringBuilder is written specifically for scenarios like this as it gives you the ability to concatenate strings without the drawback of excessive memory allocation.

You will notice I have provided the StringBuilder with an initial capacity which you don't often see. As you know the length of the result to begin with, this removes needless memory allocations.

What normally happens is it allocates an amount of memory to the StringBuilder (default 16 characters). Once the contents attempts to exceed that capacity it doubles (I think) its own capactity and carries on. This is much better than allocating memory each time as would happen with normal strings, but if you can avoid this as well it's even better.

Answer 4

Better way to tackle it would be to use a StringBuilder, since it is not immutable you won't get the terrible object generation behavior that you would get above. In .net all strings are immutable, which means that the += operator there will create a new object each time it is hit. StringBuilder uses an internal buffer, so the reversal could be done in the buffer w/ no extra object allocations.

Answer 5

You should use the StringBuilder class to create your resulting string. A string is immutable so when you append a string in each interation of the loop, a new string has to be created, which isn't very efficient.

Answer 6

A few comments on the answers given so far:

• Every single one of them (so far!) will fail on surrogate pairs and combining characters. Oh the joys of Unicode. Reversing a string isn't the same as reversing a sequence of chars.
• I like Marc's optimisation for null, empty, and single character inputs. In particular, not only does this get the right answer quickly, but it also handles null (which none of the other answers do)
• I originally thought that ToCharArray followed by Array.Reverse would be the fastest, but it does create one "garbage" copy.
• The StringBuilder solution creates a single string (not char array) and manipulates that until you call ToString. There's no extra copying involved... but there's a lot more work maintaining lengths etc.

Which is the more efficient solution? Well, I'd have to benchmark it to have any idea at all - but even so that's not going to tell the whole story. Are you using this in a situation with high memory pressure, where extra garbage is a real pain? How fast is your memory vs your CPU, etc?

As ever, readability is usually king - and it doesn't get much better than Marc's answer on that front. In particular, there's no room for an off-by-one error, whereas I'd have to actually put some thought into validating the other answers. I don't like thinking. It hurts my brain, so I try not to do it very often. Using the built-in Array.Reverse sounds much better to me. (Okay, so it still fails on surrogates etc, but hey...)

Answer 7

You can do this in .NET 3.5 instead:

    public static string Reverse(this string s)
    {
        return new String((s.ToCharArray().Reverse()).ToArray());
    }