Encode and Decode TinyURL

medium design hash map string

Problem

Implement encode(long) → short and decode(short) → long for a URL shortener.

Inputencode("https://leetcode.com/problems/design-tinyurl")

Output"http://tinyurl.com/4e9iAk"

Randomize / counter; persist mapping in a hash map.

long URL

import random, string
class Codec:
    def __init__(self):
        self.map = {}
        self.base = "http://tinyurl.com/"
    def encode(self, longUrl):
        while True:
            tok = "".join(random.choices(string.ascii_letters + string.digits, k=6))
            if tok not in self.map: break
        self.map[tok] = longUrl
        return self.base + tok
    def decode(self, shortUrl):
        return self.map[shortUrl.split("/")[-1]]

class Codec {
  constructor() { this.map = new Map(); this.base = "http://tinyurl.com/"; }
  encode(longUrl) {
    let tok;
    do { tok = Math.random().toString(36).slice(2, 8); } while (this.map.has(tok));
    this.map.set(tok, longUrl);
    return this.base + tok;
  }
  decode(shortUrl) { return this.map.get(shortUrl.split("/").pop()); }
}

public class Codec {
    Map map = new HashMap<>();
    String base = "http://tinyurl.com/";
    Random rnd = new Random();
    public String encode(String longUrl) {
        String tok;
        do { tok = randTok(); } while (map.containsKey(tok));
        map.put(tok, longUrl);
        return base + tok;
    }
    public String decode(String shortUrl) { return map.get(shortUrl.substring(shortUrl.lastIndexOf('/') + 1)); }
    String randTok() {
        String chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) sb.append(chars.charAt(rnd.nextInt(chars.length())));
        return sb.toString();
    }
}

class Codec {
    unordered_map mp;
public:
    string encode(string longUrl) {
        string tok;
        const string ch = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        do { tok.clear(); for (int i = 0; i < 6; i++) tok += ch[rand() % 62]; } while (mp.count(tok));
        mp[tok] = longUrl;
        return "http://tinyurl.com/" + tok;
    }
    string decode(string shortUrl) { return mp[shortUrl.substr(shortUrl.find_last_of('/') + 1)]; }
};

Explanation

A URL shortener does not need to "compress" the long URL at all. The simplest reliable design is to invent a short, unique token and remember which long URL it stands for in a hash map. Decoding is then just a lookup.

The Codec holds a map from token to long URL plus a fixed base like http://tinyurl.com/. To encode, we generate a random 6-character token from letters and digits, and loop until we get one that is not already used, which guarantees uniqueness.

Once we have a fresh token, we store map[tok] = longUrl and return base + tok as the short URL.

To decode, we strip the token off the end of the short URL (everything after the last /) and return whatever long URL the map has stored under it. Both operations are O(1) on average thanks to the hash map.

Example: encode("https://leetcode.com/problems/design-tinyurl") might produce token 4e9iAk, store the mapping, and return http://tinyurl.com/4e9iAk. Calling decode on that short URL looks up 4e9iAk and returns the original long URL.

Time: O(1) per op Space: O(n)