Design and implement an LRU cache

Problem

Design and implement an LRU (Least Recently Used) Cache that supports the following operations in O(1) average time:

• get(key) → returns the value associated with key if present; otherwise returns a sentinel (e.g., -1 ). Accessing a key counts as making it most recently used .
• put(key, value) → inserts or updates the value for key . If the cache exceeds its capacity, it must evict the least recently used item.

Requirements

• The prompt may describe data structures in C; you may implement in C or C++ (clarify your choice).
• Define the cache API (constructor/init, get , put , cleanup/free if needed).
• Handle edge cases:
  • Updating an existing key
  • Capacity = 0
  • Repeated get calls

Input/Output (for testing)

You may assume the interviewer will test by calling your API methods in sequence (typical library-design style), rather than via stdin/stdout.