Как бы ты реализовывал LRU cache?

Так тоже спрашивают:

• Реализуй LRU-кеш с Get и Put за O(1).