This is a classic Google interview probem, and frequently used in user-orientied application implementations.
In case the problem is not clear, we are designing a data structure that can hold a set amount of data, once the data limit is reached the oldest/first-inserted data will be erased from the data base since it’s considered ‘lease used’. With the same idea if we get or call a data no matter when it was inserted it will be now the newest or most recent used data.
In summary, this ds needs to be able to set a size and push out old data if size is reached. That sounds like a doubly linked list! This ds also needs to be able to retrive a data point and put it front of the list if it is called upon, sounds like we also need a dictionary or hash map to keep track of each node.
So our ideas are:
- each data is a dll node with pre and next pointer
- inserted node will be added to the head of the dll, and it’ll be remembered by our dictionary (node.val:node)
- get will retrive that node from the dictionary and reassign it’s neighor’s pointer to remove it from dll and insert again
- there will always be a head and a tail node (null nodes) to better keep track of the head and tail even in zero size.