Understanding Design URL Shortener in Java

A URL Shortener (such as TinyURL or Bitly) is a vital tool in modern web architecture. It maps long, complex web addresses (which can easily span hundreds of characters) to short, clean aliases (typically under 10 characters). This makes URLs easy to share in emails, social media posts, and messages.

To build a fully functional URL shortener, we must support two core operations:

• encode(longUrl): Generates a unique, short alias for a given long URL. It must be idempotent—meaning multiple requests for the same URL should return the same short code.
• decode(shortUrl): Looks up the original long URL associated with a short alias to facilitate instant redirecting.

To handle high volumes of traffic, both encoding and decoding must run in O(1) constant time. We can achieve this by maintaining two bidirectional HashMaps in memory and generating short codes using a Base36 conversion on an auto-incrementing counter.

Design Strategy

Our design leverages two principal mechanisms:

• Base36 Encoding: Standard decimal integers use base 10 (characters 0–9). By switching to base 36 (using 0–9 and a–z), we can represent large numbers using much shorter strings. For example, the auto-incremented ID 1,000,000 translates to the Base36 string lfls. This allows us to keep URLs short.
• Double HashMaps:
  • map stores the short code as the key and the long URL as the value, ensuring instant redirection.
  • reverse stores the long URL as the key and the short code as the value, preventing duplicate registrations.

Step-by-Step Execution Walkthrough

Let's trace the execution of the codec with an empty database:

1. Encoding a New URL: A request to encode "https://leetcode.com" arrives. We check the reverse map; since it's a new URL, we convert the current ID (1) to its Base36 representation ("1"). We store the bidirectional mapping and increment the ID to 2. The returned short URL is http://short.ly/1.
2. Encoding Another URL: Next, we encode "https://google.com". The ID (2) becomes "2". We save the mappings, increment the ID to 3, and return http://short.ly/2.
3. Handling Duplicates: We request encode("https://leetcode.com") again. The system finds the URL in the reverse map and returns the existing short link http://short.ly/1 immediately without incrementing the counter.
4. Decoding: A request to decode http://short.ly/1 arrives. We strip the domain prefix to get "1", lookup "1" in our decode map, and retrieve the original URL: https://leetcode.com.

Key Code Explanations

Here is why the main logic in the solution is important:

• Integer.toString(id++, 36): The core code generation line. It converts the current numeric counter into a Base36 alphanumeric string and increments the counter in a single, atomic operation.
• if (reverse.containsKey(longUrl)): Deduplication check. Ensures we do not consume database or memory space for repeated queries of the same URL.
• shortUrl.replace(base, ""): Isolates the base36 code from the domain prefix, allowing us to perform index lookups in our internal map directly.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;
 
import java.util.*;
 
public class DesignURLShortener {
 
    public static class Codec {
        // Map to decode: stores shortCode -> longUrl
        private final Map<String, String> map = new HashMap<>();
        
        // Map to encode/deduplicate: stores longUrl -> shortCode
        private final Map<String, String> reverse = new HashMap<>();
        
        private final String base = "http://short.ly/";
        private int id = 1;
 
        public Codec() {
            // Constructor
        }
 
        // Encodes a URL to a shortened URL.
        public String encode(String longUrl) {
            // Return existing short URL if already processed
            if (reverse.containsKey(longUrl)) {
                return base + reverse.get(longUrl);
            }
            
            // Convert current incrementing ID to a Base36 alphanumeric code
            String code = Integer.toString(id++, 36);
            
            // Store mappings bidirectionally
            map.put(code, longUrl);
            reverse.put(longUrl, code);
            
            return base + code;
        }
 
        // Decodes a shortened URL to its original URL.
        public String decode(String shortUrl) {
            // Strip the base URL prefix to isolate the code
            String code = shortUrl.replace(base, "");
            return map.getOrDefault(code, "");
        }
    }
 
    public static void main(String[] args) {
        Codec codec = new Codec();
        System.out.println("--- Design URL Shortener Demonstration ---");
        
        String originalUrl = "https://leetcode.com/problems/design-tinyurl";
        System.out.println("Original URL: " + originalUrl);
        
        String shortUrl = codec.encode(originalUrl);
        System.out.println("Encoded (Shortened) URL: " + shortUrl);
        
        String decodedUrl = codec.decode(shortUrl);
        System.out.println("Decoded (Restored) URL:  " + decodedUrl);
        
        System.out.println("\nChecking deduplication...");
        String shortUrlDuplicate = codec.encode(originalUrl);
        System.out.println("Second Encoding of same URL: " + shortUrlDuplicate);
        System.out.println("Is same short URL generated: " + shortUrl.equals(shortUrlDuplicate));
    }
}

Conclusion & Practical Takeaways

This in-memory URL shortener provides high performance with O(1) runtime complexity for both encoding and decoding. By using bidirectional HashMaps and Base36 conversion, we ensure data consistency and minimal memory footprint, forming a strong foundation for a production-grade system.