Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The four programming questions from my 1994 Microsoft internship interview (2023)

computerenhance.com

Post reply on HN
Print view View original

21–30 of 103 posts

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#21

Post by userbinator »

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.

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#22

Post by anitil »

CamperBob2 wrote: post #8

void CopyString(char *From, char *To) { /* Fill this in */ } The only correct answer to this interview question is "No."

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.

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#23

Post by HarHarVeryFunny »

ventana wrote: post #15
HarHarVeryFunny wrote: post #7

Earlier quoted context omitted.

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 ang…

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.

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.

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#24

Post by vikingerik »

ventana wrote: post #15
HarHarVeryFunny wrote: post #7

Earlier quoted context omitted.

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 ang…

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.

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.

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#26

Post by HarHarVeryFunny »

vikingerik wrote: post #24
ventana wrote: post #15

Earlier quoted context omitted.

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.

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…

> 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!

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#27

Post by koolba »

userbinator wrote: post #21

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 a…

> 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.

See memcpy vs memmove: https://man7.org/linux/man-pages/man3/memmove.3.html

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#29

Post by HarHarVeryFunny »

mgaunard wrote: post #28

I had somewhat similar questions asked of me in the 2000s, and I still ask similar questions today.

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.

Re: The four programming questions from my 1994 Microsoft internship interview (2023)

#30

Post by HarHarVeryFunny »

lstodd wrote: post #9
F3nd0 wrote: post #6

Earlier quoted context omitted.

> (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. :-)

2bpp is indexed obviously, question in 1994 would be is it bitplane or packed

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.

Post reply on HN