Thread-safe LFU Cache
Few comments from my side:
Looks like a code bug:
I think you want to use ReentrantLock to manage concurrent operations in multithreaded environment. But in your code I don't see any place where you have made a call to lock (neither lock() nor tryLock(long timeout, TimeUnit unit)). While unlock() is used couple of time, which is of no use in this case.
Other suggested updated:

CacheAlgorithm interface should be rather renamed to Cache only. Because it doesn't make sense in any class to make use of word Algorithm.

Code should prevent using abbreviations as much as possible. So LFU should be renamed to LeastFrequentlyUsed. Which is not a very big name. Along that it should be ended with Cache to make it more clear to user. So the better name would be LeastFrequentlyUsedCache.

It would be better to have a default constructor with default capacity, as Java API has for Collection classes.

Avoid auto-boxing and auto-unboxing in code. As these are heavy operations. Rather do custom boxing and unboxing as below:



final int frequency = frequencies.get(key).intValue();
final Set&lt;K&gt; keys = frequencyToKeys.get(Integer.valueOf(frequency));