VMware Interview Question: Implement a LRU cache that ca... | Glassdoor

Interview Question

Staff Engineer Interview Palo Alto, CA

Implement a LRU cache that can be initialized with a max

  size (in bytes) and keeps track of the hits/misses.
Answer

Interview Answer

1 Answer

0

public class LRUCache {
    private Map cache = new LinkedHashMap();
    private int capacity = Integer.MAX_VALUE;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public Object get(String key) {
        if (cache.get(key) != null) {
            Object value = cache.get(key);
            synchronized (LRUCache.class) {
                makeKeyMostRecentlyUsed(key, value);
            }
            return value;
        }
        return null;
    }

    // If key exists in the cache ensure that once we get it
    // the key becomes most recently used (so remove & add to cache).
    private void makeKeyMostRecentlyUsed(String key, Object value) {
        if (cache.get(key) != null) {
            cache.remove(key);
            cache.put(key, value);
        }
    }

    public void put(String key, Object value) {
        if (cache.get(key) == null) {
            if (cache.size() >= capacity) {
                // when capacity is exceeded, remove the least recently used element
                // In linked hash map the beginning element will be least recently used.
                List list = new ArrayList(cache.values());
                cache.remove(list.get(0));
            }
            cache.put(key, value); // add it to the end.
        } else {
            // value exists, so remove and add it back with the updated value
            makeKeyMostRecentlyUsed(key, value);
        }
    }

    @Override
    public String toString() {
        return cache.values().toString();
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(5);
        cache.put("1", "1");
        cache.put("2", "2");
        cache.put("3", "3");
        cache.put("4", "4");
        System.out.println(cache);
        cache.put("5", "5");
        cache.put("6", "6");
        System.out.println(cache);
        cache.get("5");
        System.out.println(cache);
        cache.get("2");
        System.out.println(cache);

    }
}

Anonymous on Aug 16, 2017

Add Answers or Comments

To comment on this, Sign In or Sign Up.