Understanding Design URL Shortener in Java

Introduction & Problem Explanation

A URL Shortener (like TinyURL) is a critical utility in modern web infrastructure. It maps long, verbose URLs (which can exceed hundreds of characters) into short, clean aliases (typically less than 10 characters) like http://short.ly/xyz.

The system needs to support two operations:

• encode(longUrl): Generate a unique short URL for a given long URL. It must ensure that if the same long URL is submitted multiple times, it returns the same short code without wasting memory.
• decode(shortUrl): Find the original long URL associated with a short URL to facilitate redirection.

Both operations must execute in O(1) constant time complexity. To achieve this, we maintain two HashMaps to track the bidirectional mapping in memory, and generate short codes by converting a monotonically increasing counter into a Base36 alphanumeric string.

The Algorithmic Approach

Bidirectional Mapping + Base36 Conversion

We use a clean, in-memory implementation:

• Auto-Incrementing Counter: We maintain a running integer ID. When a new long URL arrives, we stamp it with the current ID and increment the counter.
• Base36 Encoding: An integer in base 10 uses 10 characters (0-9). In base 36, we use 36 characters (0-9 and a-z). This allows us to represent large numbers with very short strings. For example, the ID 100,000 is represented in Base36 as just "255s", saving significant space.
• Bidirectional HashMaps:
  map: maps the short code to the long URL.
  reverse: maps the long URL back to the short code. This ensures deduplication of requests.

Step-by-Step Execution Walkthrough

Let's trace a Codec object starting with an empty cache (counter ID = 1):

1. Step 1 (Encode first URL):
   • Request: encode("https://leetcode.com").
   • Check: Is it in the reverse map? No.
   • Convert current ID 1 to Base36: "1".
   • Update maps:
     map = {"1": "https://leetcode.com"}
reverse = {"https://leetcode.com": "1"}
   • Increment ID to 2. Return "http://short.ly/1".
2. Step 2 (Encode second URL):
   • Request: encode("https://google.com").
   • Convert current ID 2 to Base36: "2".
   • Update maps:
     map = {"1": "...", "2": "https://google.com"}
reverse = {"...": "1", "https://google.com": "2"}
   • Increment ID to 3. Return "http://short.ly/2".
3. Step 3 (Encode duplicate URL):
   • Request: encode("https://leetcode.com").
   • Check: Is it in the reverse map? Yes! Value is "1".
   • Return immediately: "http://short.ly/1" (no maps modified, ID stays 3).
4. Step 4 (Decode URL):
   • Request: decode("http://short.ly/1").
   • Extract short code: strip prefix to get "1".
   • Lookup: map.get("1") returns "https://leetcode.com".

Key Code Snippets & 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

Designing a URL Shortener showcases the power of database key mapping and base radix conversion. By converting sequential IDs into Base36 alphanumeric strings and tracking mappings bidirectionally, we facilitate instant redirections and deduplications in O(1) time.