535. Encode and Decode TinyURL

medium

Design a URL shortener: encode any long URL into a short one, then decode it back. The hash table is the whole system — short code -> long URL, with a counter or random key to mint new codes. Interview value is in the follow-up: how do you avoid collisions, how do you handle the same URL submitted twice, how do you scale across servers.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-25

Problem

TinyURL is a URL shortening service where you enter a long URL and it returns a short URL such as http://tinyurl.com/4e9iAk, and when you enter the short URL it redirects you to the original. Design a class with two methods: encode(longUrl) returns a tiny URL, and decode(shortUrl) returns the original URL from the tiny URL. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded back to the original URL.

Constraints

1 <= url.length <= 10^4
url is guranteed to be a valid URL.

Examples

Example 1

Input

url = 'https://leetcode.com/problems/design-tinyurl'

Output

'https://leetcode.com/problems/design-tinyurl'

Explanation: encode returns something like http://tinyurl.com/4e9iAk, decode of that returns the original input.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The shortest working solution: a hash map from a counter id -> long URL, plus a reverse map from long URL -> id to dedupe repeat submissions.

Hint 2

Use a fixed prefix like 'http://tinyurl.com/' and append the id encoded as a base-62 string (a-z, A-Z, 0-9).

Hint 3

For real systems you'd use a random 6-7 character key to avoid leaking submission order. For an interview, the counter version is fine — flag the tradeoff.

Solution approach

Reveal approach

Two hash maps and a counter. longToShort maps long URL -> assigned id (for deduping repeats). shortToLong maps id -> long URL (for decode). encode(longUrl): if longUrl already in longToShort, return the existing short. Otherwise increment a counter, record id = counter in both maps, return PREFIX + base62(id). decode(shortUrl): strip PREFIX, base62-decode to int, look up shortToLong[id]. Counter approach is O(1) per op and trivially collision-free. The alternative — random 6-char key with retry-on-collision — is more secure but only needed if leaking order matters. Both are acceptable; the interviewer is looking for the dedupe map and a clean separation of mint vs lookup.

Complexity

Time: O(1) per encode/decode
Space: O(n)

Related patterns

hash-map
design
two-hash-equality-test

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

Amazon
Google
Uber
Bloomberg