DSA interview question

M-Coloring Problem

Hard · Data structures · Topics: recursion, backtracking, graph

The problem

A university schedules exams into m time slots. Two exams that share a student must not be in the same slot. Modelled as a graph (exams are vertices, conflicts are edges), the question is: can the vertices be coloured with at most m colours so that no edge connects two vertices of the same colour? This is NP-complete in general, so the interview solution is backtracking: colour vertices one at a time, try each colour that no already-coloured neighbour uses, and undo when a vertex has no legal colour.

Example: 4 vertices with edges 0–1, 1–2, 2–3, 3–0, 0–2, m = 3 → true.

Function signature

bool graphColoring(int V, const vector<pair<int, int>>& edges, int m);

Test cases

Input `(V, edges, m)`	Output	Explanation
`(4, [0-1, 1-2, 2-3, 3-0, 0-2], 3)`	`true`	For example colours 1, 2, 3, 2
`(4, [0-1, 1-2, 2-3, 3-0, 0-2], 2)`	`false`	Vertices 0, 1, 2 form a triangle
`(5, [0-1, 1-2, 2-3, 3-4, 4-0], 2)`	`false`	An odd cycle needs 3 colours
`(3, [0-1, 1-2], 2)`	`true`	A path alternates colours
`(1, [], 1)`	`true`

(Confirm: the graph is undirected with no self-loops; colours are 1..m; only adjacent vertices must differ.)

How interviewers phrase it

"Given an undirected graph and an integer M, determine if the graph can be coloured with at most M colours such that no two adjacent vertices share a colour" (GeeksforGeeks "M-Coloring Problem").

Clarifying questions to ask

Is the graph given as an adjacency matrix or an edge list?
Can there be self-loops? (Then no colouring exists.)
Do I return the colouring or just true/false?

Follow-ups to expect

"How do you check a colour is safe?"
"Why colour vertices in index order?"
"Complexity?"
"Special case m = 2?"
"Heuristics?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview