URL Shortener

Posted: 8 Jan, 2021
Difficulty: Easy


Try Problem

You have given a URL id – 'N' consisting of only digits. Your task is to generate a short URL for the given URL id.

To generate a short URL, you need to convert the given URL id to 62 base number where digits of the number are:[“0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”] i.e “0” corresponds to 0, “a” corresponds to 10, “Z” corresponds to 61, and “10” corresponds to 62, “11” corresponds to 63, and so on….

Follow Up:
Can you solve this in logarithmic time and space complexity?
Input format :
The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test contains a single integer 'N', denoting the URL id. 
Output format :
For each test case, return a short URL for the URL id.
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 1000  
0 <= N <= 10^18 

Time limit: 1sec
Approach 1

The idea here is to use recursion and generate a short URL. We will start from the last digit of ‘N’ and add its corresponding modulo 62 code to answer the string and then divide ‘N’ by 62. Finally, we reverse the answer string to get a short URL.


The Steps are as follows: 


  1. Declare a string of 62 characters where each index corresponds to a particular code of shortened URL, say ‘CODE’.
  2. Then, declare an empty string to store our shortened URL, say ‘ANSWER’.
  3. Call the shortUrlRecursion function.
  4. Reverse the ‘ANSWER’.
  5. Finally, return the ‘ANSWER’.

void  shortUrlRecursion(‘ANSWER’, ‘N’):

  1. Define base case if ‘N’ < 62 then add ‘CODE[N]' to ‘ANSWER’ and return.
  2. Add ‘CODE[N%62]' to ‘ANSWER’
  3. Recur for shortUrlRecursion(‘ANSWER’, ‘N’ / 62).
Try Problem