Katkat
Back

Design a Cache with Hit Counts

DatabricksSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This question tests the ability to design a thread-safe, high-performance cache that maintains frequency metadata alongside data, requiring an understanding of efficient data structures and concurrency control.

Problem Statement

Design a thread-safe FrequencyCache class that stores key-value pairs and tracks the total number of times each key has been accessed via get operations. Your implementation must support the following operations with optimal time complexity:

  • put(key, value): Inserts or updates the value associated with the key. The read count for a newly added key is 0.
  • get(key): Returns the value for the key if it exists and increments its read count. If it does not exist, return None.
  • delete(key): Removes the key-value pair and its associated read count.
  • get_read_count(key): Returns the number of times get(key) has been successfully called for this key.

Constraints

  • The cache should be thread-safe to handle concurrent reads and writes.
  • Operations should ideally be O(1) on average.
  • Consider the trade-off between performance and memory consistency.

Example

cache = FrequencyCache()
cache.put("a", 10)
cache.get("a")    # Returns 10, count for "a" is 1
cache.get("a")    # Returns 10, count for "a" is 2
cache.get_read_count("a") # Returns 2
cache.delete("a")
cache.get("a")    # Returns None

Edge Cases

  • Accessing a non-existent key.
  • Deleting a key that doesn't exist.
  • High contention on a single key's read count.

Hints

Hint 1

Use two separate hash maps: one to store the key-value mapping and another to store the key-count mapping.

Hint 2

To ensure thread safety, use a ReentrantLock or ReadWriteLock to manage access to the shared state.

Hint 3

If using a language with fine-grained locking, consider locking individual entries or using atomic integers for the counters to improve concurrency.

Follow-up questions

  • How would you modify your design to support a TTL (Time-To-Live) for each key?
  • If the system requires persistence, how would you asynchronously back up the hit counts to a database without blocking the `get` operations?
  • How would you implement a 'top-K' frequently accessed keys feature efficiently in this cache?