Installation

1. Install python 3 and postgresql

    $ sudo apt-get update
    $ sudo apt-get install python3-pip python3-dev libpq-dev postgresql postgresql-contrib
   

2. Create a database ("shortener" is the default name for user, password and database just for testing)

    $ sudo -u postgres psql
    postgresql=# CREATE DATABASE shortener;
    postgresql=# CREATE USER shortener WITH PASSWORD 'shortener';
    postgresql=# GRANT ALL PRIVILEGES ON DATABASE shortener TO shortener;
    postgresql=# \q
   

3. Install virtualenv

    $ sudo -H pip3 install --upgrade pip
    $ sudo -H pip3 install virtualenv
   

4. Clone this project

    $ git clone https://github.com/OmarIbannez/shortener.git
   

5. Enter the project folder and create a virtual environment

    $ cd shortener
    $ virtualenv venv
   

6. Activate virtual environment and install dependencies

    $ source venv/bin/activate
    $ pip install -r requirements/requirements.txt
   

7. Create schema

   $ python manage.py migrate
   

8. Run script to populate data base

   $ python manage.py shell
   Python 3.6.9 (default, Nov  7 2019, 10:44:02)
   Type 'copyright', 'credits' or 'license' for more information
   IPython 7.11.1 -- An enhanced Interactive Python. Type '?' for help.
   
   In [1]: %run populate_db.py
   You have requested a flush of the database.
   This will IRREVERSIBLY DESTROY all data currently in the 'shortener' database,
   and return each table to an empty state.
   Are you sure you want to do this?
   
   Type 'yes' to continue, or 'no' to cancel: yes
   

9. Install background job to fetch urls information

    $ python manage.py installtasks
    Installed 1 task.
   

10. Run server

    $ python manage.py runserver 0.0.0.0:8000
    

Algorithm

To generate the short urls I'm using the following encode function:

def encode(n):
    base = string.digits + string.ascii_lowercase + string.ascii_uppercase
    b = len(base)
    res = ""
    while n:
        r = n % b
        n = n // b
        res = base[r] + res
    return res

1. First I store the url into the database to get a base 10 number (primary key generated by the database).

2. Then I encode this base 10 number into base 62.

3. To explain the algorithm lets say the data base is storing a new url object and is returning the id 74.

4. On this line we set a variable with all the digits [0-9], all the lower case characters [a-z], and all the upper case [A-Z].

   base = string.digits + string.ascii_lowercase + string.ascii_uppercase

5. Then we get the length of the previous variable, which is 62 (all lower case plus all upper case plus all the numbers from 0 to 9).

   b = len(base)

6. We declare the variable where we are gonna store our new encoded string.

   res = ""

7. And now we start to iterate until n is 0 (n is equal to the id the database is giving us for our url).

8. On the first line of the iteration we use the modulo operator to ensure that no matter how big the id is we get a number from 0 to 61, for example in our case if we have 74 as id on the first iteration we are gonna get r = 12.

   r = n % b

9. Then we divide n by 62 using the "floor" division operator // to get the quotient without remainder and on this case we get n = 1

10. At the end of this iteration we use our variable r to get a character from base in our case we are gonna get c because c is the 12th character in base and we prepend this value to res.

    res = base[r] + res

11. On the next iteration we do the same but now n = 1 and r = 1 because 1 % 62 = 1 and then n = 0 because 1 // 62 = 0, finally we get the the r element again which in this case is 1 and we prepend it to res and we get the final encoded result which is 1c