-
-
Save Vandivier/ea2228f8f363417aa6392612e5399449 to your computer and use it in GitHub Desktop.
odinho's JS LRU adapted to LC
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 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:
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
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:
