Problem
Design a data structure that implements a Least Recently Used (LRU) cache with Get and Put operations in O(1) time. Implement the LRUCache class.
Test Cases
LRU eviction order
Input: capacity=2, Put(1,1), Put(2,2), Get(1)=1, Put(3,3), Get(2)=-1, Put(4,4), Get(1)=-1, Get(3)=3, Get(4)=4
Expected: All assertions pass