1

I have a problem from Cracking the coding interview book. Description is the following: "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?"

I can't understand what is meant by "in place" in the last sentence. How is it "in place"?

Improve this question
2
  • 3
    It means "without creating a second copy of the image in memory". Doing programming tasks "in place" is often more difficult for the programmer, but uses less computer resources. en.wikipedia.org/wiki/In-place_algorithm
    – James
    Commented Aug 31, 2015 at 16:31
  • @James, good answer. I would accept it if you consider moving in from comments to answers
    – Olena Horal
    Commented Sep 1, 2015 at 8:34

2 Answers 2

Reset to default
2

In-place refers to the use of an in-place algorithm.

Imagine that each of your pixels is printed on the top of a cube - maybe a child's wooden block. All the cubes are laid out on the floor to create your image. Now you want to rotate the image by 90 degrees.

out-of-place algorithm -> For each block, create a copy of the block and put it its new position on the floor in a different room.

in-place algorithm -> Pick up block A from its original position and figure out where it needs to be moved. Pick up block B from that position and replace it with the block A. Figure out where block B needs to go and remove block C from that location. If the block you're holding ever goes in a vacant spot, then pick up a block that hasn't been moved yet and continue. Continue until the entire original image is rotated.

For the programmer, the out-of-place algorithm is easier to create and works fine for many situations. The problem with the out-of-place algorithm is that the computer memory (RAM) required to store that second copy of the image grows with the image size. This might work fine for a digital photo from your phone, but maybe not so well for rotating a hi-def movie.

The in-place algorithm is harder to program, but the memory needed does not grow with image size. All that needs to be stored in memory is that one block (pixel) that you're holding in your other hand.

Improve this answer
1

I would say that this has to do with memory considerations. You can use a trigonometric rotation matrix and calculate everything in working memory before overwriting the original image as a block. However rotating a square matrix by 90 degrees doesn't require any complicated maths at all. With only a single 4-byte variable you can simply move each byte to its new place in the original image itself.

Improve this answer

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .