Model N Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
the problem states that search should be of order O(1).
Using Hashtable might cost O(n).
I feel, along with doubly linked list of nodes, an array of nodes should be used. the insert 'value' can be index and value is the 'node' in the doubly linked list.
The doubly linked list will help in maintaining 'Recent' and 'Oldest' node.
This will result in insert, delete, search ops in the O(1)
@Anonymous:
Hashtable contains a pointer to a node in the linkedlist.
On access of a key, you move the node to the head of the linked list.
On eviction, you remove from the tail.
@bluesky: Yes this is expected O(1) and could potentially degrade for some keys. The question does not say guaranteed O(1), and besides this is the "standard" implementation.
As to your array idea, you are assuming the keys will be integers and small enough that your array won't be prohibitively large. Why should that be the case? (And if you try to map the keys to bounded integers, you are in fact trying to hash them!).
I think the key here is cache associativity. If the cache is n way associative (but not fully associative), meaning each cache unit size can only be mapped to 1 of n location in the cache where n is constant, then the insertion, deletion and search time becomes a predetermined constant in the worst case. Although you will need a linked list at the same time to track least recently used caches, recently used are put to the head and not used cache are automatically left towards the tail. Deletion, insertion, and taking the tail element of the linked list are also constant time operations.
Use hashtable + doubly linked list.
- Loler September 28, 2012