Cache Line Eviction Simulator

Building a set-associative cache simulator with LRU eviction

This hard coding problem is representative of the systems-performance work that high-frequency trading firms like DE Shaw use to squeeze latency out of trading systems. It tests whether you can correctly implement a non-trivial hardware model: a set-associative cache with LRU (Least Recently Used) eviction and dirty-line tracking.

The core challenge is maintaining the invariants: computing set indices and tags from byte addresses, tracking recency order within each set without inefficiency, recognizing hits vs. misses, and crucially, counting writebacks only when a dirty line is evicted. Many candidates slip on the address-to-set/tag mapping, the mechanics of LRU ordering, or the conditions under which a writeback occurs. The problem requires careful bookkeeping across up to 100,000 accesses and tight correctness.

• Set-associative cache architecture and address decomposition
• LRU replacement policy and efficient ordering maintenance
• Hit vs. miss classification and cache state transitions
• Dirty bit tracking and writeback counting