Originally from here, I cleaned it up a bit as an easy reference for me.
This works on 14 and 16.
sudo service mysql stop #or mysqld
sudo apt-get remove --purge mysql-server mysql-client mysql-common
sudo apt-get autoremove
sudo apt-get autoclean
sudo deluser mysql
sudo rm -rf /var/lib/mysql
sudo apt-get purge mysql-server-core-5.5 (replace with your version - it might say it is already removed)
sudo apt-get purge mysql-client-core-5.5 (replace with your version - it might say it is already removed)
sudo rm -rf /var/log/mysql
sudo rm -rf /etc/mysql
Don’t forget to Reboot!