Composite structures
Two structures over the same items, each one pointing into the other, so that every method finds what it needs without a search and leaves both of them agreeing.
Problems worked on this page, and more to practise
- 146. LRU Cache
- 380. Insert Delete GetRandom O(1)
- 460. LFU Cache
- 232. Implement Queue using Stacks
- 706. Design HashMap
- 155. Min Stack
- 981. Time Based Key-Value Store
- 1146. Snapshot Array
- 355. Design Twitter
- 208. Implement Trie (Prefix Tree)
- 895. Maximum Frequency Stack
- 295. Find Median from Data Stream
- 432. All O`one Data Structure
Why does an LRU cache need a doubly linked list?
Because eviction needs the oldest item and a read needs to move an item to the newest end, and both have to cost the same whatever the cache holds. A doubly linked list takes a node out in two pointer writes, given the node. Singly linked is not enough: to unlink a node you need the one before it, and finding that means walking from the front. The hash map is what hands you the node in the first place, so nothing is ever searched for.
Can I use collections.OrderedDict for LRU in an interview?
Say it out loud, then offer to build it by hand. OrderedDict has move_to_end and popitem, so the whole cache is about ten lines, and knowing that is worth points. But the question is almost always testing whether you can build the map-plus-list structure yourself, and interviewers will usually ask for it. Writing the short version first and the long version second is a good use of the clock.
Why does the node have to store its own key?
Because eviction starts from the node and has to end at the dictionary. You find the least recently used node from the tail of the list, unlink it, and then you have to delete its entry from the map. The only handle you have at that moment is the node, so unless the node carries the key, there is nothing to delete by. It is the single most common omission in a first draft of this problem.
How can a set support insert, delete and a uniform random pick, all in O(1)?
Keep an array of the values and a dictionary from each value to its index in that array. A random pick is one random index, which only works while the array has no holes in it. So deleting moves the last value into the hole and shortens the array, and then writes the moved value new index back into the dictionary. Forgetting that last write is what breaks the structure two operations later.
How do I know a problem needs two structures rather than one?
List the operations and the cost each one is required to hit, then ask which structure delivers each. If one structure covers the whole list, use it and stop. If lookup by key needs a hash map and something else needs an order, a rank or a uniform pick, no single structure gives you both, and the answer is two of them with pointers between. A second structure you do not need is a second thing to keep in step, and that is where bugs come from.