Encode and Decode TinyURL
Medium · Arrays & Hashing · Hash Table · String · Design · Hash Function
Problem
Build the core of a link shortener. Implement the class Codec:
- Codec() starts with no links.
- string encode(string longUrl) returns a short link for longUrl.
- string decode(string shortUrl) returns the long URL that shortUrl was made for.
So that every answer can be checked, the short links follow one fixed scheme. The first new URL gets number 1, the next new one number 2, and so on. A short link is "http://tinyurl.com/" followed by that number written in base 62 with the digits 0-9, then a-z, then A-Z (so 10 is "a", 61 is "Z" and 62 is "10"). Encoding a URL that was encoded before returns its existing link.
Each test is a list of calls: ops[i] is the method name (the first is the class) and args[i] its arguments. The expected output lists each call’s return value, None for the constructor.
Examples
Input: ops = ["Codec","encode","encode","decode","decode"], args = [[],["https://cariara.com/prep/library"],["https://example.com/a?q=1"],["http://tinyurl.com/2"],["http://tinyurl.com/1"]] Output: [None, 'http://tinyurl.com/1', 'http://tinyurl.com/2', 'https://example.com/a?q=1', 'https://cariara.com/prep/library']
The first new URL gets code 1 and the second code 2; decoding returns each original.
Input: ops = ["Codec","encode","encode","encode"], args = [[],["https://a.io/x"],["https://b.io/y"],["https://a.io/x"]] Output: [None, 'http://tinyurl.com/1', 'http://tinyurl.com/2', 'http://tinyurl.com/1']
Encoding https://a.io/x again returns its existing link.
Input: ops = ["Codec","encode","encode","encode","encode","encode","encode","encode","encode","encode","encode","encode","encode","decode"], args = [[],["https://site.io/p1"],["https://site.io/p2"],["https://site.io/p3"],["https://site.io/p4"],["https://site.io/p5"],["https://site.io/p6"],["https://site.io/p7"],["https://site.io/p8"],["https://site.io/p9"],["https://site.io/p10"],["https://site.io/p11"],["https://site.io/p12"],["http://tinyurl.com/c"]] Output: [None, 'http://tinyurl.com/1', 'http://tinyurl.com/2', 'http://tinyurl.com/3', 'http://tinyurl.com/4', 'http://tinyurl.com/5', 'http://tinyurl.com/6', 'http://tinyurl.com/7', 'http://tinyurl.com/8', 'http://tinyurl.com/9', 'http://tinyurl.com/a', 'http://tinyurl.com/b', 'http://tinyurl.com/c', 'https://site.io/p12']
The tenth URL gets code "a", the eleventh "b" and the twelfth "c".
Constraints
- 1 <= len(longUrl) <= 10^4
- longUrl is a valid URL
- decode is only called with links returned by encode on the same object
- At most 10^4 calls are made in total
Approaches
- List of URLs, search for repeats — time O(N · L) per encode, O(L) per decode, space O(N · L)
Follow-up
A counter gives short, collision-free codes but makes them guessable, and on many servers the counter itself must be shared. Real shorteners often hand each server a block of numbers, or hash the URL (taking the first characters of a hash and probing on a collision), and keep the table in a database with a cache in front, since links are read far more often than created.
Related problems
Start free on Cariara · Coding problems · System design studio
