Interview Question: HashSet - How to get least used object?

Gosh I had right now a hell of an interview. No matter how much you prepare you go in and forget everyth开发者_如何学编程ing. :)

I thought I would share the question while it's fresh in my mind.

1) You have 1000 objects hold as a cache. You are supposed to create the cache in an efficient manner so that the search time is very short.

Obviously they were looking for a HashSet that provides constant access time.

2) How to get the object within the cache that was least (not oldest but least) used? What to use as hashcode to achieve this, and how to get this bucket without doing any expensive searching?

I was thinking to use the timestamp of the objects as a hashcode. But how would I get the least used object without doing any search?

My solution (I recently implemented something like this) is to have both Dictionary (Hashset) and ordered LinkedList. LinkedList will contain item and counter of access. When you want to get your item, you look into Dictionary to get node of LinkedList, then you increment counter and push node forward to keep list sorted. When you want to get least frequently used item you take head (or tail) of list.

This makes retrieval O(1) and insertion O(n) in worst (very rare) case and O(1) best case.

I think the way that they were going is to use something like a Least Recently Used cache algo. More info here on wikipedia: Cache Algorithms

There is also an LRU cache at this StackOverflow question.