AlgoMaster Logo

Encode and Decode TinyURL

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

This is a system design question shaped into a coding problem. We need two functions that are inverses of each other: encode maps a long URL to a short one, and decode maps that short URL back to the original. The short URL can be anything we choose, as long as the round-trip works.

Multiple valid approaches exist, each with different trade-offs around collision handling, predictability, and determinism. The core challenge is not algorithmic complexity (every reasonable approach is O(1) per call) but the design decisions and how you justify them.

Key Constraints:

  • 1 <= url.length <= 10^4 → URLs can be moderately long, but we're not dealing with massive data. Any in-memory solution is fine.
  • url is guaranteed to be a valid URL → No need for URL validation logic.
  • The problem guarantees that decode is only called with URLs produced by encode → We don't need to handle invalid short URLs.

Approach 1: Counter-Based

Intuition

Assign each URL a unique number. Keep a counter that starts at 0 and increments every time a new URL is encoded. The short URL becomes http://tinyurl.com/0, then http://tinyurl.com/1, and so on. To decode, look up the number in a map.

This is the brute force of URL shortening. It guarantees uniqueness without any collision handling, and both operations run in O(1). The cost is predictability. Anyone who sees http://tinyurl.com/42 can infer that http://tinyurl.com/41 also exists. For a production service that is a security concern, but for this problem it works.

Algorithm

  1. Maintain a counter (starting at 0) and a hash map from integer ID to long URL.
  2. On encode: store the long URL with the current counter as key, build the short URL as http://tinyurl.com/{counter}, increment the counter, and return the short URL.
  3. On decode: extract the numeric ID from the short URL, look it up in the hash map, and return the original long URL.

Example Walkthrough

map (id -> longUrl)
1Initialize: empty map, counter = 0
output
1Initialize: no output yet
1/6

Code

The counter-based approach produces sequential integers that are easy to enumerate. The next approach generates keys that cannot be guessed from neighboring URLs.

Approach 2: Random Key Generation

Intuition

Generate a random alphanumeric string for each URL instead of a sequential ID. Pick 6 characters from [a-zA-Z0-9] (62 choices per position), giving 62^6 ≈ 56.8 billion possible keys. The chance of a collision is negligible for any realistic number of URLs.

We maintain two hash maps: one from short key to long URL (for decoding), and one from long URL to short key (to avoid encoding the same URL twice). This gives both unpredictable URLs and deduplication.

Algorithm

  1. Define an alphabet of 62 characters: a-z, A-Z, 0-9.
  2. On encode: check if the long URL was already encoded. If yes, return the existing short URL. Otherwise, generate a random 6-character key, check for collisions, store the mapping in both directions, and return the short URL.
  3. On decode: extract the key from the short URL and look it up in the key-to-URL map.

Example Walkthrough

keyToUrl
1Initialize: empty keyToUrl map
urlToKey
1Initialize: empty urlToKey map (reverse lookup to avoid duplicate encodings)
output
1Initialize: no output yet
1/6

Code

The random approach is non-deterministic. Two different instances of the class produce different short URLs for the same input. The next approach is deterministic: the same URL always maps to the same short URL, which removes the need for the url2code dedup map.

Approach 3: Hash-Based (Deterministic)

Intuition

Use a hash function on the long URL to produce the key instead of a random string. Java's built-in hashCode() maps the URL to an integer, and that integer becomes the key directly. This approach is deterministic: the same URL always produces the same integer, and therefore the same short URL, which removes the need for a reverse map.

The trade-off is that hash collisions are possible: two different URLs can produce the same integer. We handle this by linear probing. If the key is already taken by a different URL, increment it by 1 and try again until a free slot is found. The probe sequence is deterministic, so decode never needs to know it happened. It reads back whatever integer encode settled on, and that integer is embedded in the short URL.

Algorithm

  1. On encode: compute hashCode of the long URL and use it as the key.
  2. While the key is occupied by a different URL, increment the key by 1.
  3. Store key -> longUrl, then return http://tinyurl.com/{key}.
  4. On decode: parse the integer after the last / and look it up in the map.

Example Walkthrough

map (hashKey -> longUrl)
1Initialize: empty map
output
1Initialize: no output yet
1/8

Code

Comparing the Approaches

All three approaches run in O(1) per call and O(n) space, so the choice comes down to the properties of the generated key rather than performance.

Scroll

Approach

Key

Predictable?

Deterministic?

Dedup of repeats

Maps

Counter

Sequential integer

Yes

Yes

No (each call gets a new id)

1

Random

Random 6-char string

No

No

Yes (via reverse map)

2

Hash

Integer hash of the URL

No

Yes

Yes (same hash for same URL)

1

The counter is the easiest to implement and reason about, which makes it a good starting point. Its sequential keys are enumerable, so it is the wrong choice when keys need to be unguessable.

The random approach removes that predictability and reuses a short URL for a repeated input, at the cost of a second hash map and a result that differs between runs.

The hash approach is deterministic with a single map: the same URL always maps to the same key, so repeats collapse without a reverse lookup. The cost is collision handling. The linear-probe loop keeps it correct, but a weak hash function or many colliding inputs degrades its worst case. All three approaches are valid solutions, and the discussion of these trade-offs is the substance of the problem.