E: py3compile:243: Requested versions are not installed

Am trying to run the command sudo apt-get install build-essential libssl-dev -y. But for most apt-get update command I end up getting below error. Not sure what is wrong with python package here

E: py3compile:243: Requested versions are not installed
dpkg: error processing package python3-apt (--configure):
 subprocess installed post-installation script returned error exit status 3
Errors were encountered while processing:
 python3-minimal
 python3-apt
E: Sub-process /usr/bin/dpkg returned an error code (1)

System info:

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 16.04.2 LTS
Release:        16.04
Codename:       xenial

Python versions :

$ python --version
Python 2.7.12

$ python3 --version
Python 3.7.4

$ apt-cache policy python3-minimal
python3-minimal:
  Installed: 3.5.1-3
  Candidate: 3.5.1-3
  Version table:
 *** 3.5.1-3 500
        500 http://archive.ubuntu.com/ubuntu xenial/main amd64 Packages
        100 /var/lib/dpkg/status

& type -a python3
python3 is /home/linuxbrew/.linuxbrew/bin/python3
python3 is /home/linuxbrew/.linuxbrew/bin/python3
python3 is /home/linuxbrew/.linuxbrew/bin/python3
python3 is /home/linuxbrew/.linuxbrew/bin/python3
python3 is /usr/bin/python3

$ file /usr/bin/python3
/usr/bin/python3: symbolic link to /usr/bin/python3.7

$ echo $PATH
/bin:/usr/local/go/bin:/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin:/home/rxy/bin:/home/rxy/.local/bin:/bin:/usr/local/go/bin:/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin:/home/rxy/bin:/home/rxy/.local/bin:/bin:/usr/local/go/bin:/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin:/home/rxy/bin:/home/rxy/.local/bin:/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin:/home/rxy/bin:/home/rxy/.local/bin:/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin:/usr/lib/jvm/java-8-oracle/bin:/usr/lib/jvm/java-8-oracle/db/bin:/usr/lib/jvm/java-8-oracle/jre/bin:/usr/local/go/bin:/usr/local/go/bin:/usr/local/go/bin:/usr/local/go/bin

file /usr/bin/python3.5
/usr/bin/python3.5: cannot open `/usr/bin/python3.5' (No such file or directory)

Contents of ~/.profile:

# ~/.profile: executed by the command interpreter for login shells.
# This file is not read by bash(1), if ~/.bash_profile or ~/.bash_login
# exists.
# see /usr/share/doc/bash/examples/startup-files for examples.
# the files are located in the bash-doc package.

# the default umask is set in /etc/profile; for setting the umask
# for ssh logins, install and configure the libpam-umask package.
#umask 022

# if running bash
if [ -n "$BASH_VERSION" ]; then
# include .bashrc if it exists
if [ -f "$HOME/.bashrc" ]; then
. "$HOME/.bashrc"
fi
fi

# set PATH so it includes user's private bin directories
PATH="$HOME/bin:$HOME/.local/bin:$PATH"
export PATH='/home/linuxbrew/.linuxbrew/bin:/home/linuxbrew/.linuxbrew/sbin':"$PATH"
export PATH=$PATH:/usr/local/go/bin

I have been hitting my head for quite some time and have come up with this solution (not nice, but if it works):

Based on the thought that Python is, in essence, an interpreted language, py3compile might be nice but should not be needed, so:

mv /usr/bin/py3compile /usr/bin/py3compile.orig
ln -s $(which true) /usr/bin/py3compile