I got an email today from one of the super secret stealth start-ups, the one I really wanted, and they told me that they had chosen to go with another candidate. Bummer.
At one recent interview, an engineer asked me to "give him the sum of the two highest digits in an integer array. Any language." I thought for a moment, then wrote:
array.sort() return array[-1] + array[-2]
He said that was fine, but since it would be O(n*logn), could I do it in O(n). He wanted a linear search instead.
After answering the question to his satisfaction, we got into a bit of a religious discussion about the merits of concentrating on performance during initial composition, versus concentrating on correctness. I'm much more a "get it working, then get it right, then profile the working program for bottlenecks and work them out." It is possible that you can create systemically slow solutions that'll require a re-write, but that's actually far less likely than having I/O or CPU bottlenecks in small functions of code that can be fixed with optimization.
He later told me that, although I didn't get the job, he voted to hire me. He liked my answers and appreciated that I was willing to stand my ground and discuss the relative merits of different approaches.