educative.io

Educative

Time complexity in LFU and LRU

Hi,
I am a bit confused about the solution for the LFU (and LRU) in the netflix category.

How is deleting a random node in a linked list O(1) ?

LinkedListNode Get(int key) {
    if(!keyDict.containsKey(key)){
      	return null;
    }
    LinkedListNode temp = this.keyDict.get(key);
    **this.freqDict.get(temp.freq).remove(temp);**
    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 LinkedList<LinkedListNode>());
    }
    this.freqDict.get(this.keyDict.get(key).freq).addLast(this.keyDict.get(key));
    return this.keyDict.get(key);
}

the java 8 source implementation is :

    public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        **for (Node<E> x = first; x != null; x = x.next) {**
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

Am i missing something?

Hi @Damien

Thank you for pointing this out. We have added our own implementation of the LinkedList and update the solution. You can review the changes now.

Have a great time learning!

Best Regards,
Faizan Zia
Technical Content Engineer