Not so long ago, I was pretty much in your situation, except that I didn't have a PhD. I was moving into a software engineering role from a DevOps role. I was initially flunking a number of interviews at pretty much the same companies you have mentioned. My advice as most, Practice and Patience while solving problems. Practice talking through a problem in particular. The interviewer is waiting with a hint in hand, which you can always use to get a direction in which to solve the problem. Getting this hint 100% of the time from the interviewer is 100% fine.
As for study, I highly recommend the index page of this book, Elements of Programming Interviews, as a reference. It contains a catalogue of questions, whose complexity exceeds that of CTCI or PIE. Here are the links.
As for study, I highly recommend the index page of this book, Elements of Programming Interviews, as a reference. It contains a catalogue of questions, whose complexity exceeds that of CTCI or PIE. Here are the links.
For the entire book, http://www.amazon.com/Elements-Programming-Interviews-Inside...
For just the index page, http://elementsofprogramminginterviews.com/pdf/epi-toc.pdf.
Good luck!