Coding Interview 13: Byte Image
You have a monochrome image (black and white only). You are to write a function that will take in this image, an x-coordinate, a y-coordinate, a width, and a height, and draw a black rectangle that has its top left corner position at the x/y coordinate and with the given width and height.
Also, the image is stored as a two-dimensional array of bytes where each byte represents 8 horizontally consecutive pixels. (1 = white, 0 = black).
This isn't a particularly complex question. The correct description would be something more along the lines of a "compound" question. This is more or less a test to see how well you can think through lots of small moving parts.
The answer isn't particularly profound, but do try to work through it on a whiteboard first before looking at the answer.
Because the rows in the 2D array are rows of pixels, we don't need to do any special logic for the y-coordintaes.
However, since 1 column in the array translates to 8 columns in the picture, then we need to do magic for the x-coordinate. There are two main possibilities:
The approach I've done here is applying a bit mask to the left and right columns of pixels individually. Then if there is any overlap, clearing out the pixels for those inbetween columns as well. If the left and right sides of the rectangle are in the same pixel column, I OR the masks together and store it in left. Then I set the right pixel mask to all 1's. This way, when the left and right masks are applied (to the same x coordinate), it will still give you the final desired result. If not, the masks are applied individually to each end and the middle pixels are cleared by the loop.
The cryptic lines where the bitmask is generated can basically be described as creating some power of two and then subtracting 1 to create a sequence of all 0's followed by a sequence of all 1's. It's inverted for the left mask to create a series of 1's followed by a series of 0's.
Also, the image is stored as a two-dimensional array of bytes where each byte represents 8 horizontally consecutive pixels. (1 = white, 0 = black).
This isn't a particularly complex question. The correct description would be something more along the lines of a "compound" question. This is more or less a test to see how well you can think through lots of small moving parts.
The answer isn't particularly profound, but do try to work through it on a whiteboard first before looking at the answer.
void Draw(byte[,] pixels, int left, int top, int width, int height)
{
int right = left + width - 1;
int left_x = left;
int right_x = right;
int left_column = left_x / 8;
int right_column = right_x / 8;
byte left_mask = (byte)(~((1 << (8 - (left % 8))) - 1));
byte right_mask = (byte)((1 << (7 - (right % 8))) - 1);
if (left_column == right_column)
{
left_mask = left_mask | right_mask;
right_mask = 0xff;
}
for (int y = top; y < top + height; ++y)
{
pixels[left_column,y] &= left_mask;
pixels[right_column,y] &= right_mask;
for (int x = left_column + 1; x < right_column; ++x)
{
byte[x,y] = 0;
}
}
}
{
int right = left + width - 1;
int left_x = left;
int right_x = right;
int left_column = left_x / 8;
int right_column = right_x / 8;
byte left_mask = (byte)(~((1 << (8 - (left % 8))) - 1));
byte right_mask = (byte)((1 << (7 - (right % 8))) - 1);
if (left_column == right_column)
{
left_mask = left_mask | right_mask;
right_mask = 0xff;
}
for (int y = top; y < top + height; ++y)
{
pixels[left_column,y] &= left_mask;
pixels[right_column,y] &= right_mask;
for (int x = left_column + 1; x < right_column; ++x)
{
byte[x,y] = 0;
}
}
}
Because the rows in the 2D array are rows of pixels, we don't need to do any special logic for the y-coordintaes.
However, since 1 column in the array translates to 8 columns in the picture, then we need to do magic for the x-coordinate. There are two main possibilities:
- The x coordinates of the left and right sides of the rectangle are in different byte columns
- The x coordinates of the left and right sides could be in the same byte column
The approach I've done here is applying a bit mask to the left and right columns of pixels individually. Then if there is any overlap, clearing out the pixels for those inbetween columns as well. If the left and right sides of the rectangle are in the same pixel column, I OR the masks together and store it in left. Then I set the right pixel mask to all 1's. This way, when the left and right masks are applied (to the same x coordinate), it will still give you the final desired result. If not, the masks are applied individually to each end and the middle pixels are cleared by the loop.
The cryptic lines where the bitmask is generated can basically be described as creating some power of two and then subtracting 1 to create a sequence of all 0's followed by a sequence of all 1's. It's inverted for the left mask to create a series of 1's followed by a series of 0's.
