codejump
EasyPythonJavaScriptTypeScript

System Design — URL Shortener

System DesignHash MapBase Conversion

The core of a bit.ly-style service: turn a long URL into a short code and back.

solve(args, ops) builds new Shortener(startId) — args = [startId] — and replays ops:

  • shorten(url) — return the short code for url. The first new URL gets id

startId, the next new URL startId + 1, and so on. The **same URL always returns the same
 code** and does not consume an id.

  • expand(code) — return the original URL, or null for an unknown code.

The code is the id written in base 62 with the alphabet
0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ (so 10 → "a",
61 → "Z", 62 → "10"). Using a counter instead of a hash guarantees there are no
collisions; encode it yourself, without toString(62) (which does not exist for 62).

Example (startId = 61)

shorten("x") → "Z"    shorten("y") → "10"    shorten("x") → "Z"    expand("10") → "y"

Sample tests

Test #1Dedup and lookup
Input: [[1],[["shorten","https://a.dev"],["shorten","https://b.dev"],["shorten","https://a.dev"],["expand","2"],["expand","zz"]]]
Output: ["1","2","1","https://b.dev",null]
Test #2Rolling over to two digits
Input: [[61],[["shorten","x"],["shorten","y"],["shorten","z"],["expand","10"]]]
Output: ["Z","10","11","y"]
Test #3Rolling over to three digits
Input: [[3843],[["shorten","p"],["shorten","q"]]]
Output: ["ZZ","100"]
← All challenges