Casey’s interview question #1

By Sijmen J. Mulder, 3 August 2023.

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:

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