Leetcode#146

Problem Statement

Logic

The secret to breaking down problems and avoiding overly complicated logic lies in systematic thinking and modularization. Here’s a structured approach to develop this mindset:

1. Understand the Problem Deeply

• What is required?
  • Identify the core requirements: In this case, maintaining an LRU cache means:
    • Access (get) a value in O(1).
    • Add or update a value in O(1).
    • Remove the least recently used item when capacity is exceeded.
• What operations are repeated?
  • From the problem:
    • Adding a node at the head (most recently used).
    • Removing a node (cleaning up when evicting).
    • Moving a node to the head.
• What is the simplest structure to satisfy these?
  • A combination of a map (fast access) and a doubly linked list (maintaining order of usage).

2. Decompose the Problem

• Split the problem into sub-problems. Ask:
  • What small, reusable operations will achieve the desired behavior?
  • For LRU Cache:
    • Adding to the head is frequent → Needs its own function.
    • Removing a node can happen in multiple cases (eviction or moving a node) → Needs its own function.
    • Moving a node involves removal and addition → Can use the above two functions.
• Write down these sub-tasks as standalone, logical operations before thinking of the bigger picture.

3. Make Logic Explicit

• Avoid trying to do multiple things in a single function.
• A function should do one thing well:
  • addToHead(node): Focuses only on adding a node to the head.
  • removeNode(node): Focuses only on safely unlinking a node from the list.
  • moveToHead(node): Combines removeNode and addToHead logically.
• Each sub-function should be:
  • Short: Easier to read and debug.
  • Reusable: Can be used in multiple contexts (e.g., moving to head reuses removal and addition).

4. Think Iteratively

• Start small and build incrementally:
  1. Implement a doubly linked list.
  2. Test addToHead, removeNode, and their interaction.
  3. Integrate the map for O(1) access.
  4. Add the eviction logic when capacity is exceeded.

5. Ask: “What Can Go Wrong?”

• To keep logic simple, think about edge cases early:
  • What if the list is empty?
  • What if there’s only one node?
  • What if the capacity is just 1?
• Anticipating these cases ensures your solution is robust without needing convoluted fixes later.

6. Practice Modularization

• Always ask:
  • Is this function doing more than one thing? If yes, break it down.
  • Can this logic be reused? If yes, make it a standalone function.
  • Example:
    • Without modularization:

func moveToHead(node *Node) {
    // Logic to unlink a node
    // Logic to add node to head
}

• With modularization:

func moveToHead(node *Node) {
    removeNode(node)
    addToHead(node)
}

7. Visualize the Data Flow

• For linked lists, sketch the structure:
  • What happens when a node is added? Removed? Moved?
  • Visualizing ensures you don’t miss edge cases like dangling pointers.

8. Iterate and Refactor

• Once the logic is working:
  • Look for repeated code.
  • Simplify without breaking modularity.

How This Applies to LRU Cache

By applying the above principles:

1. You recognize the repeated patterns (add to head, remove node, move node).
2. Break them into modular functions:
   • addToHead(node): Focuses on marking as “most recently used.”
   • removeNode(node): Cleanly removes a node.
   • moveToHead(node): Combines the above.
3. Use these primitives to build Get and Put, making them concise and intuitive

Mindset Shift: Think Like LEGO

• Think of your code as LEGO blocks:
  • Each block (function) does one thing.
  • Complex structures (features) are built by assembling blocks.
  • Changing one block doesn’t break the rest.

With practice, this modular, structured way of thinking becomes second nature, making your code both clean and efficient.

Golang Solution

type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

type LRUCache struct {
	nodeMap    map[int]*Node
	head       *Node
	tail       *Node
	capacity   int
	currentLen int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		nodeMap:    make(map[int]*Node),
		capacity:   capacity,
		currentLen: 0,
	}
}

func newNode(key int, value int) *Node {
	return &Node{
		key:   key,
		value: value,
	}
}

func (this *LRUCache) moveToHead(node *Node) {
    this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUCache) addToHead(node *Node) {
    node.next = this.head
    node.prev = nil
    if this.head != nil {
        this.head.prev = node
    }
    this.head = node
    if this.tail == nil {
        this.tail = node
    }
}

func (this *LRUCache) removeNode(node *Node) {
    if node.prev != nil {
        node.prev.next = node.next
    }

    if node.next != nil {
        node.next.prev = node.prev
    }

    if node == this.head {
        this.head = node.next
    }

    if node == this.tail {
        this.tail = node.prev
    }
}

func (this *LRUCache) Put(key int, value int) {
    // if exist then overwrite
    if node, exist := this.nodeMap[key]; exist {
        node.value = value
        this.moveToHead(node)
    } else {
        // new node add at head
        // check capacity exceed 
        //     if yes remove tail 
        node := newNode(key, value)
        this.nodeMap[key] = node
        this.addToHead(node)
        this.currentLen++
        if this.currentLen > this.capacity {
            delete(this.nodeMap, this.tail.key)
            this.removeNode(this.tail)
            this.currentLen--
        }
    }

}

func (this *LRUCache) Get(key int) int {
	if ptr, found := this.nodeMap[key]; found {
        this.moveToHead(ptr)
        return ptr.value
    }
    return -1
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

Output

Input
["LRUCache","put","put","get","put","get","put","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]

Please visit https: https://codeandalgo.com for more such contents.