Interview is a negatives filter, not a 'successful employee' indicator.
As a filter, it should be adjusted depending on the job markets, salary/benefit brackets and the type of effort a company/team is willing to put into a hire.
A retained hire is a hire who passed the negative filter and then passed the 'successful hire' assessment, which should be done in a 3 month period.
A company that is not willing to let a bad hire go after 3 month assessment, will eventually accumulate a horrible baggage, that will bring their productivity and morale.
No interview (negative filter) can be good enough to avoid the 3 month assessment. If you do not accept this thinking, and still assume that you can construct an interview that will be good enough to avoid the 3 month assessment -- then you are a likely looking to hire candidates that mimic you, and in general (regardless how average/special you are) -- you will hard time finding the candidates, and actually scaling up your hiring effort.
Back the actual interview.
Programmers need to know which algorithms are sensitive to data sets and in which way (memory consumption, disk consumption, run time cost)
Programmers need to be able to find good implementations for the specified constrained. this is important -- they need to be able to find the existing solutions, not build them themselves (unless you are hiring researches to work out things that have not been done before).
So a good test would be to present a problem, and ask a candidate to do a quick internent research, and find analogies/approaches for a given problem. Asses which one of the found on the net solutions fit better to the problem space. And then describe how they would incorporate what they have found into an implementation, and how much effort they think it should take.
Programmers need to be able to reason about maintainability and testability of the code base, using both previous experience, and analogies from open source projects. Having references to popular books on this topic is helpful is well. This is largely non-formal topic based on empirical evidence or personal experiences. So they do not need to match interviewer's expectations, but must be well argued.
Programmers need to be able to articulate how they react to business decisions that require weighting various trade offs.
Finally, important to see how they relate to the team members that they worked with, from the company they are coming from.
The interview questions posted by the OP address not more than 10% of the criteria I outlined above, so in my view these are poor examples of the CS interview questions.