Cache & Priority Systems

Notes and typical questions for Cache & Priority mechanism

Notes

These problems require maintaining a dynamically changing set of items ordered by some ranking rule (recency, frequency, priority, etc.), while supporting fast add, update, delete, and retrieval operations.

These problems combine:

• O(1) lookup (HashMap)

• Ordered maintenance (Heap / DLL / TreeMap)

• State mutation (priority/frequency/recency changes)

Focus:

• Maintain invariants

• Handle tie-breaking

• Coordinate multiple data structures correctly

• Understand space tradeoffs (lazy deletion vs strict removal)

Typical Questions

• 🌟 🟠 LC 146. LRU Cache

  • Idea: Implement with Map + Double Linked List (2 dummy nodes for head and tail, respectively)

  • Pitfalls

    • Connect the head and tail in the constructor

    • For put , it can be adding a new node or updating an existing node.

  • Optimal Answer.

    • TC: $O(1)$ for both get and put

    • SC: $O(capacity)$

• 🟠 LC 432. All O`one Data Structure

  • I only wrote a standard LRU solution. The reason I failed to come up with an O(1) solution

    • Missing the “only ±1 changes” leverage: Counts only changes by +1 or -1 each operation. That’s the crucial property that screams “adjacent bucket moves.” If you don’t consciously look for that kind of property, you’ll design a general reordering solution (yours), not a local-move solution (optimal).

  • Optimal Answer.

    • TC: $O(1)$ for all methods

    • SC: $O(n)$

• 🌟 🔴 LC 460. LFU Cache

  • Idea

    • Implement with 2 Maps

    • To get the LRU result when there is a tie, use LinkedHashSet()

  • Optimal Answer

    • TC: $O(1)$ for both get and put

    • SC: $O(capacity)$

• 🟠 LC 3408. Design Task Manager

  • Approach 1 - TreeMap+TreeSet:

    • Answer

      • TC: $O(logn)$ for all add, edit, rmv, execTop

      • SC: $O(n)$, only contains active tasks

  • 👍 Approach 2 - Map+Heap with lazy deletion

    • Optimal Answer.

      • TC:

        • $O(logn)$ for add, edit,

        • $O(1)$ for rmv

        • Amortized $O(logn)$ for execTop

      • SC: $O(n+m)$, may contain stale tasks in the heap.

• LC 716. Max Stack

  • Optimal Answer.

    • TC: $O(1)$ for top , $O(logn)$ for others

    • SC: $O(n)$