Amazon Interview Question Software Engineer / Developers
0of 0 votesDesign a cache by Least Recently Used method (LRU).
Shouldnt a hash in association with a linked list do the required. The algorithm in the link seems to be very sophisticated and is going above my head at this point in time.
the input to the hash function shall be similar to how the memory calls for a page. A null pointer shall indiacte a page fault (O(n)) and o.w. it will point to a valid page in the memory.
Moving the page would be a mere pointer manipulation with O(1). IF somebody understands the algoirthm/paper associated with the link, please take some pain to explain it. Thanks in advance
Your approach does not seem to consider the eviction of the "LRU" hash entry problem. The real problem to solve for this question is how to identify the Least recent used hash entry- ideally in constant time so that any time spent on a cache miss is mainly the time required to load the new entry into the cache.
Maintain the items in order of access in a doubly linked list, along with pointers to the first and last nodes.
- Anonymous March 02, 2010Use a hash table with keys = items, values = location in linked list.
When you access an element, delete it from the linked list and re-insert it at the beginning. When you remove an element, delete it from the end and remove it from the hash table.