Design a service with create(longUrl) and redirect(shortCode) that generates collision-free identifiers, stores the mapping, handles cache misses and expiration, and limits abuse.
Before you code
Decide the key-generation strategy (base62 from a counter/ULID/Snowflake, or hash+collision check) and whether short links need to be globally unique and unpredictable.
Hints
- Base62 over a monotonically increasing ID avoids collisions if the ID space is managed.
- For custom aliases, check uniqueness in a store; consider expiration.
- Plan for redirection: return 301/302/308 with correct cache headers.
Production & complexity notes
When solving Design a Short-Link Service on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Cache-Conscious Data Structures: Alignment, False Sharing, and Structure of Arrays to reinforce the underlying pattern.
What it practices
URL shortening: ID space design, collision avoidance, and HTTP redirection semantics, from What a hash function does.