Allowed R6 · Within policy
{
"slug": "thread-safe-lru-cache",
"title": "Thread-Safe LRU Cache",
"difficulty": "medium",
"tags": [
"coding",
"technical",
"swe",
"backend"
],
"is_free": true,
"locked": false,
"frequency": 0.75,
"last_reported_at": "2026-06-04T19:54:19.644153Z",
"url": "https://www.mokabla.com/en/c/ibm/thread-safe-lru-cache",
"agent": {
"page": "https://www.mokabla.com/agent/en/c/ibm/thread-safe-lru-cache",
"question": "https://www.mokabla.com/agent/_call/get_question?company=ibm&question=thread-safe-lru-cache"
},
"company": {
"slug": "ibm",
"name_en": "IBM Egypt"
},
"body_md": "## Problem\nWe run a Java microservice that fronts lookups against Cloud Object Storage, and we want a small in-process cache in front of it. Implement an LRU cache with a fixed capacity that supports `get(key)` and `put(key, value)` in O(1) average time. When the cache is full, evict the least recently used entry. Both `get` and `put` on an existing key count as a \"use\".\n\nOnce the single-threaded version works, I will ask how you would make it safe for concurrent calls from a Tomcat thread pool without wrapping every call in one global lock.\n\n## Examples\n**Example 1**, capacity 2: `put(1,\"a\")`, `put(2,\"b\")`, `get(1)` returns `\"a\"`, `put(3,\"c\")` evicts key 2, `get(2)` returns `-1`, `get(3)` returns `\"c\"`.\n\n**Example 2**, capacity 1: `put(\"x\",10)`, `put(\"x\",11)` overwrites with no eviction, `get(\"x\")` returns `11`, `put(\"y\",5)` evicts `\"x\"`, `get(\"x\")` returns `-1`.\n\n## Constraints\n- 1 ≤ capacity ≤ 10^5\n- Keys are strings or integers; values are arbitrary objects\n- `get` and `put` must be O(1) average, be ready to justify it\n\n## What they look for\nHash map plus doubly linked list with clean pointer surgery, handling the \"update existing key\" path, and a sensible concurrency discussion (`ConcurrentHashMap` + lock striping vs. `synchronized` vs. just using Caffeine). They want trade-offs, not a full concurrent implementation.",
"follow_ups_md": "- How would you add a TTL per entry without a background thread?\n- What changes if the cache must be shared by several pods?\n- Why is `LinkedHashMap` with `accessOrder=true` a valid answer in Java, and what is its catch?",
"access": "Question bodies are paid content: a person buys 30 days of access per company (200 EGP or 200 points) in the human app. Agents get titles, tags and difficulty; bodies only for free questions."
}