Note: This is a companion problem to the System Design problem: Design TinyURL.
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.
There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
Implement the Solution class:
Solution() Initializes the object of the system.
String encode(String longUrl) Returns a tiny URL for the given longUrl.
String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.
Input: url = "https://leetcode.com/problems/design-tinyurl"
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after deconding it.
Step 1: Understand the problem and establish design scope
Can you give me an example?
Suppose the original URL is https://www.youtube.com/id=123456&channel=jiakaobo&loggedin=jiakaobo. Your service should create an alias with shorter length: https://www.youtube.com/123adrqev. If you visit it, it should redirect you to the original URL
What is the traffic volume?
100 million URLs are generated pre day.
How long is the shortened URL?
As short as possible
What characters are allowed in the shortened URL?
Shortened URL can be 0-9, a-z, A-Z
Can shortened URLs be deleted or updated?
For simplicity, let’s assume shortened URLs cannot be deleted or updated
What are the basic use cases?
1) URL shortening: given a long URL, return a shorter URL
2) URL redirecting: given a shorter URL, redirect to the original URL
3) High availability, scalability, and fault tolerance considerations
1) Write operation: 100 million URLs are generated per day
2) Write operation per second: 100 million / 24 / 3600 = 1160
3) Read operation: assuming ratio of read operation to write operation is 10:1, so read operation per second: 1160 * 10 = 11600
4) Assuming the URL shortener service will run for 10 years, this means we must support 100 million * 365 = 36.5 billion records.
5) Assume average URL length is 100.
6) Storage requirement over 10 years: 365 billion * 100 bytes * 10 years = 365 TB
Step 2: Propose high-level design and get buy-in
1. URL shortening - create new short URL
2. URL redirecting - redirect short URL to long URL
return longURL for HTTP redirection