I absolutely agree that hiring folks who are aware of the basics is important -- essentially, you want engineers who are aware of the space of possibilities. I

I absolutely agree that hiring folks who are aware of the basics is important -- essentially, you want engineers who are aware of the space of possibilities. In my view, what makes folks dislike typical coding interviews is that in the real world, what you need is a solid understanding of what algorithms exist and when to use them/what to look for, rather than the knowledge of how to build one on-the-fly. To solve the issue you described, you don't need to know offhand how to implement a binary search tree on a whiteboard. You do need to know how to identify indexing as a bottleneck, and how to broadly think about a solution. You could then search for indexing strategies and, having studied them at some point in the past, you'd be able to pretty quickly refresh your memory and find the one that's a good fit for the problem at hand. For this reason, I've always thought these exercises would be much better off as essentially "open book" rather than real-time whiteboarding problems -- because that reflects how engineers actually work. That's also what I've pushed for in my own workplaces, and we've had good success finding talented folks, and heard positive feedback about this aspect of the process.