Yes, scalable problems are the best, but can be difficult to devise. A lot of folks tend to go the "optimization" route, by having a problem with multiple ways

Yes, scalable problems are the best, but can be difficult to devise. A lot of folks tend to go the "optimization" route, by having a problem with multiple ways of extracting more performance, typically by better algorithms or data structures. These are ok, but not great. Most candidates will reasonably start with a simple naive solution that works and then try to optimize, but time may not allow for that and the optimization may require significant rewriting of the solution. So unless you either start out with the optimized solution or you have a lot of time, you're unlikely to ever see those solutions. I tend to prefer scaling via scope. For example, for our game engineering test, we start with a half-finished 2D "game" (think something like pacman). We then have a list of functionality that can be added with increasing difficulty. This allows us to measure "seniority" by both (a) how far down the list they get and (b) the quality of the individual solutions. Another example is starting with a single threaded solution and then extending into a multi-threaded or multi-process solution.