But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.
You're in!
Given an undirected graph with maximum degree D, find a graph coloring using at most D+1 colors.
For example:
This graph's maximum degree (D) is 3, so we have 4 colors (D+1). Here's one possible coloring:
Graphs are represented by a list of N node objects, each with a label, a set of neighbors, and a color:
D+1 colors is always enough. Does your function ever need more colors than that?
Does your function go through every color for every node? You can do better. You don't want N*D in your final runtime.
We can color a graph in linear time and space (on the number of nodes, edges and/or the maximum degree).
What if the input graph has a loop? Does your function handle that reasonably?
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
time where N is the number of nodes and M is the number of edges.
The runtime might not look linear because we have outer and inner loops. The trick is to look at each step and think of things in terms of the total number of edges (M) wherever we can:
Putting all the steps together, our complexity is .
What about space complexity? The only thing we're storing is the illegal_colors set. In the worst case, all the neighbors of a node with the maximum degree (D) have different colors, so our set takes up space.
The lowest number of colors we can use to legally color a graph is called the chromatic number.
There's no known polynomial time solution for finding a graph’s chromatic number. It might be impossible, or maybe we just haven’t figured out a solution yet.
We can't even determine in polynomial time if a graph can be colored using a given k colors. Even if k is as low as 3.
We care about polynomial time solutions (n raised to a constant power, like ) because for large ns, polynomial time algorithms are more practical to actually use than higher runtimes like exponential time (a constant raised to the power of n, like ). Computer scientists usually call algorithms with polynomial time solutions feasible, and problems with worse runtimes intractable.
The problem of determining if a graph can be colored with k colors is in the class of problems called NP (nondeterministic polynomial time). This means that in polynomial time, we can verify a solution is correct but we can’t come up with a solution. In this case, if we have a graph that's already colored with k colors we verify the coloring uses k colors and is legal, but we can't take a graph and a number k and determine if the graph can be colored with k colors.
If you can find a solution or prove a solution doesn't exist, you'll win a $1,000,000 Millennium Problem Prize.
For coloring a graph using as few colors as possible, we don’t have a feasible solution. For real-world problems, we'd often need to check so many possibilities that we’ll never be able to use brute-force no matter how advanced our computers become.
One way to reliably reduce the number of colors we use is to use the greedy algorithm but carefully order the nodes. For example, we can prioritize nodes based on their degree, the number of colored neighbors they have, or the number of uniquely colored neighbors they have.
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
Reset editor
Powered by qualified.io