Implement an LFU cache with O(1) operations

Q: Implement an LFU cache with O(1) operations

This question evaluates a candidate's ability to design and implement efficient data structures for caching, including understanding frequency-based eviction policies, maintaining recency ordering for tie-breaking, and meeting strict time-complexity guarantees.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Design and implement an LFU (Least Frequently Used) cache.

The cache supports:

get(key) : return the value for key if present, else return -1 .
put(key, value) : insert or update the key with value .

Rules:

When the cache reaches capacity, it should evict the entry with the lowest access frequency .
If multiple entries share the same lowest frequency, evict the least recently used among them.
A successful get increments that key’s frequency.
A put on an existing key updates the value and increments frequency.
If capacity is 0 , all operations should be no-ops and get always returns -1 .

Performance requirement

get and put should run in amortized O(1) time.

Input/Output style (for interview)

You may be given a sequence of operations and must output results of get operations.

Implement an LFU cache with O(1) operations

Quick Overview

Performance requirement

Input/Output style (for interview)

Comments (0)