FixCode

Fix the Cache Implementation

Hard

Challenge 20 of 20

Fix the Cache Implementation

Hard

This LRU (Least Recently Used) cache implementation has a bug that causes it to evict the wrong items. Fix the implementation.

Challenge 20 of 20

80 XP

Community Solutions

Data StructuresCacheLRUMapJavaScript

Exit Challenge

Test Cases

0/2 passing

Test Case #1

Input: const cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(2);

Expected: -1 (because key 2 should be evicted)

Run tests to see results

Test Case #2

Input: const cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); cache.get(1); cache.put(3, 3); cache.get(1);

Expected: 1 (because key 1 was accessed most recently before key 2)

Run tests to see results

solution.js

<span class="token keyword">class</span> LRUCache {
  constructor(capacity) {
    <span class="token keyword">this</span>.capacity = capacity;
    <span class="token keyword">this</span>.cache = <span class="token keyword">new</span> Map();
  }
  
  get(key) {
    <span class="token keyword">if</span> (!<span class="token keyword">this</span>.cache.has(key)) {
      <span class="token keyword">return</span> -<span <span class="token keyword">class</span>="token number">1</span>;
    }
    
    <span class="token keyword">const</span> value = <span class="token keyword">this</span>.cache.get(key);
    <span <span class="token keyword">class</span>=<span <span class="token keyword">class</span>="token string">"token comment"</span>>// Move the accessed key to the end (most recently used)</span>
    <span class="token keyword">this</span>.cache.delete(key);
    <span class="token keyword">this</span>.cache.set(key, value);
    <span class="token keyword">return</span> value;
  }
  
  put(key, value) {
    <span <span class="token keyword">class</span>=<span <span class="token keyword">class</span>="token string">"token comment"</span>>// If key exists, update its value and move it to the end</span>
    <span class="token keyword">if</span> (<span class="token keyword">this</span>.cache.has(key)) {
      <span class="token keyword">this</span>.cache.delete(key);
    }
    <span <span class="token keyword">class</span>=<span <span class="token keyword">class</span>="token string">"token comment"</span>>// If at capacity, remove the first item (least recently used)</span>
    <span class="token keyword">else</span> <span class="token keyword">if</span> (<span class="token keyword">this</span>.cache.size >;= <span class="token keyword">this</span>.capacity) {
      <span class="token keyword">const</span> firstKey = <span class="token keyword">this</span>.cache.keys().next().value;
      <span class="token keyword">this</span>.cache.delete(firstKey);
    }
    
    <span class="token keyword">this</span>.cache.set(key, value);
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  
  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    
    const value = this.cache.get(key);
    // Move the accessed key to the end (most recently used)
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }
  
  put(key, value) {
    // If key exists, update its value and move it to the end
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    // If at capacity, remove the first item (least recently used)
    else if (this.cache.size >= this.capacity) {
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    
    this.cache.set(key, value);
  }
}

Console

Run your code to see output here

Previous ChallengeNext Challenge

Exit