In programming problems, we often encounter the requirements of implementing something "in-place".
For example:
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?
**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. In Java, character array can be used instead of string to perform string operations in place.
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, as well as the example problem given at the beginning of this article.
