I had a phone interview with amazon today. I messed up on the time complexity after solving the problem, I was able to come up with the runtime only after analyzing it with the interviewer. He gave me the hint and worked through basically. Don't know if I will progress.