What does "in-place" mean?

Question

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

What does in-place mean?

Answer 1

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.)

Answer 2

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

• In-place algorithm
• In-place matrix transposition

Answer 3

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