Implement an LFU cache with O(1) operations
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design and implement an **LFU (Least Frequently Used) cache**.
The cache supports:
- `get(key)`: return the value for `key` if present, else return `-1`.
- `put(key, value)`: insert or update the key with `value`.
Rules:
1. When the cache reaches capacity, it should evict the entry with the **lowest access frequency**.
2. If multiple entries share the same lowest frequency, evict the **least recently used** among them.
3. A successful `get` increments that key’s frequency.
4. A `put` on an existing key updates the value and increments frequency.
5. If capacity is `0`, all operations should be no-ops and `get` always returns `-1`.
### Performance requirement
- `get` and `put` should run in **amortized O(1)** time.
### Input/Output style (for interview)
You may be given a sequence of operations and must output results of `get` operations.
Quick Answer: This question evaluates a candidate's ability to design and implement efficient data structures for caching, including understanding frequency-based eviction policies, maintaining recency ordering for tie-breaking, and meeting strict time-complexity guarantees.