For anyone encountering this issue on Ubuntu 16.04…
node-gyp can’t use Python 3.5.X which seems to the be the default that ships with 16.04. I read somewhere that 16.04 was supposed to ship with Python2 as well but I can’t find it on my install.
I fixed the above issue by:
apt-get update
apt-get install python2.7
ln -s /usr/bin/python2.7 /usr/bin/python
Now when node-gyp goes looking for python it will hit your Python2.7 install and load correctly.