48. Design an In-Memory Cache with Custom Eviction Policy : Low Level Design Interview Round

Design an In-Memory Cache with Custom Eviction Policy

Design an in-memory cache with a fixed capacity and a custom eviction policy. The user must provide the policy logic before initializing the cache.

At any point the cache can ask the policy which key will be selected for eviction next. Although an actual eviction will only take place if the cache has more elements than its maximum size after adding a new entry.

Eviction Policies

Eviction timing rule:
During put(key,value) for a new key, first insert the entry. If after insertion cache.size() > capacity, then evict exactly one key using the eviction policy.
(So the newly inserted key can be evicted if the policy chooses it.)

REMOVE-LARGEST-POLICY: Evict the entry with the largest key length. If multiple keys have the same maximum length, evict the entry with lexicographically smallest key among them.
REMOVE-HEAVIEST-POLICY: Evict the entry with the maximum key weight. If multiple keys have the same maximum weight, evict the entry with lexicographically smallest key among them.

Key weight is the sum of character values: a=1, b=2, ..., z=26.
Example: cab has weight 3 + 1 + 2 = 6.

Your design should make it easy to add more eviction policies in the future (e.g., Strategy pattern).

Methods

CacheBuilder(int capacity, String evictionPolicy)

Builds a cache builder configured with capacity and an eviction policy.

capacity is the maximum number of keys the cache can hold.
evictionPolicy is either REMOVE-LARGEST-POLICY or REMOVE-HEAVIEST-POLICY.

String get(String key)

Returns the value for key if present, otherwise returns .

key contains only a-z.

void put(String key, String value)

Inserts or updates an entry. May trigger eviction for new keys.

key and value contain only a-z.
If key exists: overwrite its value, and do not evict.
If key is new: first insert it, then if cache.size() > capacity, evict exactly one key chosen by the eviction policy.

String nextEvictionKey()

Reports the key that would be evicted next if eviction were needed right now.

Must not evict anything.
Return if the cache is empty.
Computed purely from the current keys using the configured eviction policy (largest length / heaviest weight, then lexicographically smallest tie-break).

boolean remove(String key)

Removes key if present.

Returns true if removed, else returns false.
key contains only a-z.

Examples

Example 1: INSERT-THEN-EVICT behavior (REMOVE-LARGEST-POLICY)


// capacity = 2, policy = REMOVE-LARGEST-POLICY
CacheBuilder(2, "REMOVE-LARGEST-POLICY")

put("a",   "v1")        // cache: { a }
put("bb",  "v2")        // cache: { a, bb }

nextEvictionKey() -> "bb"
  // among {a(len=1), bb(len=2)} => "bb" is largest length

put("ccc", "v3")
  // step 1 (insert first): cache becomes { a, bb, ccc }  (size=3)
  // step 2 (size > capacity): evict largest-length key among {a, bb, ccc} => "ccc"
  // final cache: { a, bb }

get("ccc") -> ""
get("bb")  -> "v2"

Example 2: Tie-break includes the newly inserted key (REMOVE-LARGEST-POLICY)


// capacity = 3, policy = REMOVE-LARGEST-POLICY
CacheBuilder(3, "REMOVE-LARGEST-POLICY")

put("bb", "1")          // cache: { bb }
put("aa", "2")          // cache: { bb, aa }
put("cc", "3")          // cache: { bb, aa, cc }

nextEvictionKey() -> "aa"
  // all len=2 => lexicographically smallest is "aa"

put("dd", "4")
  // insert first: { bb, aa, cc, dd } (size=4)
  // all len=2 => evict lexicographically smallest among 4 keys => "aa"
  // final: { bb, cc, dd }

get("aa") -> ""
get("dd") -> "4"

Example 3: REMOVE-HEAVIEST-POLICY (weight + lexicographic tie-break)


// capacity = 2, policy = REMOVE-HEAVIEST-POLICY
CacheBuilder(2, "REMOVE-HEAVIEST-POLICY")

put("az", "v1")         // weight("az") = 1 + 26 = 27
put("by", "v2")         // weight("by") = 2 + 25 = 27

nextEvictionKey() -> "az"
  // tie on weight 27 => lexicographically smallest is "az"

put("c", "v3")          // weight("c") = 3
  // insert first: { az, by, c } (size=3)
  // evict heaviest => weight 27 tie => evict "az"
  // final: { by, c }

get("az") -> ""
get("by") -> "v2"

Example 4: Updating an existing key does not evict + remove(key)


// continuing from a cache containing: { by, c } with capacity=2

put("by", "v9")          // update existing key, no eviction
get("by") -> "v9"

remove("by") -> true     // cache: { c }
remove("by") -> false    // already removed
get("by")    -> ""