I believe that there are certain kind of questions which can just not be prepared beforehand.

I was asked this question in my Google's last round, after recommenation from Hiring Committee. (HC thought few harder questions should have been asked):

Given a zero-indexed array 'A'= {1, 2, 3, ..., n} of 'n' integers, how can we re-arrange the numbers in it such that for any two numbers a [i] and a [j] (i < j), their average does not lie between i and j?

Does someone really believe that these kind of questions can be really be solved with reasoning during the 45 min interview process ?
If yes, how to prepare for them ?