The Four Programming Questions from My 1994 Microsoft Internship Interview

Computer, Enhance!SubscribeSign inThe Four Programming Questions from My 1994 Microsoft Internship InterviewInterestingly enough, at least two of them were specifically about performance!Casey MuratoriAug 02, 20238710ShareThere are no Performance-Aware Programming lessons this week because it is Summer Internship 1994 Week here on Computer, Enhance! This week will feature five posts about the programming questions I was asked when I interviewed for a Microsoft summer internship way, way back in 1994. Normally scheduled lessons will resume next week.Long, long, long ago — I believe it was in 1994, but it could have been 1993 — I had to interview at Microsoft for a summer intern position. I interviewed with four separate people, and each one asked me a classic Microsoft interview “programming question”.Of course, there wasn’t much of an internet back then, so I had no idea that was going to happen. I had no idea what a classic Microsoft programming question even was, or that they would be asking me them in the interviews.What’s more, being young and inexperienced at the time, I had actually never had anyone ask me to solve a programming question on the spot before. It was a brand new experience for me, and although I would never recommend this style of question as an interview today, I can tell you that as a teenager it was a tremendous amount of fun.It was so much fun, in fact, that I remember all four questions to this day.This week, I’d like to share the four questions with you, talk about the answers that were “correct” at the time, and perhaps go a little further and ask what the “correct” answers might be today given the evolution of desktop computing. Each day this week, I’ll post an answer to one of the questions until we’ve completed all four.For now, let’s look at the questions themselves…Question #1: Rectangle CopyI believe the idea behind the interview process was that the programming questions would get harder as you went through the day. So the first question was the easiest: write C code that copies a rectangle from one buffer to another.I do not remember precisely which parameterization they gave me to do. Because this question was easy for me even at the time, my memory of it is less specific — but it was something like this:void CopyRect(char *BufferA, int PitchA, char *BufferB, int PitchB,
int FromMinX, int FromMinY, int FromMaxX, int FromMaxY,
int ToMinX, int ToMinY)
{
/* Fill this in */
}In other words, given buffers A and B, a “From” rectangle in buffer A, and a “To” position in buffer B, write the code that copies the elements from A to B. Pixels were often only 8 bits at that time, so I believe the elements were 8-bits in this question.As you can see, this is a pretty easy question, at least for anyone who knows C/C++. It might be a bit scarier for people who aren’t used to working with pointers, but in general, the idea of a rectangle copy is fairly straightforward. I was not asked to do anything specific with regards to the performance, either, so it was really just designed to see if I understood this kind of thing at all.Question #2: String CopyWeirdly, the second person who interviewed me asked a very similar question, but one that was seemingly easier than the first question. This was the only one that might be considered “out of sequence”, since questions 3 and 4 ramped up in difficulty quite a bit.Question number two was a string copy. Generally speaking, if you can write a rectangle copy, you can write a string copy, but, I guess they had their reasons for asking this.Specifically, the strings were ASCII-Z, which means one byte per element, null-terminated — something like this:void CopyString(char *From, char *To)
{
/* Fill this in */
}This is a strange question for a number of reasons, not the least of which being the modifications that they asked me to make after I (successfully) wrote it out. Of the four interviews, in retrospect, this is the only one where I’m left wondering if maybe the interviewer didn’t really know their stuff that well… it’s hard to say, but, as I’ll describe in more detail when I answer this question, there were some things in this interview that, with the benefit of all the experience I have now, I look back on and scratch my head a little bit.Question #3: Flood Fill DetectionThe third question was by far the most interesting of the four, and quite a bit more difficult than the first two. It’s still not actually difficult, but given my relative inexperience with problems like it at the time, I was not able to solve this one on the spot. But it’s a fantastic little problem just the same!The question comes from an implementation of a flood fill algorithm the interviewer had written for a Microsoft product. I forget which product, but I think it was some flavor of BASIC. It was for the graphics library of some language product like this, because I remember the interviewer specifically saying the solution “allowed us to beat Borland’s performance”.For folks who don’t know what a “flood fill” is, it’s like the paint bucket in Photoshop: given an image and a particular X,Y coordinate in that image, you want to find all the connected pixels of that color and change their color to something else. While this is not really a feature people think much about today (you do not, for example, see a lot of “how to implement a flood fill using OpenGL” posts on the internet, etc.), it was a very common operation in hobbyist graphics libraries of the era. My recollection is that many BASICs I encountered in the early days all had flood fills.For this question, they did not ask me to implement an actual flood fill. Rather, they asked me to implement the code that detected whether a particular byte matched a particular color.Now normally this would not be much of a question, because that’s just an equals operator — if each byte represents a pixel. But the catch in this question is that this was for four-color CGA mode, where pixels occupy only two bits each.This means that each byte contains four pixels packed together, not one. So you cannot just use a simple comparison (at least not in those days, since SIMD instructions did not exist on home computers). So the question becomes, what is the most efficient way to test to see if any of the four pixels in a byte contains a given color?In other words:int ContainsColor(char unsigned Pixel, char unsigned Color)
{
/* Fill in the computation of true (non-zero) or false (zero) here */
}Additionally, I was allowed to store Color however I wanted — so if I needed some precomputation, I was allowed to bake it in there.This was my favorite question of the four by far, even though I couldn’t do it. In retrospect, it’s even more my favorite now, because it’s a classic example of doing SIMD-style programming without any SIMD instructions. It was the first time I’d ever seen anything quite like that, but of course, it was not the last.Question #4: Outlining A CircleThe fourth and final question was somewhat ridiculous. While there’s nothing wrong with asking someone to write the code to outline a circle, it’s almost entirely an experience question. Either you already know the algorithm that you’d use for this sort of thing on 1990s desktop hardware, or you don’t. There’s no chance you can figure it out on the spot, because the original discovery of the algorithm itself was pretty darn spectacular.So, question number four is a fine question if you want to know how well-read the candidate is. If not, it’s mostly useless. Needless to say, I didn’t get this one in the interview, because I’d never seen the algorithm (or anything like it). I did eventually write the code on the whiteboard for it, but the interviewer had to hold my hand through most of it.Anyway, the question takes the following form:void Plot(int X, int Y); /* This is given as already existing */

