You're designing an LRU cache that keeps only recently used items. To make get and put average O(1), what does the HashMap do and what does the doubly linked list do?
The [Key: Node] Dictionary is only the index that jumps from a key to its list node in O(1); the doubly linked list keeps the recency order, head most recent and tail oldest, so a node can be unlinked and moved to the front or removed from the end in O(1).
CS fundamentals and algorithmsShort answerIntro
What's the difference between a stack and a queue?
#data-structure
CS fundamentals and algorithmsMultiple choiceIntro
You're picking a data structure for the message list on a chat screen. Which is the most…
#linked-list
CS fundamentals and algorithmsShort answerAdvanced
You need to write an in-memory image cache with LRU eviction yourself. Which data…
#linked-list
CS fundamentals and algorithmsShort answerAdvanced
You've implemented an LRU cache and the interviewer follows up: "Now make each entry…
#linked-list