Design LFU Cache

Design a cache with capacity cap supporting get k and put k v. When full, put evicts the least frequently used key; ties are broken by evicting the least recently used among them. A get miss prints -1.

1 <= cap <= 10^4 O(1) per operation expected