One take-home project I was given was very cleverly designed. Without going into too much detail, the project description initially seemed pretty simple. The actual getting-it-to-work part took about half an hour. However there was a requirement near the end that said the whole operation had to complete in less than X amount of time. The initial straightforward implementation I wrote took about 8-times longer to complete. Eventually, 3 hours later, after pulling out a lot of clever tricks I had come up with an implementation that met the performance requirements. The benefit of this type of approach is that it allows potential applicants of many levels to understand and tackle the problem while also allowing them to choose to bail out after that 30 minute mark if they can't think of any way to improve performance. Seems like a polite way to set a high bar standard.
There are naive ways to solve certain problems (finding primes), but there is a general guideline that tasks should finish in under one minute (I believe).
