Design a URL shortening service
- Store given url in a database assigning a unique interger id to it.
- convert the integer to character string that is at most 6 characters long. This problem can basically seen as a base conversion problem where we have a 10 digit input number and we want to convert it into a 6 character long string.
The long url should also be uniquely identifiable from short url. So we need a Bijective Function. This is necessary so that you can find a inverse function g(‘abc’) = 123 for your f(123) = ‘abc’ function. This means:
- There must be no x1, x2 (with x1 ≠ x2) that will make f(x1) = f(x2),
- and for every y you must be able to find an x so that f(x) = y.
How to convert an integer to a 6 character string
A URL character can be one of the following
- 1) A lower case alphabet [‘a’ to ‘z’], total 26 characters
- 2) An upper case alphabet [‘A’ to ‘Z’], total 26 characters
- 3) A digit [‘0′ to ‘9’], total 10 characters
There are total 26 + 26 + 10 = 62 possible characters.
So the task is to convert a decimal number to base 62 number. Check the base-62 conversion program in Github