CareerCup

It is an classic problem - implement it by using one queue and a HashMap\Table ?
Each time you access an element from the map, remove it from last and add it at front of queue.

HashMap will hold direct references to nodes in queue, so it will be a O(1) operation to find it in queue.

The most recently used pages will be near front end and least recently pages will be near rear end

If you know Java good and it is allowed to be lazy, we can reuse LinkedHashMap to achieve the desired behavior.

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.function.Function;

/**
 * Created by sis on 6/4/15.
 */
public class CareerCup_5735022524891136 {
    public static void main(String[] args) {
        LRU<Integer, Integer> cache = new LRU<>(2, s -> {
            System.out.println(s);
            return s;
        });

        // new value
        cache.apply(1);
        // use cache
        cache.apply(1);
        // new value
        cache.apply(2);
        // new value, 1 is pushed from cache
        cache.apply(3);
        // use cache
        cache.apply(2);
        // new value because we removed 1 previously
        cache.apply(1);
    }

    /**
     * LRU implementation as a pattern 'Proxy'.
     * @param <K> key type
     * @param <V> value type
     */
    public static final class LRU<K, V> implements Function<K, V> {
        private final LinkedHashMap<K, V> map;
        private final Function<K, V> realSubject;

        public LRU(final int size, Function<K, V> realSubject) {
            this.realSubject = realSubject;
            this.map = new LinkedHashMap(16, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return this.size() == size + 1;
                }
            };
        }

        @Override
        public V apply(K k) {
            V v = map.get(k);
            if (v == null) {
                v = realSubject.apply(k);
                map.put(k, v);
            }

            return v;
        }
    }
}

Use two data structures in tandem:

1) A "move to front" doubly linked list (that is, every time an element is accessed, it gets moved to front of the list.... each node of list represents a page in this case)
2) hash table mapping page identifiers of some sort to references in the double linked list

So here is how things work.

Assume only M pages can exist in the cache.

Now whenever a page is accessed, check to see if it's in the hash table.
Case 1: Cache Miss
----------------------------
If it is NOT, check if number of elements in the LIST is < M.
If it is < M, simply add the element to head of the list, and add corresponding entry in hash table, and move the page into cache.
If we already have M elements in the LIST, we must remove the LRU page.
Use tail pointer to the list and remove the last element there (i.e., delete it from the list, delete it from hash table AND delete the page from the cache itself).

Case 2: Cache hit
-------------------------
Page does exist in hash table. Follow the hash table ("value" is reference to node in doubly linked list) to get the node pointer. Now do some pointer magic to move the node to head of the list.


Everything is O(1).

Email me for opportunities in the Waterloo/Toronto, Ontario area.