One of my favorite questions to ask interview candidates, (especially if they bring it up first) is about performance tuning.  In fact, recently one candidate and I got into some questions about computational complexity, big O notation, and space / time tradeoffs which is definitely not the norm.