A URL shortener is a lookup problem wearing an algorithm costume
Everyone reaches for a clever hash. The interview is really testing whether you notice this is a read-heavy key-value problem, not a puzzle.
Design a URL shortener. Where do you start?
Not with the encoding. With one number: the read-to-write ratio.
Why that first?
It's about 100 reads for every write. That one fact decides most of the design.
How so?
It tells me this is a lookup-and-cache problem, not a write-throughput problem.
Fine. Hash the long URL, take the first seven characters. Done?
That's the trap. Two different URLs can hash to the same code.
So rehash on a clash.
A clash means a read-before-write check on every insert. Your clean write path is gone.
Any other problem with hashing?
Yes. The same URL always hashes to the same code. You can't give two people separate links.
So what makes the code, if not the content?
Decouple them. Generate a unique 64-bit ID, then encode that.
Why does that fix it?
The ID is unique by construction. No collisions, no read-before-write, nothing serial in the way.
Encode it how?
Base62. Just digits and letters.
Why not base64? It's right there.
Base64 uses plus, slash, equals. Those break when pasted into a URL. Base62 never does.
next id: 1,000,000,007 -> base62 -> "15ftgG" -> long URLWhere do the mappings live? Relational database?
A key-value store. The only query is: given a code, return the URL. A primary-key lookup.
Relational could do that too.
It could, but you'd never touch its joins or transactions. Wrong tool, more cost.
Reads are 100 to 1. So keep it all in Redis and skip the database?
No. A cache isn't a system of record. Redis restarts, every link dies.
So what's Redis for?
The hot keys only. Check cache, miss goes to the store, then populate the cache.
Last thing. Doesn't the ID counter become a bottleneck?
Only if you hand out IDs one at a time. Hand out blocks of a thousand.
And each server?
Serves its block locally. The counter is hit once per thousand writes, never on the hot path.
Closing line?
It's a read-heavy key-value lookup in disguise. Unique IDs, base62, a durable store, cache the hot keys.
↑ answer it in your head first ↑
Traps
- ⚠ Hashing the long URL to make the code. Collisions force a read-before-write on every insert, and identical URLs collapse to one link you cannot expire independently.
- ⚠ Treating the cache as the system of record. A restart with no durable store deletes every link, which is fatal for a service whose whole promise is permanence.
- ⚠ Reaching for a relational database when the only access pattern is a primary-key lookup.