URL Shortener

Easy
0/40
Average time to solve is 10m
profile
Contributed by
10 upvotes
Asked in companies
AdobeMakeMyTripShareChat

Problem statement

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?
Detailed explanation ( Input/output format, Notes, Images )
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.
Note: 
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
Sample Input 1 :
2 
51
156
Sample Output 1 :
P
2w
Explanation :
In test case 1, the shortened URL will be P since 51 corresponds to P.

In test case 2, the shortened URL will be 2w since 156 corresponds to 2w.
Sample Input 2 :
2
5
422
Sample Output 2 :
5
6O
Explanation :
In test case 1, the shortened URL will be 5 since 5 corresponds to 5.

In test case 2, the shortened URL will be  6O since 422 corresponds to 6O.
Hint

Think of a recursive solution and generate each character of the URL one by one.  

Approaches (2)
Recursive Approach

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

O(log62N), Where ‘N’ is the given number.

 

Since we are dividing N each time by 62 until it becomes <62. 

Let us say it becomes 1 at the kth turn. 

So  N / (62^(k) = 1, and  62^k = N.

Taking the log base 62 both sides

and  k = log62N 

Hence the overall time complexity will be O(log62N). 

Space Complexity

O(log62N), Where N is the given number.

 

Since we need O(log62N) recursion calls. Hence the overall space complexity will be O(log62N).

Code Solution
(100% EXP penalty)
URL Shortener
Full screen
Console