Merge Sort on LL, Flatten LL & LRU Cache

LRU Cache Implementation Architecture

Combines a **Doubly Linked List** (for $O(1)$ node eviction & promotion) with a **HashMap** (for $O(1)$ key lookup).

Production Code Example:

import java.util.HashMap;
public class LruCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { this.key = k; this.val = v; }
    }
    private final int cap;
    private final HashMap<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);

    public LruCache(int capacity) {
        this.cap = capacity;
        head.next = tail; tail.prev = head;
    }
}

Key Complexity & Algorithmic Takeaways:

When implementing Merge Sort on LL, Flatten LL & LRU Cache in coding interviews and production applications, keep these core guidelines in mind:

• Time Complexity Analysis: Always evaluate best-case, average-case, and worst-case time complexities ($O(1)$, $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$).
• Space Complexity & Memory Bounds: Account for auxiliary memory usage, call stack frame recursion overhead, and heap allocations.
• Edge Cases & Validation: Test empty inputs, null pointers, single-element collections, duplicate values, and integer overflow bounds.
• Optimal vs Naive Solutions: Start with a clear brute-force solution, then optimize using techniques like Hashing, Two Pointers, Windowing, or Dynamic Programming.

Summary Takeaway:

Mastering Merge Sort on LL, Flatten LL & LRU Cache provides the foundational problem-solving skills needed to pass technical coding interviews at top tech companies and write ultra-performant software systems.