29

Reverse words in a string (words are separated by one or more spaces). Now do it in-place.

What does in-place mean?

NibblyPig
  • 51,118
  • 72
  • 200
  • 356
  • 1
    Check out this thread for tips on how to do it in C/C++: http://stackoverflow.com/questions/198199/how-do-you-reverse-a-string-in-place-in-c-or-c – Mia Clarke May 06 '10 at 09:15
  • 2
    @Banang: although this is answering a different question (reversing a string, rather than the words in a string, e.g. "dog bites man" becomes "man bites dog" rather than "nam setib god") – Simon Nickerson May 06 '10 at 09:21
  • http://stackoverflow.com/questions/16585507/sorting-in-place may explain it. – Yuan Wen Apr 05 '16 at 06:27

3 Answers3

40

In-place means that you should update the original string rather than creating a new one.

Depending on the language/framework that you're using this could be impossible. (For example, strings are immutable in .NET and Java, so it would be impossible to perform an in-place update of a string without resorting to some evil hacks.)

LukeH
  • 263,068
  • 57
  • 365
  • 409
10

In-place algorithms can only use O(1) extra space, essentially. Array reversal (essentially what the interview question boils down to) is a classic example. The following is taken from Wikipedia:

Suppose we want to reverse an array of n items. One simple way to do this is:

function reverse(a[0..n])
    allocate b[0..n]
    for i from 0 to n
       b[n - i] = a[i]
    return b

Unfortunately, this requires O(n) extra space to create the array b, and allocation is often a slow operation. If we no longer need a, we can instead overwrite it with its own reversal using this in-place algorithm:

function reverse-in-place(a[0..n])
    for i from 0 to floor(n/2)
       swap(a[i], a[n-i])

Sometimes doing something in-place is VERY HARD. A classic example is general non-square matrix transposition.

See also

polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
  • is non-square matrix transposition even possible to do in-place? Surely it requires different dimensions on each side. a 2x3 array becoming a 3x2 array? – penguat May 06 '10 at 09:32
  • 2
    @penguat: the matrix would be stored in a 1D array of 6 elements. Transposition switches from row-major to column-major and vice versa, e.g. `ABCDEF` to `ADBECF`. – polygenelubricants May 06 '10 at 09:45
  • Ah. Yes, I see now how an in-place transposition could be tricky, and require an awful lot of thinking before implementation. – penguat May 06 '10 at 10:55
7

You should change the content of the original string to the reverse without using a temporary storage variable to hold the string.

Charles
  • 2,615
  • 3
  • 29
  • 35