Amortized-Analysis Investigation of a Production Cache
Overview
What this challenge is about.
Read the C++ cache source (around 1,800 lines, custom open-addressing with periodic resize-and-rehash). Perform amortized analysis using all three methods (aggregate, accounting, potential) for insert, lookup, and evict. Identify why p99 spikes correlate with rehash events (likely candidate: O(n) rehash on a 10M-entry table). Propose two redesigns (incremental rehash, or a different data structure like a hopscotch hash) with amortized bounds for each operation. Implement the better choice and re-measure p99. Deliver a 10-page technical analysis, the implementation, and a benchmark report.
The Brief
What you'll do, and what you'll demonstrate.
Perform an amortized analysis of a production cache, identify the rehash-driven p99 spike, and prove a redesign with better worst-case behavior.
Earning criteria — what you'll demonstrate
- Apply aggregate, accounting, and potential amortized-analysis methods to real code
- Connect amortized bounds to observed production latency
- Design hash-table redesigns with better worst-case operations
- Translate algorithmic analysis into production redesign decisions
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
Careers
Roles this prepares you for.
Real titles. Real skill bridges. Pick the one closest to your trajectory.
Career mappings coming soon.