Encode and Decode TinyURL
mediumTime: O(1)Space: O(n)
Signals to notice
design URL shortenerencode long URL to shortdecode back
Brute force first
Not applicable — the challenge is the encoding scheme, not algorithmic complexity.
The key insight
Hash map: generate a unique short code (counter, random, or hash), store the mapping both ways. Encode returns the short URL; decode looks up the original. O(1) per operation.
What must stay true
The encoding must be bijective — each long URL maps to exactly one short URL and vice versa. A simple incrementing counter or random string works.
Easy way to go wrong
Hash collisions with random codes — either check for collisions or use a counter for guaranteed uniqueness.