Skip to content

Instantly share code, notes, and snippets.

@Vandivier

Vandivier/lru.js Secret

Created February 13, 2022 18:55
Show Gist options
  • Save Vandivier/ea2228f8f363417aa6392612e5399449 to your computer and use it in GitHub Desktop.
Save Vandivier/ea2228f8f363417aa6392612e5399449 to your computer and use it in GitHub Desktop.
odinho's JS LRU adapted to LC
Based on [this](https://stackoverflow.com/a/46432113/3931488) Stack Overflow answer and trivially adapted to fit [LeetCode 146. LRU Cache](https://leetcode.com/problems/lru-cache/)
```
var LRUCache = function(capacity) {
this.max = capacity;
this.cache = new Map();
};
LRUCache.prototype.get = function(key) {
let item = this.cache.get(key);
if (item) {
// refresh key
this.cache.delete(key);
this.cache.set(key, item);
}
return item === undefined ? -1 : item;
};
LRUCache.prototype.first = function() {
return this.cache.keys().next().value;
};
LRUCache.prototype.put = function(key, val) {
// refresh key
if (this.cache.has(key)) this.cache.delete(key);
// evict oldest
else if (this.cache.size >= this.max) this.cache.delete(this.first());
this.cache.set(key, val);
};
```
@odinho
Copy link

odinho commented Feb 14, 2022

It's written to solve a problem in a real code base. Not meant as the fastest ever, though it should be plenty fast, but the main thing is readability and terseness.

But, it seems to work for me:
Screenshot from 2022-02-14 21-24-45

@Vandivier
Copy link
Author

@odinho the code above passes many test cases including the basic / default case available when you click Run Code. It fails some more complex cases and not on account of timing out. I believe it is due to the eviction logic (I'm also not saying you're wrong or they are right, I think there's a case to be made that there are some extra assumptions in the leetcode solution, idk)

Here's a specific case:

image

@issacgerges
Copy link

issacgerges commented Oct 3, 2023

The issue is the here.

The truthyness of item is being used to determine if the key needs to be refreshed. In the leetcode test the value is 0, which coerces to false. Since false/undefined/empty string are all fair values, you'd instead explicitly want has

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment