Design a data structure for LRU cache

Question

Sigiloso · Accepted Answer

There are many ways to do this

Sigiloso · Answer

Would a Priority Queue work here? If we have a hash function to help us the lookup, then we might have to just end up truncating tail of the Queue and add element to the head or vice versa.

Ganesh · Answer

In java, just extend the LinkedHashMap

    static class MyLru extends LinkedHashMap {

        int capacity;

        public MyLru(int capacity){
            super(capacity,0.75f,true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            if(size()>capacity) {
                return true;
            }
            return false;
        }
    }

Google

Pergunta de entrevista da empresa Google

Respostas da entrevista

Empresas seguidas

Buscas de vagas