Choose a Hash Table vs Trie for a URL-Shortener Cache
Overview
What this challenge is about.
Implement (1) a hash-table cache with linear probing and (2) a compressed trie cache, both with the same eviction policy (LRU). Measure (a) p50/p99 lookup latency, (b) memory footprint at 2M entries, (c) insert throughput. Run on the provided 24-hour anonymized trace (around 51M lookups). Compare results, then write a 6-page decision memo recommending one with a 'when this changes, revisit' section. Deliver source code, a benchmark report, and the memo.
The Brief
What you'll do, and what you'll demonstrate.
Choose between a hash table and a compressed trie for a 2M-entry URL-shortener cache backed by latency and memory measurements on a real trace.
Earning criteria — what you'll demonstrate
- Implement a hash table with linear probing and a compressed trie correctly
- Benchmark latency at p50 and p99, not just average
- Reason about memory footprint of pointer-heavy structures
- Write a decision memo that ages well under changing constraints
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.