4 ms·
It's funny: if you asked me that right now, I wouldn't be able to do it. That knowledge was in my brain at some point, but it fell out. I can, however, implemen
by shrimp_emoji 7y ago
It's funny: if you asked me that right now, I wouldn't be able to do it. That knowledge was in my brain at some point, but it fell out. I can, however, implement a PR quad tree[0] (which is a trie and not a tree) which allows efficient coordinate search of a 2D space since that's what I've been doing most recently. I think that's more impressive, but it's not what you asked for so I fail the interview. :3
0: https://en.wikipedia.org/wiki/Quadtree https://en.wikipedia.org/wiki/Quadtree
- User23 7y agoYeah, that's how it appears it really works. That said, the fundamental idea behind bsearch is toddler easy. It's interesting that such an apparently simple algorithm, namely start in the middle, pick left or right depending on the key, and repeat, is so challenging to code correctly.
- animal531 7y agoFor bonus points you can also implement an Octree.
- shrimp_emoji 7y agoThat would be for coordinate search in 3D spaces. :D
- User23 7y agoIt's fun how easy it is to program in higher dimensional spaces and how hard it is to think in them. Mathematical formalism is a superpower!