Problem of the Day
A new programming or logic puzzle every Mon-Fri

Today's goal is to create a function that reverses a string passed in to it without using any extra space. Can you also do it in under linear runtime?

Comments:

• Eddy - 9 years, 11 months ago

  My solution to the problem in C. I'm assuming that it's okay to call strlen() since otherwise it would be impossible (that I know of) to do it in less than linear runtime since the location of the string terminator is unknown until it's discovered.

  reply permalink

• Kevin Benton - 9 years, 11 months ago

  Assuming that a call to len doesn't require a linear scan. Here is a generator that does it, but it's essentially the same thing that the "reversed" function already does...

  def stringreverser(string):
      for i in reversed(xrange(len(string))):
           yield string[i]
  

  reply permalink

• Anonymous - 9 years, 10 months ago

  Quick C Solution:

  void reverse_str(char *str, int len) {
      for(int i = 0; i < len/2; ++i) {
          str[len] = str[i]; 
          str[i] = str[len-1-i];
          str[len-1-i] = str[len];
      }
      str[len] = '\0';
  }
  

  reply permalink

• Anonymous - 9 years, 9 months ago

  You can be a little tricky by using bitwise operation magic instead of moving the null character around. XOR can be used to twiddle values without the use of a third memory location. It still takes 3 operations.
  A = A ^ B
  B = A ^ B
  A = A ^ B

  reply permalink