JavaScript Interview Questions: LRUCache

Problem Statment

Design a data structure for LRU Cache. It should support the following operations:

Key Design Points:

• LRUCache(capacity:number) Initialize the LRU cache with a positive size capacity.
• get(key:number): any| number: Return the value of the key if the key exists, otherwise return -1.
• put(key: string | number, value: any): Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
• The functions get and put must each run in O(1) average time complexity.

Solution Explanation

LRUCache can be implemented in a multiple ways. But to provide time complexityO(1) we have mostly one way to do it — By using a Map and List

1. Map: For faster lookup
2. List: To maintain the sequence and capacity.

At high level, it will work as follow

• On put add an entry to a map and put it in the first position in List
• On get return the entry form Map and reorder the list by removing the corresponding node and put at the first position (Head).
• On put if the capacity exhausted, remove the last entry (Tail) from the List.

Following this strategy will give you the critical O(1) the average time complexity for get and put

Solution

Try on Leetcode

Link: https://leetcode.com/problems/lru-cache/

My Solution’s Score:

Thanks! 👋