3 ms·
But a skip list is an application of linked lists. If you can implement a skip list you can implement a linked list. If you can't implement a linked list I can'
by chrisseaton 7y ago
But a skip list is an application of linked lists. If you can implement a skip list you can implement a linked list. If you can't implement a linked list I can't see how you'd implement a skip list.
> Not that you would usually implement such a thing yourself anyway.
Google has data structure libraries. They write low-level code like kernels that has no library of data structures. They implement programming languages where they need to implement data structures from scratch. Lots of need to do it.
- voodootrucker 7y agoEach 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.