Encode and Decode TinyURL

How it works

This approach uses two hash maps to create a bidirectional mapping. One maps long URLs to short URLs, and the other maps short URLs back to long URLs. This ensures that encoding the same long URL twice returns the same short URL, avoiding duplicates. The trade-off is using more memory for the extra map.

Steps

1. Maintain two hash maps: encodeMap (longUrl to shortUrl) and decodeMap (shortUrl to longUrl).
2. encode(longUrl):
   • If longUrl is not in encodeMap, create a new short URL using the current count.
   • Store the mapping in both encodeMap and decodeMap.
   • Return the short URL.
3. decode(shortUrl):
   • Look up the short URL in decodeMap and return the corresponding long URL.

Complexity

• Time complexity: O(1) for encode() and decode().
• Space complexity: O(n * m)

Where n is the number of longUrls, m is the average length of the URLs.

Things to watch for

Not Handling Duplicate URLs Consistently

If the same long URL is encoded multiple times, some implementations generate different short URLs each time, wasting storage. Using a bidirectional mapping (approach 3) ensures the same long URL always returns the same short URL, but this trade-off uses more memory.

Incorrect Parsing of the Short URL

When decoding, you must correctly extract the ID from the short URL. Common mistakes include not handling the base URL prefix properly, using the wrong string split method, or forgetting to convert the extracted string to an integer before lookup.

Integer Overflow with Sequential IDs

Using a simple incrementing integer ID works for small scale, but can overflow for very large numbers of URLs. In production systems, consider using larger integer types, UUIDs, or base62 encoding to handle billions of URLs while keeping short URLs compact.

class Codec:

    def __init__(self):
        self.encodeMap = {}
        self.decodeMap = {}
        self.base = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.encodeMap:
            shortUrl = self.base + str(len(self.encodeMap) + 1)
            self.encodeMap[longUrl] = shortUrl
            self.decodeMap[shortUrl] = longUrl
        return self.encodeMap[longUrl]

    def decode(self, shortUrl: str) -> str:
        return self.decodeMap[shortUrl]

class Solution {
private:
    unordered_map<string, string> encodeMap;
    unordered_map<string, string> decodeMap;
    string base = "http://tinyurl.com/";

public:
    string encode(string longUrl) {
        if (encodeMap.find(longUrl) == encodeMap.end()) {
            string shortUrl = base + to_string(encodeMap.size() + 1);
            encodeMap[longUrl] = shortUrl;
            decodeMap[shortUrl] = longUrl;
        }
        return encodeMap[longUrl];
    }

    string decode(string shortUrl) {
        return decodeMap[shortUrl];
    }
};