Casey’s interview question #1

By Sijmen J. Mulder, 3 August 2023.

• Question 1: rectangular copy (this page)
• Question 2: strcpy
• Question 3: flood fill check
• Question 4: circle drawing

Casey of Molly Rocket posted four interview questions asked for his 1994 Microsoft intership.

This page is about the first: rectangular array copy. Essentially:

Implement a function to copy a rectangular section from one two-dimensional byte array to another, e.g.:

void rect_copy(
    char *src_buf, int src_stride,
    char *dst_buf, int dst_stride,
    int x0, int y0, int x1, int y1, int w, int h);

Casey’s own explainer video is already online by now but I thought it fun to have a go myself, event hough this is a fairly straightforward question for most programmers with some C experience.

First, let's go through the signature:

• src_buf and is the source buffer.
• src_stride is the line length in the source buffer – that is to say, when you’re at column x in row y, advancing stride elements through the buffer gets you to the same column x on row below, y+1.
• dst_buf and dst_stride are the same but for the destination array.
• x0 and y0 are the column and row of the top left corner of the source rectangle, in the source array.
• x1 and y1 are the column and row of the top left corner of the destination rectangle, in the destination array.
• w and h are the width and height of the rectangle to be copied. Because no scaling is to be applied, these are the same for the source and destination rectangle.

As is implied here, two-dimensional arrays are represented in memory by laying out the rows sequentially – the last element is one row is followed by the first element of the next.

I decided that the simplest approach would be to use two counters, y and x, to loop over every position in the rectangle and then calculate the indices in both arrays in the loop:

void rect_copy(
    char *src_buf, int src_stride,
    char *dst_buf, int dst_stride,
    int x0, int y0, int x1, int y1, int w, int h)
{
	int x, y;

	for (y=0; y<h; y++)
	for (x=0; x<w; x++) {
		dst_buf[dst_stride * (y1+y) + x1+x] =
                src_buf[src_stride * (y0+y) + x0+x];
	}
}

So given an x and y position relative to our rectangle origin, we find the position of that element within either array by taking the starting position (the buf pointer), taking y jumps of length stride to get to the correct row, and then finally adding x to get to the position.

This is a common idiom for accessing multi-dimensional arrays in C. If the length is known at compile-time we can declare a 2-dimensional array directly, e.g. int cells[25][80]; for 25 rows of 80 elements, but that syntax will use the same logic.

While clear in intent and readable (in my opinion) this solution could be optimized, which is what Casey did in his solution. By keeping an offset that is incremented +1 for every column and +stride for every row, no multiplication would be necessary.

No big takeaways here, hope you have a nice day! Comments welcome by email or on Mastodon.

Back to top