In past interviews, I have been asked to implement:
- A linked list
- A BST
- A hashtable/hashmap
- A trie
- A k-d tree
More importantly, I've been asked to implement data structures that augmented the basic structures mentioned above (e.g. a hashmap with a constraint on the number of entries, with evictions based on LRU status).
The point of these questions was not to see if I had memorized the precise implementation details; when implementing the hashmap I did not bother trying to rehash when the number of entries crossed a threshold. Rather, it was to verify that:
- As a programmer, I at least have a familiarity with these structures
- As an engineer who is going to need to solve a problem, I can utilize and extend these structures in order to fit the needs of the solution
If you can describe the operations that occur on accessing a node in a splay tree, you can probably write passable code to implement them. What's much more important, though, would be to be able to speak intelligently about why you would be using a splay tree in the first place: what shape of data and patterns of data access would lead you to choose the structure, and what features of a splay tree would enable good performance in relevant metrics where other solutions would not.