Encode and Decode Tiny URL
Design a URL shortener. encode(longUrl)decode(shortUrl)
Example 1
Output: "https://cscode.io/algo/strings/EncodeDecodeTinyURL"
Explanation: decode(encode(url)) must return the same URL.
How to Think About It
Step 1: The short URL is a key into a table
The short URL does not need to contain the long one. It only needs to be a unique key; the object keeps a map from key to long URL, and decoding is a lookup.
Step 2: Make keys from a counter
Give each new URL the next number from a counter: 1, 2, 3, ... Numbers never repeat, so keys never collide. Random keys also work, but then you must check for collisions.
Step 3: Keep keys short with base 62
Writing the counter in base 62, using the digits 0-9, a-z and A-Z, keeps keys short: six characters cover 626, about 56 billion URLs.
Step 4: Same long URL, same short URL
A second map from long URL to key means encoding the same URL twice returns the same short URL, instead of using up a new key.
Walkthrough
| Call | Counter | Key | Returns |
|---|---|---|---|
| encode("https://cscode.io/algo/") | 1 | 1 | http://tinyurl.com/1 |
| encode("https://cscode.io/java/") | 2 | 2 | http://tinyurl.com/2 |
| encode("https://cscode.io/algo/") | already known | 1 | http://tinyurl.com/1 |
| decode("http://tinyurl.com/2") | 2 | https://cscode.io/java/ |
The 62nd URL gets the key "Z", and the 63rd gets "10".
Java Solution
The two maps make both directions O(1); toBase62
import java.util.HashMap;
import java.util.Map;
public class EncodeDecodeTinyURL {
private static final String BASE = "http://tinyurl.com/";
private static final String DIGITS =
"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
private final Map<String, String> codeToUrl = new HashMap<>();
private final Map<String, String> urlToCode = new HashMap<>();
private long nextId = 1;
public String encode(String longUrl) {
String code = urlToCode.get(longUrl);
if (code == null) {
code = toBase62(nextId++); // a new, never-used short code
codeToUrl.put(code, longUrl);
urlToCode.put(longUrl, code);
}
return BASE + code;
}
public String decode(String shortUrl) {
return codeToUrl.get(shortUrl.substring(BASE.length()));
}
private static String toBase62(long n) {
StringBuilder sb = new StringBuilder();
while (n > 0) {
sb.append(DIGITS.charAt((int) (n % 62)));
n /= 62;
}
return sb.reverse().toString();
}
public static void main(String[] args) {
EncodeDecodeTinyURL codec = new EncodeDecodeTinyURL();
String url = "https://cscode.io/algo/strings/EncodeDecodeTinyURL";
String tiny = codec.encode(url);
System.out.println(tiny); // http://tinyurl.com/1
System.out.println(codec.decode(tiny).equals(url)); // true
}
}
The original implementation,
Complexity
- Time: O(L) per call, where L is the URL length (for hashing it); the base-62 conversion is O(log of the counter).
- Space: O(total length of the URLs stored).
A real service would store the table in a database and hand out ranges of the counter to each server. For encoding a whole list into one string, see