For non-deep learning, read David Barber's book:

http://web4.cs.ucl.ac.uk/staff/D.Barber/textbook/090310.pdf

Some sections may be less relevant, depending on what you want to do, but Section III is a very good introduction to machine learning methods.

Do the exercises as you're reading. Theory is one thing, but in ML my rule of thumb is that you don't really understand a model until you've coded it up. A collection of written exercises would be a good way to impress an interviewer, too.