Encode And Decode Tinyurl - Leetcode Solution

Problem Statement:

Design a system to encode a URL to a shortened URL and decode a shortened URL to the original URL. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Solution:

The problem is asking to design a system to encode URL to a shortened URL and decode a shortened URL to the original URL. This is a very classic problem of system design. The solution to this problem can be achieved using two different approaches:

1. Encoding Hash Map: In this approach, we will create a hash map to store the URLs and generate a unique key for each URL. The key will be used to generate a shortened URL that will be sent to the client. When the user clicks on the shortened URL, the server will find its corresponding key from the hash map and redirect him to the original URL.

2. Encoding Base62: In this approach, we will use the Base62 encoding algorithm to generate a shortened URL. Base62 is a character set of 62 characters (a-z, A-Z, 0-9) that can be used to encode any integer. We will use this algorithm to generate a unique ID for each URL and convert it into a short URL using Base62 encoding. When a user clicks on the shortened URL, the server will decode it into the ID and find the URL from the database.

Algorithm 1: Encoding using Hash Map

1. We will use a Map<String, String> to store the original URL as the key and the shortened URL as the value.
2. For each new URL, we will generate a unique key using UUID.randomUUID() and add it into the hash map with the original URL.
3. Return the shortened URL by appending the key with the base URL.
4. When a user clicks on the shortened URL, the server will get the key from the URL and get the original URL from the hash map.

Algorithm 2: Encoding using Base62

1. We will use an integer ID to represent each URL. The ID will be incrementally generated for each new URL.
2. We will convert the ID into Base62 encoding to generate a shortened URL.
3. We will store the URL and its ID in the database.
4. When a user clicks on the shortened URL, we will decode it into the ID and retrieve the original URL from the database.

Time and Space Complexity:

Algorithm 1: Encoding using Hash Map

• Time Complexity for encoding: O(1)
• Time Complexity for decoding: O(1)
• Space Complexity: O(N)

Algorithm 2: Encoding using Base62

• Time Complexity for encoding: O(logN)
• Time Complexity for decoding: O(logN)
• Space Complexity: O(N)

Overall, the first algorithm is faster in terms of encoding and decoding, but the second algorithm is more space-efficient. Both approaches are valid and have their own advantages.

1