Реализуйте LRU-кэш с ограничением capacity, в котором при переполнении удаляется элемент, к которому дольше всего не обращались; операции get и put должны работать за константное время.