Skip to main content
edited tags
Link
200_success
  • 145.6k
  • 22
  • 191
  • 480
deleted 1 characters in body; edited tags; edited title
Source Link
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Design LRU cache interview questions - code review request

Code reviewers, I request you review the code and suggest all tips for improvement.

Design LRU cache interview questions - code review request

Code reviewers, I request you review the code and suggest all tips for improvement

Design LRU cache interview questions

Code reviewers, I request you review the code and suggest all tips for improvement.

Source Link
JavaDeveloper
  • 8.5k
  • 29
  • 93
  • 162

Design LRU cache interview questions - code review request

Code reviewers, I request you review the code and suggest all tips for improvement

public class LRU<K, V> {
    
    private final Map<K, Entry<K, V>> map;
    private Entry<K, V> eldest;
    private final int lruSize;
    
    public LRU (int lruSize) {
        if (lruSize <= 0) {
            throw new IllegalArgumentException("size should atleast be one");
        }
        map = new HashMap<K, Entry<K, V>>();
        this.lruSize = lruSize;
    }
    
    private static class Entry<K, V> {
        Entry<K, V> left;
        K key;
        V value;
        Entry<K, V> right;
        
        Entry (Entry<K, V> left, K key, V value, Entry<K, V> right) {
            this.left = left;
            this.key = key;
            this.value = value;
            this.right = right;
        }
      
    };

    /**
     * Head is first node of the linked list.
     * Similar to - convert tree to doubly linkedlist.
     */
    private void addFirst(Entry<K, V> entry) {
        remove(entry);
        if (eldest == null) {
            entry.left = entry.right = entry;
            eldest = entry;
        } else {
            // last node of the list. extra storage just for purpose of simplification
            Entry<K, V> tail = eldest.left;
            
            tail.right = entry;
            entry.left = tail;
            
            // now deal with circularing
            eldest.left = entry;
            entry.right = eldest;
        }
    }
    
    private void remove (Entry<K, V> entry) {
        assert entry != null;
        
        if (entry.left != null) entry.left.right = entry.right;
        if (entry.right != null) entry.right.left = entry.left;
        if (entry == eldest) eldest = entry.right;
    }
    
    
    /**
     * Allowing null. Since, this is behavior of linkedhashmap.
     * Still adding synchronization as interviewer is bound to ask this question
     */
    public synchronized void put(K key, V value) {
        Entry<K, V> entry = new Entry<K, V>(null, key, value, null);
        map.put(key, entry);
        addFirst(entry);
     
        if (removeEldestEntry()) {
            remove(eldest.key);
        }
    }
    
    public synchronized V get (K key) {
        Entry<K, V> entry = map.get(key);
        if (entry != null) {
            addFirst(entry);
            return entry.value;
        }
        return null;
    }
    
    public synchronized void remove (K key) {
       Entry<K, V> entry = map.remove(key);
       if (entry != null) {
           remove(entry);
       }
    }
    
    private boolean removeEldestEntry() {
        return map.size() > lruSize;
    }
}