Реализуйте LRU-кэш с операциями get(key) и put(key, value) за O(1). При переполнении выкидывайте давно не использованный элемент.