void OutlineCircle(int Cx, int Cy, int R)
{
/* Fill in code here that calls Plot once for each pixel on the outline */
}You may be wondering why everything is an integer instead of a floating point number. Well, it was 1994, and floats still weren’t fast enough on desktop computers to be used for most things. Integer was still preferred most of the time for graphics. Things were moving toward float, to be sure, but the era of “most graphics happens in float” had not yet arrived.AnswersThose are the four questions I was asked in my internship interview. I will be giving my answers — both then, and now — in the next four posts. But before you read those, give them a shot yourself! They were a lot of fun for me at the time, and I think you might enjoy them too. If you’re an experienced programmer, you already know how to do all of them, but if you’re like me, you will still enjoy rederiving the last two from scratch!And of course, if you’re not already a Computer Enhance subscriber and would like to sign up to haver our free or paid posts delivered to your inbox, you can always pick a subscription level here:Subscribe8710SharePreviousNext10 CommentsJoost Aug 2, 2023Drawing a circle is an interesting challenge. I think I came up with an elegant solution. It isn’t particularly difficult, but it does require some aha-moments. My key insights were:1) If you know one point on the circle, you can only go to one of three pixels from there. For each of these three pixels, calculate the distance to the center of the circle and pick the one that’s closest.For example, let’s say we’re drawing the upper-right quadrant. We know that the pixel to the right of the center – at (radius, 0) – is on the circle. Since this is the upper-right quadrant, there are only three possible pixels that connect to it, to the left at (radius - 1, 0), to the top at (radius, -1), or to the topleft at (radius - 1, -1). Pick the pixel that’s closest to the center and repeat until you reach to point above the center.2) You don’t need to use the square root.Normally, calculating the distance to the center requires a call to sqrt(), but we’re never interested in the distance itself. All we need is to compare distances and squared distances work for that just as well.3) If you know the distance to the center for the current pixel, it’s easy to calculate the distance when you move one pixel, because it changes by a predictable amount.Suppose you know that the distance to the center is 0 for pixel (6, 8). Since this is in the bottom-right quadrant, moving one pixel up will get you closer to the center, but by how much? Well, the distance changes from 6^2 + 8^2 to 6 ^2 + 7^2 and the difference between 8^2 and 7^2 is 2 * 8 - 1. In general, if you move from x^2 to (x-1)^2, the difference is 2 * x - 1. You can also go in the other direction: if you move from x^2 to (x+1)^2, the difference is 2 * x + 1.Coming up with those insights and verifying their correctness was the tricky part. After that, implementing the algorithm was pretty straightforward.https://gist.github.com/joost-basic-bits/853215920d84fa1796ee5e500c90eda4ReplySharegonutz Aug 2, 2023EditedThe third question is really interesting. I have this idea: Put the color you are looking for, e.g. binary 01, into a byte byte four times, e.g. 01010101. Then xor this with the byte you are looking at. Now the result will have two zeros where the color was found. E.g.:01 00 11 01 the four pixels in our buffer01 01 01 01 the color we look for00 01 10 00 pixels XOR colorThe first and last pixel are the color we are looking for.I thus need to check whether the first two bits are zero, the second two bits are zero, the third two bits are zero or the last two bits are zero. Also multiple of these can be true, if the color exists more than once in these four pixels.This could be done with four if-statements but we want to be fast. I just listed all bytes that meet any of these conditions, i.e. that have at least one 00 pair in the four positions. I tried to find a common pattern in these, e.g. every byte <= 84 means we found the color. But I do not really find a nice way to put a fence around these numbers using bit manipulation.My answer would thus be to have a look-up table of 256 entries, i.e. an array of 256 bytes, and put 1 where there is a match.The first step, making 01 into 01010101, can also be done with a four-element lookup-table.I started learning programming with resources from around 1995 and I remember lookup-tables to be used a lot for graphics, so maybe this was the way they beat Borland :-DThe answer for me would then be:int ContainsColor(char unsigned Pixel, char unsigned Color) {return Matches[FourTimes[Color] ^ Pixel];}ReplyShare4 replies8 more comments...TopLatestDiscussionsNo postsReady for more?Subscribe© 2026 Casey Muratori · Privacy ∙ Terms ∙ Collection notice Start your SubstackGet the appSubstack is the home for great culture

