Last Updated: 19 Apr, 2021

Encode and Decode

Easy

Asked in companies

Solve now

Problem statement

Tiny URL is an online URL shortening service, where you get a short version of a given URL as a substitute.

Your task is to design encode the original URL “S”, into a tiny URL and decode the previously encoded tiny URL into the original URL.

Example:

S= “https://youtu.be/dQw4w9WgXcQ”, can be encoded to TinyUrl “http://tinyurl.com/abcdef”, then in future queries “http://tinyurl.com/abcdef”  can be decoded into “https://youtu.be/dQw4w9WgXcQ”

Note:

The URL given to you for decoding will always be one of the URLs you have already returned after encoding in the past.

The encoded URL should strictly be of the format “http://tinyurl.com/abcdef”, where instead of “abcdef” you can have any alphanumeric code of length 6.

Input Format:

The first line contains an integer, 'K’ denoting the number of queries.

The second line contains a string ‘S’, denoting the URL.

Output Format:

For each test case, return the decoded URL.

Output for each test case should be in a new line.

Note:

You don't print anything, it has already been taken care of. Just implement the given functions.

Constraints:

1 <= K <= 1000
1 <= |S| <= 50

Where |S| is the length of string S.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Encoding :

Encoding a URL into TinyURL “http://tinyurl.com/abcdef”, where “abcdef” is an alphanumeric string of length 6, can be done using a simple hashing algorithm, and an alphanumeric string generator.

For an alphanumeric string generator, you can just generate a random alphanumeric string of length 6 and check whether this code is previously used or not. If it isn’t then use it to encode the current URL.

Decoding:

After encoding the URL in the encoding function, you are to hash the original string to TinyURL. Which you can use in the decoding function.

Below is the detailed algorithm:

Create two global hashmaps/maps, 'URL_TO_TINY' and 'TINY_TO_URL', which hash a string to a string.
Create a function “randomAlpha”, which returns a random alphanumeric string of length 6.

Encode function:

Check if this URL “S”, has already been encoded in previous queries. If it has, then return the previously encoded TinyURL from hashmap 'URL_TO_TINY'.
If not then generate a random alphanumeric string 'STR' using the function “randomAlpha” and check if 'STR' has already been used previously, if it is used in hashing some other string then generate another random string, do this repeatedly.
Create a new string “tiny”= “http://tinyurl.com/” + str.
Hash the given URL “S” to the URL “tiny”, in the hashmap 'URL_TO_TINY'. And hash the URL “tiny” to the given URL “S” in hashmap 'TINY_TO_URL'.

Decode function:

We only get the URL in the decode function which we have already encoded first. Therefore we can just return the value stored in the hashmap 'TINY_TO_URL'.

Solve now