Most day-to-day coding is simple and boring. Your interview questions should be, too. I've interviewed 100's of candidates over the years. Many of them had trouble writing a couple of for loops. This was for a somewhat similar problem. I would stress "we don't need an optimal solution, we just need a working solution."