I have a PhD in CS from UC Santa Cruz, and I was hired by Google out of school. The key is to do internships: just like undergrads, you have to prove to companies that you can do the work, and internships are the best way of doing that. I did two internships at Google, and did the conversion interviews.
What I don't understand is why you are applying to Google if you're doing a Physics PhD. Why become a doctor of Physics and then throw it away trying to apply for jobs that have zero overlap? You're not trained for the job, and I strongly suspect this is the problem the OP was having. Why aren't you applying to NASA or SpaceX or something?
I hear it's actually not that uncommon for physicists to become data scientists. More importantly though, I was successful in physics as an undergraduate, and it's sort of the academic culture to continue onto to grad school (as well as the culture in my family). In any case, I could always leave grad school if I want to, but I think it's also helping me gain a better computer science background (I've only taken 3-4 computer science classes so far...)
I'm not applying to NASA or SpaceX because I'm really interested in consumer tech, and always have been. Honestly, maybe I have the total wrong idea for what I want to do, and I understand that. That's again why I want to do an internship.
I actually have a Google interview in a couple of weeks. If you don't mind me asking, did you work at Google as a researcher or software engineer?
There are very few people who actually work under Google Research, everyone else is a software engineer (including everyone who worked on my research paper with me [1]). The trick is to realize that there are many product teams for which what you'll be doing are researchy style jobs. These are usually things where you're working on the backend (Compute Platform, Search, Google X) rather than the frontend (Javascript UI stuff). While the job description is software engineer, for those reasearchy jobs, you're doing work that's very similar to what you might be trying at the university lab. Except with a lot more data, and a lot more computing power behind you.
Matt Welsh has written a number of times about his job change from Harvard Prof to Google, and he's a software engineer by title AFAIK, but he's clearly doing research work.
I like the internship idea. However, I should add that these should be non-research. I did internships at industry labs - this seemed like a good idea at the time since I was prepping for a career in research. Now that I want to get out of it, those research internships aren't worth as much as the Google internships.
As a someone who is 5 years out of his PhD (working at a research lab), I'm a bit perplexed at how I can make up for the lost years of industry experience. The best idea I have now is to start my own company.
What I don't understand is why you are applying to Google if you're doing a Physics PhD. Why become a doctor of Physics and then throw it away trying to apply for jobs that have zero overlap? You're not trained for the job, and I strongly suspect this is the problem the OP was having. Why aren't you applying to NASA or SpaceX or something?