🫠 Задача на выходные: LRU Cache

Классика интервью. Проверяет знание STL, сложности операций и дизайн-мышление😸

// Реализуй класс LRUCache:
// - LRUCache(int capacity)
// - int get(int key) // O(1)
// - void put(int key, int val) // O(1)
//
// При переполнении вытесняется
// наименее недавно использованный элемент.
//
// Разрешено использовать STL.

✏️ Реализуй. Объясни выбор структур данных и почему сложность O(1).