This site requires JavaScript to run correctly. Please turn on JavaScript or unblock scripts

The author recounts four programming questions posed during a Microsoft summer internship interview in 1994, noting that at least two of these questions focused on performance, which is interesting given the era. The first question involved writing C code to copy a rectangle from one memory buffer to another. This task required handling buffer parameters like pitch and coordinate information, specifically copying elements based on a defined source rectangle to a destination position in another buffer. Although described as straightforward for someone familiar with C/C++, the focus was on testing fundamental understanding of pointers and memory manipulation. The second question asked for a string copy, specifically dealing with ASCII-Z strings which are null-terminated, testing sequential memory handling. The author reflects that this question, while seemingly easier than the first, raised questions about the interviewer's depth of knowledge. The third question, Flood Fill Detection, proved to be the most interesting and difficult, stemming from an implementation of a graphics library, possibly based on BASIC. This problem required determining the most efficient method to check if a specific color existed among the four pixels packed within a byte in a four-color CGA mode, where pixels occupy only two bits. The challenge was to implement a function that checked for color matches efficiently, moving beyond simple comparison to optimize for speed, which the author suggests could be achieved using a lookup table implemented from 256 entries. The fourth question involved outlining a circle, which is presented as more of an experiential test regarding algorithmic knowledge rather than purely coding skill. To solve this, the author devised a method based on calculating the distance from candidate pixels to the circle's center, utilizing the principle that squared distances can be compared without needing the computationally expensive square root function. This approach required detailed analysis of how distance changes when moving incrementally in x and y coordinates relative to the center to efficiently determine the next pixel on the outline. These experiences, from basic buffer operations and color-packed bit manipulation to geometric algorithm optimization, represent a retrospective look at fundamental programming concepts relevant to the evolution of desktop computing.