Overview
What this challenge is about.
Build a hash table and compressed trie for a URL-shortener cache, benchmark both, then recommend one structure to earn your verifiable certificate.
The scenario
Linkfurt is a Berlin financial-technology firm whose URL-shortening service rewrites long payment, invoice, and statement links into short codes, serving roughly 600 million redirects a month with a small platform team of about 35 staff. At that volume, the choice of in-memory cache structure directly affects redirect latency and the per-instance memory bill.
The Brief
What you'll do, and what you'll demonstrate.
Decide whether a linear-probing hash table or a compressed trie is the better in-memory cache for two million URL short codes, justified by measured latency and memory results on the provided redirect trace.
Earning criteria — what you'll demonstrate
- Implement a linear-probing hash table and a compressed trie with identical caching semantics and a shared least-recently-used eviction policy
- Design a reproducible benchmark that reports median and tail (99th-percentile) latency, memory footprint, and insert throughput rather than averages alone
- Measure and reason about in-memory data-structure footprint at the two-million-entry scale
- Translate measured engineering trade-offs into a defensible written recommendation for a platform team
- Articulate the conditions (traffic shape, key length, memory budget) under which an infrastructure decision should be re-evaluated
Program Fit
Where this fits in your program.
Sharpens the same skills your degree expects you to demonstrate.
Aligned coursework coming soon.
Skills
Skills you'll demonstrate.
Each one shows up on your verified credential.
- Hash Tables
Apply hash tables to solve real industry problems and demonstrate production-level capability.
- Trie Data Structure
Apply trie data structure to solve real industry problems and demonstrate production-level capability.
- Benchmarking
Apply benchmarking to solve real industry problems and demonstrate production-level capability.
- Memory Analysis
Apply memory analysis to solve real industry problems and demonstrate production-level capability.
- Decision Memos
Apply decision memos to solve real industry problems and demonstrate production-level capability.
- Complexity Analysis
Apply complexity analysis to solve real industry problems and demonstrate production-level capability.
Careers
Career paths this challenge builds toward
Completing this challenge demonstrates skills that transfer directly to these roles:
Backend Engineer
This challenge mirrors a core backend task: choosing and proving an in-memory data structure under real traffic instead of guessing. You leave able to implement caches correctly and justify the choice with measured evidence, the everyday work of a backend engineer on a platform team.
This challenge sharpens
- hash-tables
- trie-data-structure
- benchmarking
Platform / Infrastructure Engineer
Platform engineers constantly weigh latency against memory cost at scale. By measuring footprint at two million entries and writing a revisit-conditions memo, you practise the capacity-aware, decision-documenting judgment that defines the platform role.
This challenge sharpens
- memory-analysis
- benchmarking
- decision-memos
Staff Engineer (Technical Decision-Maker)
Staff-level work is largely defensible recommendations others can act on. Turning complexity analysis and benchmark data into a clear memo with explicit trade-offs and revisit triggers is exactly the evidence-to-decision skill this challenge builds.
This challenge sharpens
- complexity-analysis
- decision-memos
- memory-analysis