I'm sorry but if someone is trying to get a job with the title, "Software Engineer" in it and they cannot do a nested for loop (the slow O^2 solution) I don't know what to tell you other than that person is not fit for the job.

In terms of basics it's akin to "fizz buzz".