How to Implement an O(1) LRU Cache for Interview Success

Problem Statement

The interview question asks to design an LRU (Least Recently Used) cache where both put and get operations must run in O(1) time.

Approach

The solution combines a hash table for constant‑time key lookup with a doubly linked list to record usage order. When a key is accessed or inserted, its node is moved to the front of the list; the tail holds the least‑recently used element.

Key Operations

Put : Insert new data at the head of the list. If the key already exists, update its value and move the node to the front. If the cache is full, remove the tail node and delete its entry from the hash table.

Get : If the key exists in the hash table, move the corresponding list node to the front and return its value; otherwise return –1.

Implementation Details

The Go struct LRUCache holds a map from int keys to *list.Element and a *list.List representing the doubly linked list. The constructor initializes the map with the given capacity and creates a new list.

type LRUCache struct {
    m map[int]*list.Element // hash table storing list nodes
    l *list.List            // doubly linked list
    cap int                 // cache capacity
}

type Data struct {
    Key   int
    Value int
}

func Constructor(capacity int) LRUCache {
    cache := LRUCache{}
    cache.m = make(map[int]*list.Element, capacity)
    cache.l = list.New()
    cache.cap = capacity
    return cache
}

func (this *LRUCache) Get(key int) int {
    if v, ok := this.m[key]; ok {
        this.l.MoveToFront(v)
        return v.Value.(Data).Value
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if v, ok := this.m[key]; !ok {
        if this.cap == this.l.Len() {
            data := this.l.Remove(this.l.Back())
            delete(this.m, data.(Data).Key)
        }
        e := this.l.PushFront(Data{key, value})
        this.m[key] = e
    } else {
        v.Value = Data{key, value}
        this.l.MoveToFront(v)
    }
}

/** Usage
 * obj := Constructor(capacity)
 * param1 := obj.Get(key)
 * obj.Put(key, value)
 */

Visual Illustration

The article includes two diagrams that depict the list ordering after put/get operations and the eviction of the tail element when capacity is exceeded.