The problem has no known polynomial time algorithm, and I guess the solution given by Bartosz Milewski is adequate for an interview. However the problem (graph isomorphism) is NOT known to be NP-complete, and it is strongly conjectured not to be. I think the fastest program available for this problem is known as nauty, written by the mathematician Brendan McKay.