Each individual level of the skip list can be an array (as described in [1]), so yes, you still have a fair bit of pointer chasing, but the article goes into go

Each individual level of the skip list can be an array (as described in [1]), so yes, you still have a fair bit of pointer chasing, but the article goes into good detail all the tricks you can use to reduce it. I think most binary tree implementations require pointers, so they aren't amenable to this type of optimization. I haven't implemented a skip list myself, so I could be wrong here and happy to hear about why if I am. [edit to add]: I totally get why this would be applicable at Google. The part I find silly is that most companies other than the FAANGs usually just use libraries made by the FAANGs and don't have much reason to focus on this level of comp sci in their own interview processes, yet they still read articles like this and copy Google anyway.