Personally I use a completely different strategy when faced with a problem that can't be adequately understood just by studying it for a short time: I go ahead and attempt solutions, and use their shortcomings as a way of arriving at a better understanding of the problem.
Obvious caveats:
This doesn't work with a problem where you can't know that an attempted solution doesn't work until it's too late.
You have to be able to throw away solution drafts, not just theoretically willing if presented with ironclad proof of their inadequacy, but as a matter of routine practice.
And in fact, prototyping solutions to programming problems is an extremely good way to explore the problem well enough to have a better understanding of what is actually required, and what the best way to tackle it is.
One of the most useful pieces of advice I've gotten: where the solution method is not obvious, start by writing down what you do know about the problem, even the trivial bits (and then, what follows logically from that). Sometimes just seeing it all there and not having to hold those threads of thought in your memory is very helpful to making connections. Also, it is reassuring for me to see that I do know something about the problem and have somewhere to start--that my mind is not a complete blank.
I was taught to approach proofs this way. Figure out what you can derive from what you know. If the proof if is possible, one of those threads must approach the intended conclusion.
It also helps to think of statements from which your goal would directly follow, and work backwards. If one of those back-threads meets a forward-thread, you win. Still, I don't like a mechanical approach like that unless I'm certain I'm at a loss for an intuitive understanding of the problem.
I think this is a kind of crucial point, as I by definition, do not know what to do next.
After avoiding wireheading patterns that push you to "solve" the problem you could try to pinpoint your confusion about what to do. See where your thoughts get stuck and ask questions about why.
(While this is a general discussion, I have "doing well on interview questions" as an instrumental goal; the discussion below is somewhat skewed due to that).
I noticed one of the common failures to solving problems (especially under time constraints) is trying to solve the problem prematurely. There are multiple causes for this; awareness of some of them might reduce the chance of falling into failure mode, others (at least one) I do not have a solution to, and a procedural solution might not exist other than the magic of experience.
Here is my list of the first kind (awareness-helps group):
This brings me to the last failure mode which I do not have a solution for (which is why I am posting ;). If I avoid the traps above, I should have a pretty good understanding of the problem. I think this is a kind of crucial point, as I by definition, do not know what to do next. This uncertainty is scary and might push me into trying to immediately solve it, very similar to 1 above. While you might be able to avoid acting on this by being emotionally reflective (which has the instrumental side effect of appearing more confident) I still do not know what exactly should be done next. Giving some time for unconscious processing seems necessary even on a smallish (interview-question-size) problems, but how much time? And what should I be doing in this time? Meditation? Drawing the problem? Trying to solve sub-problems? Writing down lists of whatever-comes-to-mind? I can use the time constraint-expected size of communicating the solution (in proper format, e.g. C++ code) as an upper bound; but there is a moment when I have to sigh (optional) and take a shot at solution. I do not have anything better to go by than gut feel here.
(Even after the plunge, there is a chance of getting stuck, which is where Meta-thinking skills come in)