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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Encode and Decode TinyURL and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →