If you want to solve difficult problems, simply hire mathematicians. In academics, the Math department has its house in order. But Compsci departments vary so much between different universities that I start interviews of NCG with some really basic questions that anyone in the field should know.
For example, I might start with a linked list, an interrupt handler (ISR), and a semaphore/mutex/threading problem. If you can do 2 out of 3, then that's a good start. If you can't do any one then I recommend to the HM to pull the plug and skip the remaining interviewers.
But if you can already do a bunch of stuff in Matlab that I can't do. And you seem to be interested in C++ (or whatever we're using). Then I have no problem letting you figure out the rest on your own. The CS part of the j ob isn't really hard, not at the practical application level.