Интервью Вопрос: HashSet - Как получить наименее используемый объект?

Question

Черт возьми, у меня сейчас было адское интервью.Независимо от того, сколько вы готовите, вы идете и забыть все.:)

Я думал, что поделюсь вопросом, пока он свеж в моей памяти.

1) У вас есть 1000 объектов, которые хранятся в кеше.Вы должны создать кэш эффективным способом, чтобы время поиска было очень коротким.

Очевидно, они искали HashSet, который обеспечивает постоянное время доступа.

2) Как получить объект в кеше, который использовался минимум (не самый старый, но минимум)?Что использовать в качестве хеш-кода для достижения этой цели и как получить эту корзину без каких-либо дорогостоящих поисков?

Я думал использовать метку времени объектов в качестве хэш-кода.Но как бы получить наименее используемый объект без поиска?

Answer 1

Мое решение (я недавно реализовал что-то подобное) состоит в том, чтобы иметь Dictionary (Hashset) и заказанный LinkedList.LinkedList будет содержать элемент и счетчик доступа.Когда вы хотите получить свой элемент, вы смотрите на Dictionary, чтобы получить узел LinkedList, затем увеличиваете счетчик и продвигаете узел вперед, чтобы сохранить список отсортированным.Когда вы хотите получить наименее часто используемый элемент, вы берете голову (или хвост) списка.

Это делает поиск O(1) и вставку O(n) в худшем (очень редком) случае и O(1) в лучшем случае.

Answer 2

Я думаю, что они собирались использовать что-то вроде алгоритма наименьшего количества недавно использованных кешей. Больше информации здесь в википедии: Алгоритмы кэширования

В этом вопросе StackOverflow есть также кэш LRU .