I wouldn't recommend going back to school. You already have a Master's in Physics, which should give you all the math background you need to understand CS algos. I'd even encourage you to start to "translate" your Physics knowledge into code.
Google, FB, Microsoft, et. al. are more concerned with your ability to explain CS concepts at a whiteboard than your degrees.
Have you considered SpaceX? http://www.spacex.com/careers/list
They are usually very interested in cross discipline candidates.
Once you are there, I'd say the best way would be to find someone in your network who works at google, and get referred. If you don't know anyone, make contacts through various channels.
Is this you personal experience?
I know for a fact that almost no one I interviewed with bothered to look at github. Some even admitted that asking for github is just a formality and that they don't have time or resources to evaluate it objectively.
I also concur that getting a referral from an any employee that you might meet is the better than just blindly sending in your resume, though not as good as a strong referral (i.e. someone you've had direct experience working with before). You will get more attention from the HR side and the employee referring you will have a better idea of what teams will be relevant than the HR people will.
If you think you have talent in that area you could spend the next two years working in that area, then apply
> I want to work at google because I want to work with the people there who are just the smartest people around
Be careful with that kool-aid, it's toxic in high doses.
Considering how many times we've warned you before about posting comments that break the HN guidelines, I should probably ban your account for this. But we'll give you another chance. Please don't break the guidelines again, if you want to keep commenting here.
* How can I get an interview? It seems simply sending my resume through the online portal will not work because I don't have a stellar academic record or much experience.
* How can I figure out what to apply for? I have experience in UI but does google even do that? I want to work at google because I want to work with the people there who are just the smartest people around. But I don't really care what I work on.
* How and how long should I prepare for the interview? I am working through the Cormen's algorithms book but I don't really have a solid CS education. And I hear that they just want you to know everything. So should I just go back to school?
* I have heard that one way is to participate and excel in coding competitions. Should I then focus my entire energy on this front? Or will this be misguided?