Abstract Confusions

Complexity is not a cause of confusion. It is a result of it.

Interesting Interview Question: Check if a String is Rotated

Found an interesting interview question at Stackoverflow.

How will you find a string ‘a’ is a rotated string of some string ‘b’ (say, or some other reference string, but known)?

Example:
a= ‘stackoverflow’, b = ‘overflowstack’, then ‘a’ is rotated string of ‘b’.

a= ‘stackoverflow’, b= ‘flowrevostack’, then ‘a’ is NOT rotated string of ‘b’.

What makes this interview question interesting is seemingly difficult question (check Jon Skeet’s answer, he admitted the actual answer is simple and elegant).

Algorithm: Is the string rotated?

  • Assert both strings S1 and S2 are of same length. If not, return False.
  • Check and see if S1 is a substring of S2+S2. If so, return True, else return False.
And a two line Python code sample of this (Bias alert: I am learning Python, so you will get only Python example):
>>> def isRtn(s1,s2):
        return len(s1)==len(s2) and s1 in 2*s2

>>> a="stackoverflow"
>>> b="overflowstack"

>>> isRtn(a,b)
True

>>> b="helloverflow"

>>> isRtn(a,b)
False

It is the elegance of solution which makes the interview question interesting. And the Python implementation is icing on the cake.

One response to “Interesting Interview Question: Check if a String is Rotated

  1. Pingback: Tweets that mention Interesting Interview Question: Check if a String is Rotated String of Other String « Abstract Confusions -- Topsy.com

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: