educative.io

Educative

LFU: Is implementation correct?

See my comment inline:

    LinkedListNode Get(int key) {
    if(!keyDict.containsKey(key)){
      	return null;
    }
    LinkedListNode temp = this.keyDict.get(key);
    this.freqDict.get(temp.freq).deleteNode(temp);
// here temp == this.keyDict.get(key), 
// therefore if this.freqDict.get(this.keyDict.get(key).freq) 
// can return null we will have NullPointerException on above line
// and will never get into below if-statement. 
// Am I missing something here?
    if(this.freqDict.get(this.keyDict.get(key).freq) == null){
        this.freqDict.remove(this.keyDict.get(key).freq);
        if(this.minFreq == this.keyDict.get(key).freq){
            this.minFreq += 1;
        }
    }
    this.keyDict.get(key).freq += 1;
    if(!this.freqDict.containsKey(this.keyDict.get(key).freq)){
        this.freqDict.put(this.keyDict.get(key).freq, new MyLinkedList());
    }
    this.freqDict.get(this.keyDict.get(key).freq).append(this.keyDict.get(key));
    return this.keyDict.get(key);
}

Also coding style is a bit strange, why not replace multiple this.keyDict.get(key) calls with a local variable? Those calls do have a cost.


Type your question above this line.

Course: https://www.educative.io/collection/10370001/4938268330688512
Lesson: https://www.educative.io/collection/page/10370001/4938268330688512/5632413361766400