What if we never had to remove entries from the LRU cache because we had enough space, what would you use to support and get and set?


#1

Design Cache Q: What if we never had to remove entries from the LRU cache because we had enough space, what would you use to support and get and set?


#2

map with doubly LL


#3

HashMap with Double linked list


#4

we do not need DLL here as we never have to remove entries.


#5

But we have to maintain the access order. When we access a particular entry, we have to bring it to front to maintain LRU order. How can we do that without using DLL ?


#6

that's the point, LRU is significant word only when we need to remove entries. Other than that there's no need of LRU. therefore only a map would work fine


#7

In this case we wont be needing the DLL because we won't be deleting any entries and whole purpose of DLL is to maintain the accessing sequence so when we have to remove a entry we can delete the entry which is least expected to requested.


#8

we can use linked hash map, it will solve LRU problem


#9

We can do it with 2 stacks and map also.


#10

Hi! What do you mean by 2 stacks?


#11

If there is no eviction required under current assumptions then there is no LRU happening, it is just get & set.
Assuming most people are quoting Java, Hashmap is the wrong answer as it doesn’t support concurrency. ConcurrentMap ( or Hashtable ) is the right data structure to use.


#12

No A map plus a doubly linked list is required. Map is to search for the key and DLL for updating the node so that the least recently used node can we evicted when the memory is full.


#13

A hash-map and a DLL is required, The hash map will guide with the address and the DLL will eventually guide the eviction in less time


#14

We could use an unordered set instead of doubly linked list along with a map.


#15

A simple Hashmap would work since we have enough space and there is no eviction required.


#16

HashMap with Double linked list


#17

We will need only an unordered map and not map, because map will sort the values and rearrange them in an order while unordered map will preserve the order of the pages, in which they are referred.
There’s no need of DLL as we have enough space and we are not deleting entries from the cache