algoadvance

Leetcode 535. Encode and Decode TinyURL

Problem Statement:

The “Encode and Decode TinyURL” problem is all about designing a system for encoding and decoding URLs, similar to the services provided by TinyURL. Specifically, you’ll need to implement two methods:

  1. String encode(String longUrl): This method takes a long URL and returns a tiny URL.
  2. String decode(String shortUrl): This method takes a tiny URL and returns the original long URL.

The key challenges here are to ensure that:

Clarifying Questions:

  1. Does the short URL need to follow a specific format (e.g., fixed-length, specific characters allowed)?
    • Typically, TinyURL uses a base62 encoding (0-9, a-z, A-Z), but we can tailor this based on specific requirements.
  2. Is there a limitation on how long the URLs can be?
    • Generally, there is no fixed limitation but understanding any constraints could help with optimization.
  3. Do we need to handle duplicate URLs, and should they map to the same short URL?
    • Yes, the same long URL should always map to the same short URL.

Strategy:

  1. Data Storing Strategy:
    • We’ll use two HashMaps to store the mappings:
      • longToShort: maps long URLs to their short form.
      • shortToLong: maps short URLs back to their original long form.
  2. Encoding Strategy:
    • For encoding, generate a unique short key for each new long URL using a counter or a random character generator.
    • To keep URLs short, base62 encoding will be used to manage the generated keys effectively.
  3. Decoding Strategy:
    • Simply use the shortToLong map to retrieve the original URL.
  4. Avoid Collisions:
    • Ensure unique short URLs using unique ID generation techniques and checking for existing mappings.

Code:

import java.util.HashMap;
import java.util.Random;

public class Codec {

    private HashMap<String, String> longToShort;
    private HashMap<String, String> shortToLong;
    private static final String CHAR_SET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private static final String BASE_URL = "http://tinyurl.com/";
    private static final int KEY_LENGTH = 6;
    private Random rand;

    public Codec() {
        longToShort = new HashMap<>();
        shortToLong = new HashMap<>();
        rand = new Random();
    }

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (longToShort.containsKey(longUrl)) {
            return longToShort.get(longUrl);
        }

        String shortUrl = "";
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < KEY_LENGTH; i++) {
                sb.append(CHAR_SET.charAt(rand.nextInt(CHAR_SET.length())));
            }
            shortUrl = BASE_URL + sb.toString();
        } while (shortToLong.containsKey(shortUrl));

        longToShort.put(longUrl, shortUrl);
        shortToLong.put(shortUrl, longUrl);
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return shortToLong.get(shortUrl);
    }
}

Time Complexity:

This solution ensures efficient encoding and decoding operations even with a considerable volume of URLs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI