2

Gosh I had right now a hell of an interview. No matter how much you prepare you go in and forget everything. :)

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?

Houman
  • 64,245
  • 87
  • 278
  • 460
  • 2
    I also don't think GetHashCode is a great way of determining age. – Ray Booysen Feb 21 '11 at 11:34
  • 1
    This is a trick question but unfortunately a very common one (not the specific question here, but *trick questions*). The problem with trick questions is that you either know the solution or you don't, but they are very hard to figure out yourself. A google search and some reading however, and you would easily find the solution to this problem. But if I were asked this question in an interview I would just say "I don't know, give me a browser and I'll find out". If that's not good enough, I wouldn't want to work there. – Lasse V. Karlsen Feb 21 '11 at 11:41
  • @Lasse V. Karlsen I don't think that this is trick question. It is just LFU cache, nothing fancy. Unless they want to abuse `GetHashCode` in some way. – Andrey Feb 21 '11 at 11:49

2 Answers2

1

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.

Community
  • 1
  • 1
Ray Booysen
  • 28,894
  • 13
  • 84
  • 111
1

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.

Andrey
  • 59,039
  • 12
  • 119
  • 163