Reversing a string

Question

I had this as an interview question, and the interviewer pointed this out. Here's what I wrote:

//C# Syntax here
public string Reverse(string s)
{
    char[] arr = s.ToCharArray();
    int idx = 0;
    int endIdx = s.Length - 1;
    for(; idx < endIdx; ++idx, --endIdx)
    {
        char temp = arr[idx];
        arr[idx] = arr[endIdx];
        arr[endIdx] = temp;
    }
    return arr.ToString();
}

However, the interviewer was asking if I should have changed it to this:

//C# Syntax here
public string Reverse(string s)
{
    char[] arr = s.ToCharArray();
    int idx = 0;
    int endIdx = s.Length - 1;
    while(idx < endIdx)
    {
        char temp = arr[idx];
        arr[idx] = arr[endIdx];
        arr[endIdx] = temp;
        ++idx;
        --endIdx;
    }
    return arr.ToString();
}

Personally, I like the first version, because it puts all of the machinery which controls the loop into the loop statement. One can insert continue or break or return statements into the loop without it breaking things.

However, some programmers dislike putting that stuff into the for, because they think it's being too "clever".

What do you consider best-practice for this?

Answer 1

I would argue against changing it. This seems to be exactly what for-loops were invented for. Also, why not put the initialization in the for loop?

I would have also preferred

