Hacker News Reader

If you were weirdly interested in the four color theorem, you might like this common coding interview question about graph coloring: https://www.interviewcake.com/question/graph-coloring

View on HN

That's a rather nasty interview question, though. If you've never heard of the problem before, writing the greedy algorithm isn't too bad. But it is actually more challenging if you are familiar with graph colouring, as knowing that it's NP-complete might be enough to stop one from even considering this to be an edge case...

If you really want your interviewees to hate you, ask them to solve it using D colours!

The problem description doesn’t specify “planar”, and K4 has degree 3 for each of its four vertices, but (obviously) requires 4 colors (and K5 has maximum degree 4, but requires 5 colors, etc.)

Also, K3, K2 and K1 are planar with maximum degree 2, 1, respectively 0, but require 3, 2, 1 colors.

So, in general, D colors isn’t sufficient.

Reply on news.ycombinator.com