An Interview Question

Here's a great interview question, well, assuming that you're interviewing a software engineer.

What is the easiest way to determine if a given string is the rotation of another string?

First, I guess there could be some question of what rotation of a string even is. If you were to take letters off the end of the string and stick them on the beginning one at a time, you would be making a rotation of the string. For example, the following are all rotations of the string "obfuscate"

ateobfusc

fuscateob

scateobfu

eobfuscat

There are lots of ways you could try to determine if one string is a rotation of another. You could easily rule out some strings by checking to make sure the lengths are the same first. Then you could maybe start at the first character and attempt a character-by-character comparison and move your pointer back to the front if you reach the end...or some other complicated algorithm.

But there's a really easy way to tell if a string is a rotation of another string. Engineers who value the simplest way to solve a problem will do it this way.

Stick one of the strings together with a copy of itself and then see if the other string appears inside that new string. Like this, using the examples above:

ateobfuscateobfusc

fuscateobfuscateob

scateobfuscateobfu

eobfuscateobfuscat

You still need a sanity check for length, because you can find "ob" inside of "fuscateobfuscateob" but that doesn't make it a rotation.

Here it is as a JavaScript function.

function isRotation(a, b) {
    return (a.length === b.length) && ((a + a).indexOf(b) !== -1)
}

That's all there is to it. You can do it in one line. I think it's a good question.

Amphibian.com comic for August 20, 2014