You have to design a LRU cache such that all operations can be done in O(1) – read, write and insert.
- In case, cache is full, you have to remove an element which was read/written last.
- Each read should update the timestamp of these elements.
- Read request of the element contains a key which is not the location of the element.
Assuming hashmap has retrieval complexity of O(1), we can do this using a doubly link list and a Hashmap
- Doubly link list will be used to store indexes sorted by date/timestamp information.
- Keep track of first and last node.
- No sorting effort is needed as each new node will have latest timestamp.
- The Hashmap will retrieve the node searched by key. It will also contain pointer to its respective doubly link list node.
- Search the node by key. Retrieve the node value and index for doubly linklist.
- Delete the node from doubly linked list and add it with the updated date value at the starting of the list.
- Complexity of deleting a node in doubly link list is O(1) as we can reach to it without traversing the list.
- Add the new node in the hashmap and the doubly linked list.
- If the cache is full, use the pointer to the last node in the doubly linked list and delete that node. Set the delete pointer appropriately.
- Inserting at the start of linked list is operation with time O(1).
- Update operation will need similar operation as READ in terms of accessing the data structure. Hence, similar time complexities apply.
- Deleting the node from the doubly-linked list and hashmap can be done in O(1).
Queue with DLL + HashMap