Design a least-recently-used cache with O(1) get and put.
Whether you can combine two data structures to hit a bound neither reaches alone.
System designStandard
What a strong answer does
The important constraint is not “build a cache,” it is “make both get and put O(1).” If you ever scan the cache to discover the least-recently-used item, you have already failed the requirement. A plain array or list can keep recency order but cannot find an arbitrary key in constant time. A plain hash map can find keys quickly but has no idea which key is oldest. That mismatch is what makes this a design question: no single obvious structure gives all the operations you need within the bound.
Where this is taught properly
- The KV Cache — Inference Engineering