Back to solutions

Encode and Decode TinyURL

MediumArrays

Map long URLs to short keys and back.

Open problem
Constraints
  • 1 <= q <= 10^4
  • URLs are valid strings

Counter key with a map

Time O(1) per callSpace O(number of URLs)

Keep a hash map from a generated short key to the original URL. encode mints a new unique key (here an incrementing counter appended to a base) and stores the mapping; decode just looks the key up. This is reversible and O(1) per call.

Key terms
surrogate key:
A short generated identifier standing in for the long URL.
lookup table:
The map that lets decode reverse the encoding.
string encode(const string& longUrl) {
    string key = "http://tinyurl.com/" + to_string(counter++);
    toLong[key] = longUrl;
    return key;
}
string decode(const string& shortUrl) { return toLong[shortUrl]; }
Step by step
  1. encode: create a unique short key (base + counter) and store key -> longUrl.
  2. Return the short key.
  3. decode: return the stored long URL for the given short key.
  4. Because each key is unique, the round trip always recovers the original.