LRU (Least Recently Used) Cache

A Quick Overview

We need to design and implement a data structure for LRU (Least Recently Used) cache. It should support two operations -

Problem Statement

1. get(key) - Get the value (always positive) of the key if it exists in cache, otherwise returns -1.  2. set(key, value) – Set or insert value if the key is not already present.

Input: [“LRUCache”, “set”, “set”, “get”, “set”, “get”, “set”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]  Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Example-

LRU cache is implemented using hashed linked list, which is composed of a hash map and a doubly linked list. But why a hashed linked list?

1. For set function, update value of given node and insert it at front of hashed-linked list.  2. If a node with given value already exists, delete it & update pointers.

Approach

Time Complexity: O(1) for all operations  Space Complexity: O(N), as extra space is used

How to implement this approach in different programming languages?