Had my phone interview few weeks ago and was asked a variation of this https://leetcode.com/problems/race-car/ The question was a longer version of this. I came up with a suboptimal BFS solution (without caching) and the interviewer said he liked it. I completed the code with no bugs. We discussed another solution and DP. But got rejected. The interviewer was just not friendlt and the whole thing left a very bad taste in my mouth with Google. I have interviewed and passed phone screens for all others recently so I am experienced enough to know when an interviewer is determined to show what a god he is compared to the interviewee.