I've implemented this for leetcode without realizing it's paper worthy: https://leetcode.com/problems/lfu-cache/

My implementation: https://pastebin.com/48mMTTdK

I am surprised to see that the paper was only published in 2010. I would expect something this simple to have been discovered earlier. I guess it's easy only after someone tells you constant time is possible.