Encode and Decode

Easy
0/40
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in companies
AmazonMicrosoftExpedia Group

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
https://youtu.be/dQw4w9WgXcQ
Sample Output 1:
http://tinyurl.com/abcdef
Explanation for Sample Input 1:
The decoded URL is of the form as described in the problem i.e. “http://tinyurl.com/” followed by an alphanumeric string of length 6.

Multiple answers are possible for encoding, eg: “http://tinyurl.com/sds5xw”, “http://tinyurl.com/8x9qxt”, “http://tinyurl.com/g4e6cd”, etc.

The only constraint is that once you have encoded a URL ‘S’ into some TinyURL, then you should be able to decode that TinyURL in the future.
Sample Input 2:
2
http://codingninjas.com/code/y8fMRhONFF
http://abc.com/code/DNC3bYvUx
Sample Output 2:
http://tinyurl.com/sds5xw
http://tinyurl.com/8x9qxt
Hint

Hash the given URL.

Approaches (1)
Hashing

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'.
Time Complexity

O( K*log( |S| ) ), where K is the number of queries and |S| is the length of the URL.

 

There are K queries and in each query, and on each query we are doing O( log(|S|) ) work because of hashing.

Space Complexity

O( K*|S| ), where K is the number of queries and |S| is the length of the URL.

 

For each query, we are storing the string in the hash function, thus the space complexity is O( K*|S| ).

Code Solution
(100% EXP penalty)
Encode and Decode
Full screen
Console