Design and implement an LRU cache
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## 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.
Quick Answer: This question evaluates knowledge of data structures, algorithmic design, API design, and memory/resource management required to implement an efficient eviction-based cache (LRU) that supports constant-time operations.