Rendered at 23:27:57 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
zhxiaoliang 2 days ago [-]
The author’s memory is remarkable. I hardly remember my own name that far back, LOL. Back then, I knew I would always struggle with those types of interviews, so I always carried a floppy disk with me to them. The disk contained a few programs I had written, and I would simply tell the interviewers, “Don’t give me a quiz. I’m terrible at it, so if you do, I’m out.” However, if they were willing to look at my capabilities, I would share a few of my programs. That approach actually worked most of the time and got me the jobs. The good old days!
animal531 1 days ago [-]
Memory is a funny thing.
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.
TimByte 1 days ago [-]
Names disappear instantly, but some oddly specific technical acronym from one interview decades ago gets burned into ROM
mikepurvis 2 days ago [-]
I can tell this is from forever ago by floppy disk.
zhxiaoliang 2 days ago [-]
Yes, but it feels like yesterday...
mvdtnz 2 days ago [-]
That's an IRL save icon for anyone who's wondering.
kakacik 1 days ago [-]
3D printed to the finest details, heck it can even store like half a picture.
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
TimByte 1 days ago [-]
A small floppy full of actual programs probably said much more about your ability than a whiteboard quiz ever could
chistev 2 days ago [-]
Why did that approach change?
zhxiaoliang 2 days ago [-]
I’m not sure if that strategy still works in today’s job market. It might still be, but I’m not the one to answer since I haven’t been on a job interview in quite some time.
joezydeco 1 days ago [-]
I work in embedded systems. I always carry a few (small) projects with me in a backpack with a power supply and bring them out if certain topics allow me to do a show-and-tell.
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.
HeyLaughingBoy 1 days ago [-]
10 years after I was hired, one of the interviewers still remembered me showing him a small board that I'd designed, even though he was a Windows MFC programmer and didn't know the first thing about microcontrollers.
I've made great hires who had binders just like you described.
ta8903 2 days ago [-]
Surely the modern equivalent to that is having public git repositories.
HarHarVeryFunny 1 days ago [-]
Perhaps, but has "I'm not doing your whiteboard challenge - check out my git repositories instead!" ever worked for you?!
zhxiaoliang 1 days ago [-]
Haha, for some reason when phrased like that I get a bad feeling about the outcome of the interview.
timmg 1 days ago [-]
My first ever programming interview was like a group interview. There were three or four programmers asking me questions, one at a time.
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
KetoManx64 1 days ago [-]
On the upside, think how annoying it would have been to be part of that team and have a boss that doesn't have any ability to admit he is wrong.
RankingMember 1 days ago [-]
Yep, sounds like a bullet dodged there.
TimByte 1 days ago [-]
Funny how often "there are optimized functions for that" really means "I haven't thought through what the optimized function actually has to do"
burnt-resistor 2 hours ago [-]
"Group interviews" produce horrible, unfair dynamics.
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));
}
I think you dodged several bullets by not getting hired there because they sounded insufferable.
coolThingsFirst 1 days ago [-]
C is pretty bizarre but I expect someone writing it professionally to know that even passing void compareStrings(char str1[], char str2[]) is equivalent to compareStrings(char * str1, char * str2) so no way to get the length of it with sizeof(str1) and strlen walks the string until it finds the null terminator.
burnt-resistor 2 hours ago [-]
No, it's not bizarre, it's standardized on what is and isn't UB based on history, and usually for performance.
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.
As a kid on old hardware I'd loop 360 degrees and do sin and cos, and wait ages for that circle. I wasn't super clever I probably just cargo culted it from somewhere.
ufmace 2 days ago [-]
The circle outlining one seems interesting to me. I definitely didn't read the algorithm ahead of time, and I'm probably not as smart as a revolutionary genius computer scientist, but I thought of 2 basic algorithms in a few minutes.
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.
Exactly! I used this question regularly. It wasn’t a gotcha question or even an impossible-without-experience question as the author thinks. It was a show me HOW you think through something question. There are a lot of ways to solve it, from scanline to sin/cos to using the circle equation, but you can _progress_ from naive to advanced solutions, and all solutions above plus the DDA or Bresenham solutions have symmetries (hint: more than four quadrants are symmetrical) that you can use to optimize it. A practiced interviewer can learn a lot about the candidate with this question.
ufmace 2 days ago [-]
I wonder if there's a class of people who managed to get CS degrees but really aren't that good. To them, it might feel more like either you remember the perfect and optimal but complex solution you were taught in a class, or you don't happen to remember it and are completely stuck and can't make any progress at all. I don't think I'd want to hire or work with somebody who can't come up with some sort of solution after thinking through it for a few minutes.
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.
HarHarVeryFunny 1 days ago [-]
> I wonder if there's a class of people who managed to get CS degrees but really aren't that good
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.
twodave 1 days ago [-]
It's not necessarily a class of people. It's proficiency vs. mastery. Is some set of people more able to master a subject than another? Sure. Each person has different limits to their potential, of course, but for most things achieving mastery is more a matter of putting the work in over time.
rhyperior 1 days ago [-]
A family member took the same calculus class that I did, from the same teacher. They passed, per their own account, only by memorizing the rules. I memorized what I needed to but the concepts clicked intuitively. So sure, some people “get it” and some people just pass a subject like CS.
HeyLaughingBoy 1 days ago [-]
> I wonder if there's a class of people who managed to get CS degrees but really aren't that good
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.
danbruc 1 days ago [-]
Your second one is somewhat in the right direction, I think. My guess would be that you split the circle into eights, that keeps the tangent slope between zero and one. Then you can go along one axis from 0 to sin(45°) times the radius and the value along the other axis will always either stay the same or change by one as the derivative is between zero and one. As you move along your primary axis, you generally keep the value along the secondary axis unchanged but you accumulate the error. When the error crosses 0.5, you move one pixel along the secondary axis and adjust the error accordingly. And of course you always draw eight mirrored and rotated pixels. In some way an adaptation of the Bresenham algorithm for drawing lines.
TimByte 1 days ago [-]
Your second idea is pretty much the direction the classic solution takes: walk along the curve incrementally, avoid square roots, and use symmetry to fill in the other parts
It's pretty amazing to me that, if your goal is to check that the intern candidate can write plain C, the questions still look pretty reasonable to me even in 2026, maybe except for the question related to colors which will probably confuse the majority of the interns (2 bits per color? how is that possible).
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!
Akronymus 2 days ago [-]
> (2 bits per color? how is that possible).
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.
Oh right. Guess the " (2 bits per color? how is that possible)" is what threw me off there, because I read it as 2 bits per colour channel, rather than cga colour. Of course, "indexed" colours can get away with much fewer bits.
consp 2 days ago [-]
A modern example of odd color schemes is 18bit color which is still often used in small cheaper displays (666/18bit vs 565/16bit) keeping the maximum color space available for all colors on these displays. If you are lucky you only have 16bit bus available and also need to do 3:2 packing, but that allows you to use 24bit in code and ramming the bytes in sequence over the 16bit bus without any modification (since they ignore the extra two bits per color).
HarHarVeryFunny 2 days ago [-]
It seems the first two questions are coding ones, and the second two ("flood fill" and circle drawing) are more thinking ones.
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.
ventana 2 days ago [-]
I don't believe you need trig for that, it actually makes it harder if you try to iterate the angle. I believe the expected solution is to start at (R, 0) which is known belongs to the circle, and go left/top, choosing the pixel closest to the circle on each step, which does not require any floating point arithmetic.
HarHarVeryFunny 2 days ago [-]
The problem is under-specified both in terms of requirements and any implementation restrictions.
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.
vikingerik 2 days ago [-]
Right, iterating through pixels is better. The tricky part about iterating the angle is that you need to choose the step size correctly or else you could skip pixels. Like if you iterate in 1-degree increments, you'll plot 360 pixels total, but the size of the circle on your canvas might be more than 360 pixels wide. I'm sure there's a way to choose the angle iteration step size to guarantee not skipping pixels, but you'd often duplicate work and re-plot the same pixel twice.
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.
HarHarVeryFunny 2 days ago [-]
> The tricky part about iterating the angle is that you need to choose the step size correctly or else you could skip pixels
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!
__s 2 days ago [-]
The circle one is fishing for sonething clever. 90s without floats means no trig
HarHarVeryFunny 2 days ago [-]
So use sin/cos lookup tables?
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.
F3nd0 2 days ago [-]
> (2 bits per color? how is that possible)
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. :-)
Sharlin 2 days ago [-]
Their point, I believe, is that someone (just about any younger person in 2026) who has never seen indexed color modes, or colors taking less than one byte per pixel to encode, could reasonably be confused by the notion of "two bits per pixel".
lstodd 2 days ago [-]
2bpp is indexed obviously, question in 1994 would be is it bitplane or packed
HarHarVeryFunny 2 days ago [-]
CGA was very limited, and didn't even support full per-color indexing - instead you got to choose one of two palettes (i.e. one of two different sets of 4 predetermined colors).
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.
bananaboy 2 days ago [-]
CGA is even more nuanced than just two palettes. You can choose from three palettes, and each can be set to low intensity or high intensity, so you can effectively choose from six. On top of that, the background colour for each palette (colour 0 which defaults to black) can be set to any colour from the full CGA 16 colour palette! I wrote a sample program for a friend recently to demonstrate this https://github.com/samizzo/cgasample
userbinator 2 days ago [-]
The second one is absolutely trivial if you've ever read K&R (even if you're not allowed to just call strcpy()), while the fourth one is also very straightforward if you know about https://news.ycombinator.com/item?id=15266331 ; but 32 years ago, knowledge definitely did not propagate as quickly as it does today.
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.
koolba 2 days ago [-]
> The second one is absolutely trivial if you've ever read K&R (even if you're not allowed to just call strcpy())
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.
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?
ggambetta 2 days ago [-]
This brings back memories! I could easily pass this interview today, because I used to write code like this all the time 25 years ago doing gamedev (and so did everyone else to some extent). But the really interesting thing is that I just realized I haven't written code like this in a long, long time.
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.
nikanj 2 days ago [-]
The circle one would have gotten me. "There's a neat algo for this. The name starts with B, and you just get an oracle that tells you if next y ==current y or y-1. And then you loop x, and you have to mirror that to do all octants of the circle with mirroring and flipping by -1 for some octants"
Writing that oracle after 20+ years would have been left as an exercise to the reader.
ggambetta 2 days ago [-]
Fair, I wouldn't have been able to write Bresenham back then (or now, off the top of my head). I'd have written a simple trig-based one. Maybe I'd have failed the interview :D
locusofself 2 days ago [-]
This is a fun article. As a current Principal at MSFT I've never seen these type of questions being asked in interviews. I don't think it's fair or accurate to say "If you’re an experienced programmer, you already know how to do all of them". So many of the SWEs and candidates at Microsoft are just studying leetcode using python, joining the company and writing managed C# code.
daymanstep 2 days ago [-]
I would far prefer getting managed C# over the Electron garbage that constitutes much of Windows nowadays.
dotancohen 2 days ago [-]
Where in MS Windows is Electron used?
joe_mamba 1 days ago [-]
WebView2, not Electron, but same shit.
burnt-resistor 2 hours ago [-]
Q1 Rectangle copy. Needs to know if overlapping ranges and/or NULL pointers need to be handled. It can be reduced to FromMaxY-FromMinY+1 memcpy()'s and some pointer math using strength reduction to replace unnecessary multiplies with adds.
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.
teunispeters 1 days ago [-]
The Bresenham line algorithm was such a breakthrough to me - talk about looking at a differential (partial differential) from an integer view, by a particular axis! Anyway, by extension, approaching a circle using similar is actually "relatively obvious".
[I'm self-taught, so some things aren't as obvious to me as they are to others, and I still get terminology wrong!]
eps 2 days ago [-]
A friend of mine interviewed for MS around the same time, albeit for a senior-ish position, and his question required knowing Fibonacci trees.
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.
TimByte 1 days ago [-]
What I like about these questions is that they're small enough to fit in your head, but still reveal a lot about how someone thinks about memory, representation, and hardware
NoSalt 1 days ago [-]
I tried to implement flood-fill for a JavaScript project I am working on. I found out quickly that recursion was NOT the best way to do this.
2 days ago [-]
dieselgate 2 days ago [-]
How does the video whiteboard work? I presume he isn't really writing backwards or is this some sort of software that handles the video and writing surface?
I think he wears a shirt with mirrored writing so it looks correct to the viewers.
dieselgate 2 days ago [-]
Dang cool, think I've heard or seen references to it before but never seen it. Thanks for the information and link
simonjgreen 2 days ago [-]
What impressed me most is when he pushes a button and the board physically moves up to make space
dsatrainer 1 days ago [-]
I was busy being born in 1994 when I should've been trying to pass this interview haha
mgaunard 2 days ago [-]
I had somewhat similar questions asked of me in the 2000s, and I still ask similar questions today.
HarHarVeryFunny 2 days ago [-]
It's been a long time since I did any interviewing, but for a whiteboard task I'd ask for something very simple like reversing a list. It's basically a lying test more than a coding test - and sad how many people claiming multiple years of C++ could not do it.
aa-jv 2 days ago [-]
The "Borland flood fill" routine that Microsoft was trying to beat was in the very popular (at the time) "Turbo Graphics for Borland" package which had an immensely useful stack of graphics primitives, some a little more advanced than what was available in Windows at the time, for pure DOS mode.
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.
latexr 1 days ago [-]
All of them are available as YouTube videos. If you only watch one, I recommend the fourth.
I interviewed at Microsoft in Redmond in 1997 and got zero programming questions. They were all knowledge-based or brain-teaser questions so I don't know if I believe that they gave 4 programming questions in 1994.
varjag 2 days ago [-]
Mid 1990s were still dog-years for computing, everything moved fast. It's like 2013 to 2026
rep_movsd 1 days ago [-]
There are 3 algorithms I learned for circles when I was a kid.
I wrote about them a decade and a half ago
The third one is prety clever
You can tell a lot about a C/C++ engineer by asking a simple question like strcpy(). Assuming they get it right (which many don't), you can then cover test cases, you can discuss trade offs on safety vs performance, and failure modes. It can actually be very interesting.
tzs 2 days ago [-]
I had a go at the circle one. What I tried was starting with something very straightforward (pseudocode):
for each x from -r to r
find y that minimizes abs(x^2 + y^2 - r^2)
plot(x,y)
Finding y could be done by taking sqrt(r^2 - x^2) and then taking whichever for floor or ceil of that gives less error. But I assume they probably don't want sqrt. We could find y without using sqrt by doing some kind of search--say start with 0 and increment checked x^2 + y^2 - r^2 until we find where that crosses 0 and then take whichever y made it closes to 0. But that will be even slower than sqrt.
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
Here's how it is used:
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}')
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
i.e., for 68 values of x, the first y it looked at was the right one. Here are the numbers for a radios 300 half circle:
That was a fun little exercise. It has two multiplies, but they are both by 2 so could easily be replaced by add or shift.
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.
jimbob45 2 days ago [-]
What is pitch in regard to a rectangle in question two?
hcs 2 days ago [-]
Pitch is the offset between the start of consecutive rows of pixels in the image, used to convert y coordinates into the start of any given row, so you access a pixel as buffer[y*pitch+x]. Often this is the image width, but can be greater depending on required alignment.
ggambetta 2 days ago [-]
So at the end of each run increment the relevant pointer by (pitch - w) not pitch which I'm sure it's one of the bugs they saw all the time in this interview :)
2 days ago [-]
coolThingsFirst 1 days ago [-]
today it's paxos/raft questions for an internship writing Next.js for 10$ an hour.
0xpgm 1 days ago [-]
If I may guess, this is for a web3 internship?
offercc 2 days ago [-]
[flagged]
Ozzie-D 2 days ago [-]
[dead]
CamperBob2 2 days ago [-]
void CopyString(char *From, char *To)
{
/* Fill this in */
}
The only correct answer to this interview question is "No."
anitil 2 days ago [-]
Well in an interview I guess something like "Of course we shouldn't allow C-strings in general outside of syscalls and argv, but for the purpose of the exercise...." And now you've shown that you know what you're talking about and that you won't be difficult to work with.
TZubiri 1 days ago [-]
I don't think it was clear in 1994 that not passing the size of a string was a sin
anitil 23 hours ago [-]
Oh 100%, I was responding to the parent who's response was 'No'. Even if you have 100% ban on strcpy and z-strings you're forced to use them in certain cases (like argv), and I was pointing out that sometimes we engage with certain conceits in a job interview, and by refusing to engage with it you're giving out a signal that you'll be difficult to work with
HarHarVeryFunny 2 days ago [-]
/* YOLO */
while (*to++ = *from++)
;
userbinator 2 days ago [-]
I see someone has read K&R.
0x1ceb00da 2 days ago [-]
Syntax error: variable "to" not found
HarHarVeryFunny 1 days ago [-]
Upper case is for compile-time constants. I couldn't make myself do it.
ggambetta 2 days ago [-]
Thought the same. Reckless today, literally standard back then.
sgerenser 2 days ago [-]
Hey, in 2026 strcpy is still part of the C standard library (much to the chagrin of anyone security conscious).
userbinator 2 days ago [-]
The key point (which I believe static analysers these days can easily check for) is to check the sizes of the source and destination.
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.
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.
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
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.
I think you dodged several bullets by not getting hired there because they sounded insufferable.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.
1) https://www.computerenhance.com/p/microsoft-intern-interview...
2) https://www.computerenhance.com/p/microsoft-intern-interview...
3) https://www.computerenhance.com/p/microsoft-intern-interview...
4) https://www.computerenhance.com/p/efficient-dda-circle-outli...
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.
https://en.wikipedia.org/wiki/Midpoint_circle_algorithm
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.
https://en.wikipedia.org/wiki/Color_depth
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.
[1]: https://en.wikipedia.org/wiki/Color_Graphics_Adapter
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.
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!
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.
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.
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?
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.
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.
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.
https://www.youtube.com/watch?v=ielZBraKsw8
https://www.youtube.com/watch?v=sabeq-FtfGw
https://www.youtube.com/watch?v=OE_UNZW-4_U
https://www.youtube.com/watch?v=JtgQJT08J1g
https://schmantics.blogspot.com/2011/12/third-circle.html
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):
Here's how it is used: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:
i.e., for 68 values of x, the first y it looked at was the right one. Here are the numbers for a radios 300 half circle: That was a fun little exercise. It has two multiplies, but they are both by 2 so could easily be replaced by add or shift.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.
while (*to++ = *from++) ;