for(int idx=0; idx < endIdx; ++idx, --endIdx) {

if only so that I don't have to scan up and down the page looking for the initialization of idx.

Answer 2

I personally would go with the while loop. I'm not against for loops at all, but yours is different than most, and caused me to reread to catch up. I am used to seeing, as I imagine most people are, for loops with an initializer and only one statement to iterate:

for (int i = startValue; i < endValue; i++) {...}

To me, you're already initializing outside of the loop statement (as you said, you prefer to keep things in the loop statement), so you may as well use a while so people expect initialization to be elsewhere. Same with using this construct:

++idx, --endIdx

I'm not expecting this sort of thing in a for loop. I would be more aware something like this might happen in a while loop.

Summary: I personally think the while loop is more readable, because I have certain expectations for for loops. If this is true of the other people who will read/maintain the code, I don't know.

Answer 3

That code looks pretty complex for the trivial task it does.

1. No need to convert the string to a char array. By not calling ToCharArray() you get rid of an extra copy of data.
2. Poorly named variables IMHO. (The convention for index is i.)
3. No need to substract from the end index. (which I prefer to call length as a convention)
4. You shouldn't call ToString(), but use the constructor of string. Your code outputs the typename instead of the reversed string.

Altogether:

public string Reverse( string s )
{
    int length = s.Length;
    char[] reversed = new char[ length ];

    for ( int i = 0; i < length; ++i )
    {
        reversed[ i ] = s[ length - 1 - i ];
    }

    return new string( reversed );
}

And of course, the proper solution would be using Reverse() from IEnumerable. But that wasn't part of the question perhaps.

return new string( s.Reverse().ToArray() );

---

An interesting article which compares different reverse string implementations can be found here.

It's a pity you got referred to here from Programmers.SE, IMHO you do touch some points which are perfectly discussable on Programmers.

Answer 4

The primary consideration when deciding what to put in the for-loop header should be whether the for-loop header conveys the structure of the loop. The three elements (initializer; condition; update) should form a coherent story.

I would express your function like this:

public string Reverse(string s)
{
    char[] arr = s.ToCharArray();
    for (int i = 0, j = s.Length - 1; i < j; ++i, --j)
    {
        char swap = arr[i];
        arr[i] = arr[j];
        arr[j] = swap;
    }
    return arr.ToString();
}

From just the for-loop header, a reasonably experienced programmer can recognize the idiom for stepping two array indices until they meet in the middle. By convention, i and j are array indices; you don't need the …Idx Hungarian suffix.

In comparison, the interviewer's proposal looks unstructured. I feel like I have to mentally decompile it back into the for-loop above to understand what is going on.

I've also renamed temp to swap as a silent "comment".

---

You might be wondering, to what extreme can you pack logic into the for-loop header? In practice, I've never seen more a good for-loop header that involved more than two variables. The probable explanation is that the condition usually involves a binary comparison operator. A third variable would therefore usually be "off-topic" for the header.

Two other guidelines you might want to use are:

• If you can fill in all three parts of the header (initializer; condition; update), then a for-loop is probably appropriate.
• If the loop body surreptitiously updates the iteration variable, such that the header tells a misleading or incomplete story, then the iteration should probably not be done using a for-loop.

Answer 5

@Billy ONeal : I strongly believe that this is a matter of taste. Robert C. Martin states in Clean Code that software developers like to use obfuscated code to "show off" and I agree with him. I also liked to do that until I started to work on my first complex project and I realized that extra mind mappings are not necessary.

That been said, my option will be to use the while() loop; I think that we can go here with the same principle which is applied to a method: the loop should do one thing and one thing only (personal opinion extrapolated from Clean Code). So, if I look at a piece of code after 4 hours of endless debugging, it might feel easier to read (I only formatted the code for easier reading):

     //top-down reading per loop
     while (UnswitchedCharactersExist())
     {
         SwitchCharacters(arr, idx, endIdx);
         IncrementStartIndex();
         DecrementEndIndex();
     }

than:

     //read the initializer, the condition, the code block and go back up for the update
    //after that read the condition, the code block and go back up for the update
    for(; UnswitchedCharactersExist(); IncrementStartIndex(), DecrementEndIndex())
    {
        SwitchCharacters(arr, idx, endIdx); 
    }

My 2 cents on the subject.

Answer 6

Personally, I can't really warm up to either version. I guess that to me, reversing a sequence is so obviously a fold, that anything which doesn't implement it as a fold looks just plain weird.

I would have expected to see something much more like this:

public static string Reverse(this string s)
{
    return s.Aggregate("", (acc, el) => el + acc);
}

I.e. implemented as a left fold.

After all, reversing any sequence (not just strings) is really just the same as

foldl (flip (:)) []

Answer 7

I honestly don't think it matters. For a function this simple, I can think of several similar implementations:

• Have an index to the front and to the back in a for loop
• Have an index to the front and to the back in a while loop
• Have a single index, and calculate the offset from the end of the loop each time round the loop
• All of the possibilities above, but increment/decrement a pointer to char, rather than an index into an array (at least in C, can you do this in C# ?)

And probably several more. I think that the right answer is whatever seems most readable (unless it's EGREGIOUSLY inefficient), and if you think it may be called in an inner loop leave a comment saying (a) don't do that and (b) suggest what changes you'd think about making then, but you'd most likely need to be sure, the function is too simple for your common sense to be much guide about what's faster.

I agree your answer has the potential problems the interviewer described, and his has the potential problems you described. I think either is more than fine, so long as you can see the potential issues, I don't think they can be improved into a single "best" answer.

Answer 8

I was going to write this as a comment but got out of space, so...

In general lines, I agree with Peter Leppert; I think the while is more idiomatic here.

Of course C for syntax allows you to use the first case, and in simple functions I don't think it really matters, but then, C allows you implementing mostly any function in the header of a for loop with an empty body, and that doesn't makes it a good idea ;-).

Your for header was

for(; idx < endIdx; ++idx, --endIdx)

just because you got out of space in the whiteboard. In a computer it would have been more like the following:

for(int idx = 0, endIdx = s.Length - 1; idx < endIdx; ++idx, --endIdx)

Ok, fair enough. Now you find you need another control variable for a new functionality:

for(int idx = 0, endIdx = s.Length - 1, otherVar = FunctionCall(param1, param2); idx < endIdx && otherVar < AnotherFunctionCall(param1); ++idx, --endIdx, otherVar += 5)

What now, uh? It gets ugly very quickly. This doesn't scale up, so, where do you put the line? Character limit in header? Only two control variables?

That's why I would only do the classic for loop:

for (int i = 0; i < maxI; i++)
{
    ...
}

and use a while for everything else.

Anyway, with that question the interviewer was probably trying to see how you think rather than testing your programming capabilities.

Answer 9

Although both for and while are loops and both will work but as a general guideline, for loop is better suited in this case because

• When we know the number of iterations in advance, we should use for loop as it allows initiation, condition and increment to be done in one line.
• Index variable (idx in this case), is more appropiately scoped, why should we increase the scope of idx when this is meant only to be used within the loop.
• Unlike while loop, statements like continue, etc. (if required) can be used without any issues.

While loop should be usually used if we don't know number of iterations in advance.

Answer 10

I think it's important to go back to the context that this was an interview question.

When I interview people, I try to ask questions that don't have one "right" answer - that's more like a trivia test, which is actually fairly useless to me. Instead, I'll ask a question that requires more of an opinion response, watch the candidate, and look for them to apply logical thinking to the problem.

If you can justify that it should be a for loop, and your code is readable, good answer. If you can justify that it should be a while loop, and your code is readable, that's also a good answer. But if you say "it should be a for loop because that's the right way," that's just spewing out dogma and doesn't demonstrate independent thought. It's a less mature answer. Not that it's wrong, but if I'm trying to figure out if you're a starting programmer or an experienced engineer, it's a clue.

By the way, another really good answer is to say "In my code I'd use Reverse() on the array, because it's already tested." An employer generally does not want to pay you to reinvent the wheel, and as an interviewer I'd appreciate the depth of your experience that shows.

Answer 11

All things aside, I believe that these two pieces of code function differently. The first is predecrement, the second is post.

I would agree that for loops make this specific application more obfuscated (not by much, but it is certainly less clear). I recommend using for loops primarily for iterating linearly through a collection with the intent of going from some start to an end, where both of these points are known/fixed before the loop starts.

I think that the for loop is a completely valid approach for something like this though. If you find yourself making a for loop and placing an if statement nearly in the beginning of it, then you may want to consider using a while loop.