3 ms·
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 mo
by crote 9y ago
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!
- Someone 9y agoThe 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.