Encode and Decode TinyURL
mediumTime: O(1)Space: O(n)
Recognize the pattern
design URL shortenerencode long URL to shortdecode back
Brute force idea
Not applicable — the challenge is the encoding scheme, not algorithmic complexity.
Better approach
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.
Key invariant
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.
Watch out for
Hash collisions with random codes — either check for collisions or use a counter for guaranteed uniqueness.