My Java solution using map and priorityQueue


  • 0
    T

    I made the structure separate for clarity, though not concise. I have a map to store the values, and a priorityQueue to store access timestamp so that the oldest can be easily dequeue'ed. then when an key is either read or written, we need to find the corresponding queue item to update the queue, so we need another map to link from the key to the actual priorityqueue item.

    a first impl using java.util.PriorityQueue works fine but for larger input gives Timeout. so I borrowed the approach of one other user's solution, and gave a simplified impl of PriorityQueue using double-linked list.

    public class LRUCache {
    
    static class Freq {
        public int key;
        public int ts;
        public Freq prev;
        public Freq next;
        public Freq(int key) {this.key = key;}
        public void setTs(int ts) {this.ts = ts;}
        public boolean equals(Object o) { return ((Freq) o).key == (this.key);}
    }
    
    
    // a linkedList implementation of priority queue,
    static class MyQ {
        int size;
        Freq head = new Freq(0);
        Freq tail = new Freq(0);
        public MyQ() {
            size= 0;
        head.next = tail;
        tail.prev = head;
        head.prev = null;
        tail.next = null;
        }
        public void remove(Freq f) {
            f.next.prev = f.prev;
            f.prev.next = f.next;
            size--;
        }
        
        public Freq poll() {
            if (head.next == tail) return null;
            Freq result = head.next;
            Freq tmp = head.next.next;
            head.next = tmp;
            tmp.prev = head;
            size--;
            return result;
        }
        
        public void offer(Freq f) {
            size++;
            f.next = tail;
            f.prev = tail.prev;
            tail.prev.next = f;
            tail.prev = f;
            
        }
        
        public int size() {
            return this.size;
        }
    }
    
            Map<Integer, Integer> buf = new HashMap<Integer,Integer>();
        
        Map<Integer, Freq> freqBuf = new HashMap<Integer, Freq>();
        
        MyQ freq;
        
        int capacity;
    public LRUCache(int capacity) {
    
        this.capacity = capacity;
         freq = new MyQ();
    }
    
    int ts = 0;
    
    public int get(int key) {
        if ( !buf.containsKey(key)) return -1;
        int result = buf.get(key);
        
        Freq f = freqBuf.get(key);
        freq.remove(f);
        f.setTs(ts++);
        freq.offer(f);
        
        return result;
    }
    
    public void set(int key, int value) {
        buf.put(key,value);
        
        if (!freqBuf.containsKey(key)) {
            
            Freq f = new Freq(key);
            f.setTs(ts++);
            
            if (freq.size() == capacity) {
                Freq f1 = freq.poll();
                freqBuf.remove(f1.key);
                buf.remove(f1.key);
            }
            freq.offer(f);
            freqBuf.put(key, f);
        } else {
            Freq f = freqBuf.get(key);
            freq.remove(f);
            f.setTs(ts++);
            freq.offer(f);
        }
        
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.