I can say the difference between now and the last time I had to do this (~12 years) is stark.
Seriously...if I have to take another test checking my ability to O(N) a problem, I'm gonna scream. I've been living in ginormous game engines for 6 years, and the amount of times I've had to, in the span of a timed half an hour, optimize a routine to make sure it was running in the optimal time has been....zero.
I'm sure it comes up, and I'm sure it's useful, but this all reminds me of the older assembly guys who used to put in all kinds of wonky tricks that eventually got optimized out by the compiler. Bubblesort has been solved. If your company has to implement it again, you're doing it wrong. There's a routine lying around somewhere in the company. Really.
I don't know what the solution is for evaluating tech talent, but this doesn't seem like it.
Also, web guys...if you're really concerned about speed, maybe you should consider writing some of this code in a lower level language. Plus, if your ad server takes 5-10 seconds to respond, then all of your optimization is for nothing anyway. But hey, you got the O(log N) solution. Bully for you.
Too many people looking for too few jobs. As a 50 something programmer I am now, shall we say, "semiretired". My last interview was a humiliating kick in the crotch. O(N)? Yeah, that and more. The kids need to wake up an (*gasp*, dare I say it?) unionize before they get "rightsized" out of the biz.