The four programming questions from my 1994 Microsoft internship interview (2023)
computerenhance.com
computerenhance.com
I fondly recall pirating Strike Commander on 35 floppies, it took quite a few sessions to transfer this since there was quite often some data reading error... good memories, feel like from 5 centuries ago
I also carry a binder. Each page is a one-page description of a project with a color photo of the system and a bulled-point list of all technologies inside. It's a great conversation starter. Hasn't failed me yet.
I've made great hires who had binders just like you described.
I also take months to learn new names, but I can tell you that my second interview ever was for a company which did low level SCADA work. Even though I never took that job or worked in any such related field I can still tell you what it stands for.
The only one I remember was to check if two strings were equal (in C). I wrote (maybe buggy) code to iterate both pointers, comparing while looking for the null terminator.
The interviewer stopped me and said, “You should compare their lengths first. If they are different, you can exit early.”
I was pretty young and didn’t know much, but I explained, “But you have to look for the terminator to find length so it’ll take twice as long.”
He snapped, “There are optimized functions for that!”
I assumed he was right. Needless to say, I didn’t get the job.
Maaaany years later, I realized the std library was probably open source. So I checked (one). It was nice to be vindicated :D
NUL-terminated strings don't know their lengths and so, without an "n" variant function and running strlen() ahead-of-time, must iterate the entire thing. Pascal format strings (supported up to 255 byte lengths in the classic form) could find length as an O(1) operation because there was no terminator necessarily.
Snapping with know-it-all arrogance is toxic and doesn't help anyone. You were correct because strcmp has to iterate both strings, just like strlen would.. and it's totally pointless.
#include <string.h>
/* C89 and handles NULL and overlapping strings */
int strequal(const char *a, const char *b) {
return (a == b || (a != NULL && b != NULL && strcmp(a, b) == 0));
}
You could iterate over the degrees 0 to 360, use trig functions to figure out where the point at that angle is, and plot the closest point. Might need to be a bit tricky about the step size, but I bet you could compute a decent guess from the radius using more trig functions. Of course that probably doesn't work if you don't have floating point and trig functions.
You could also split it into four quadrants. Plot each of the top, bottom, right, and left points by direct computation of adding/subtracting the radius, then for each quadrant, you start from the computed point, check 3 specific points in the appropriate direction for which way you're going in that quadrant, plot whichever one is closest to the radius away from the center, then repeat from that plotted point until you reach the computed point for the next quadrant. It would be tedious and repetitive, but should be doable. You could probably also avoid computing square roots by comparing the squares instead. So I guess you'd want something based on that idea to do it fast on 90s hardware.
In fact, coming up with the CS-perfect solution immediately may be a bit of an anti-signal. I want the person who can think their way through to a solution to a problem that's new to them reasonably well. The fact that you happened to have memorized the best algorithm for this and can recite it on command doesn't tell me much useful, because nobody has the perfect algorithm for everything memorized.
This is a horrible over-generalization, but it seems to me that at least for last 10 years or so colleges are creating students who are more like systems integrators (glorified stack overflow cut-and-pasters) than developers who can equally well think for themselves and derive things from scratch.
I learned to program in the late 70's in the 8-bit home computer era, and developers of my generation had no choice but to write most of everything from scratch, other than implementing a few well known published algorithms. You approached everything from a perspective of "how can I solve this problem?" rather than "what can I find to solve this problem for me?". Additionally due to severe hardware constraints (speed, memory) we had to always be creative and think outside the box - the mentality was that nothing was impossible, just a matter of finding the best solution.
Yes, yes, oh my god yes!
The classic one that will stick in my memory forever was the candidate with an MSCS who was given the problem description and categorized and described what class of problem it was, but completely failed to make any progress in solving it.
I'm sure she was great at complex algorithms, but we just wanted a for... loop to start with.
The flipside of this is that one of the best hires we ever made had such a bad resume that I remember storming into my boss' office and asking why I was wasting my time interviewing that person.
For the circle drawing exercise, it just seems that the interviewer did not do a good job hinting the author. Fun fact: a person I know got this question on their Microsoft interview in around 2016. I guess, it the question works, why bother changing it!
this is probably a rhetorical question, but lemme answer anyways: By packing the colour channels into a single byte. So, for example, you'd have RRGGBBAA within a single byte, for each pixel. Giving you 64 possible colours, with 4 steps of alpha.
Or if you don't need to have alpha, you could pack it even further down to RRGGBB in a byte, which leaves 2 bits left over for the next pixel. Via that, you can pack four pixels worth of colour data into 3 bytes: RRGGBBRR|GGBBRRGG|BBRRGGBB (italics for delineting pixels, vertical bars for delineting bytes)
The latter is a tradeoff between compression and a more complex accessing pattern.
A bit of a tangent, some system used RRRGGGBB for colours, because the eyes are the least sensitive to differentiating the amount of blue, so that's another way to use up a full byte per pixel.
But the original post actually talks about CGA [1] with just four colors. Encoding a color needs two bits then, so each byte encodes four pixels.
Assuming high colour depth, yes, but wouldn’t it have been specified as part of the question that ‘this was for four-color CGA mode’? I think 2 bits per colour for 4 colours total seem pretty sensible even in 2026. :-)
CGA was followed by EGA which supported 16 individually indexed colors (with a palette of 64 colors). With dithering you could display "faded polaroid" quality photos.
The flood fill color detection one would be fastest with a look up table returning a bitmask of colors contained in the byte, with the Color param also as a bitmask, then the result is just lut[Pixel] & Color.
The circle drawing one only needs you to know basic trig to get from radius and angle (0-360) to (x,y) offset from origin. You could embellish the answer with symmetry and LUTs too, but the problem statement doesn't say anything about efficiency.
As the author notes, it would certainly be a massive ramping up in difficulty if they were expecting you to reinvent the midpoint algorithm on the spot.
Given the lack of difficulty of the other questions (and this being pre-internet, targeted for an intern), I don't think the interviewer can have been expecting too much sophistication.
The other obvious way do do it, only requiring the same minimal realization that this is about triangles (with radius as hypotenuse) is to use r^2 = x^2 + y^2 and iterate x=0..r deriving y. You could do it without sqrt if they stipulated that.
So yes, start at (R, 0), increment the y-coordinate each time and possibly decrement the x-coordinate, until x=y which will be at 45°. If the circle's center is an integer on the pixel grid, you can reflect/translate each pixel in that first octant to all eight as you go. If the center is fractionally positioned, you'd have to calculate it all the way around, iterating primarily on y or x depending on the location.
Yes, although the problem statement doesn't say if they care. In this case they are only giving a draw_pixel() primitive, but if you had draw_line() then you could use that to avoid gaps.
The other thing is that this is 90's era, with a CGA display (640x200) being mentioned in the previous question, so I'm not sure there's enough resolution to draw a real circle without gaps unless you do resort to some hack to ensure there aren't any!
Additionally, I was allowed to store Color however I wanted — so if I needed some precomputation, I was allowed to bake it in there.
I believe it can be done in three operations, not including the precomputation.
The naive approach’s assumes you can iterate over the first string until it terminates.
It’s a bit trickier if you do not assume the memory regions cannot overlap.
See memcpy vs memmove: https://man7.org/linux/man-pages/man3/memmove.3.html
y -= x >> 4;
x += y >> 4;
Certainly works, and seems to require 100 iterations to get a full circle.
Are there other approximations, taking smaller angular steps, to get a better circle?
It was an awesome package - I shipped many products which used it in that era - and it was always a bit amusing to me that it seemed like Borland had almost everything they needed to write an operating system. But, they didn't.
Programming has changed over time, but the change has been so gradual I hadn't even realized this until this article. These days I'm pondering how the profession has changed in the last 2 years due to AI. Feels a lot more like a step change. And yet I'm having more fun than I've had in a long time, both at work and at home, throwing Claude at problems. I still don't fully understand why.
Writing that oracle after 20+ years would have been left as an exercise to the reader.
https://www.youtube.com/watch?v=ielZBraKsw8
https://www.youtube.com/watch?v=sabeq-FtfGw
Q2 String copy. Also needs to know if overlapping ranges and/or NULL pointers need to be handled. Must assume ASCIIZ in src. (DOS also had $-terminated strings and Pascal had length & pointer strings.) Pretty easy.
Q3 Flood fill. Keep filling towards either end of the current scanline while the pixel value is the same. Look up and down one scanline with the same width as the filled segment for additional scanline segments that are the same, and recursively begin the algorithm again for each.
Q4 Circle draw. IIRC needs a trig data table to avoid floating point. The current x position needs to be tracked and for each line in y, the length of the current line part to advance x needs to be calculated. Calculate one quarter of the circle and replicate it to all 4 quadrants. I believe the fairest circle rasterization calculation is to subtract half of a pixel width from the radius so that drawing relates to the center of pixels.
[I'm self-taught, so some things aren't as obvious to me as they are to others, and I still get terminology wrong!]
It wasn't an abstract CS flex on interviewer's part either, because apparently the fib trees were actually used in some part of the FrontPage.
I think he wears a shirt with mirrored writing so it looks correct to the viewers.
for each x from -r to r
find y that minimizes abs(x^2 + y^2 - r^2)
plot(x,y)
But what if we take advantage when we are trying to find the y for x+1 that we already have found the y that minimizes the error at x? Say we wrote a next_y(y, e) function that takes the y that was used for x and the error e that would be the error if we also used y for x+1 and that function returns the y that would minimize the error at x+1.
That's pretty easy (Python):
def next_y(y, e):
if e < 0: # need to increase y
delta = 1 + 2*y
while e < 0:
if e + delta >= 0:
if abs(e+delta) < abs(e):
return y+1, e+delta
else:
return y, e
else:
e += delta
y += 1
delta += 2
elif e > 0: # need to decrease y
delta = 1 - 2*y
while e > 0:
if e + delta <= 0:
if abs(e+delta) < abs(e):
return y-1, e+delta
else:
return y, e
else:
e += delta
y -= 1
delta += 2
else:
return y, e
def circle(r): x = -r y = 0 e = 0 print(f'{x},{y}') for i in range(2r): e += 2x + 1 x += 1 y, e = next_y(y, e) print(f'{x},{y}')
Here are some half circles drawn with it: https://imgur.com/a/5aYzPqS
The basic idea is that when you increase x by 1 you increase x^2 by 2x+1, and so (x+1, y) would have error 2x+1 more than (x, y). You then need to change y to compensate.
Changing y by k changes y^2 by 2yk + k^2. Changing k by 1 changes the amount that y^2 changes by 2y + 2k + 1. Note that 2y + 2k + 1 goes up by 2 every time k goes up. In other words if you look at the sequence y^2, (y+1)^2, (y+2)^2, ... the third order diffs are 2. So to see how consecutive changes to y affect y, we can just keep track of the adjusted e and the current second order diff. Then for each consecutive y we can add the second order diff in to update the adjusted e to for the next y, and add the third order diff (the constant 2) into the second order diff.
I split next_y into two cases depending on whether we need to increase y or decrease y. There is probably some way to combine them but it is late and I'm half asleep. Oh, and I realize half of the abs() calls can be removed. I thought it looked clearer with them.
For a radius 50 half circle here is how times it took N tries to find the right y:
3 0
68 1
18 2
6 3
2 4
1 5
2 10
3 0
410 1
121 2
35 3
13 4
7 5
2 6
3 7
2 8
2 11
1 24
1 25
An improvement would be to make more use of symmetry. The curve looks best when x is between -r/2 and r/2. It would be better to draw just those parts and then use symmetry to fill the rest.
void CopyString(char *From, char *To)
{
/* Fill this in */
}
while (*to++ = *from++) ;