Is it amazing that they can't do them at all, or they can't do them in the spotlight in a totally unfamiliar? I have a strong feeling that most of the people you think fall in the former are actually in the latter.
Yes, the solution might be a couple nested for loops. But if it's a new question to the interviewee, then they don't know the solution yet.