Implement LRU, Extend to LFU, Analyze Complexity

Implement an in-memory Least Recently Used (LRU) cache with capacity N that supports get(key) -> value and put(key, value). Achieve O( 1) average time per operation using appropriate data structures; justify your choices and analyze time and space complexity. Follow-up: Modify the design to implement a Least Frequently Used (LFU) cache with O( 1) or amortized O( 1) operations; explain the eviction policy, how you track and update frequencies on get/put, and how you break ties by recency.