First phone interview asked general info (confirming information on resume) and a simple coding question, where you'd code fib() in both iterative and recursive, and talk about the cons/pros between both, run time, possible error checking (what happens when the answer overflows? how would you handle that?), etc. Afterwards, he answered some questions (what kind of programming languages do you use?), which surprised me because the phone interview was meant to be 45min, but he was willing to go over that time limit to answer my questions in detail, with his personal experience in the company.
Second phone interview was entirely made out of coding questions; this about tree traversal and finding a fast way to pick out the nth largest integer from a large integer array (so it'd have to be in linear time, unlike normal sorting using value comparison, which would be at least O(n log n) or worse). I was able to answer both questions (that is, I produced a viable way to do both within given restrictions that he mentioned). One difference between this and the previous interview was that the person was rushing very quickly, and literally tried hanged up when the 45 min mark was up (not even asking questions, just saying "if you have any questions, simply contact the recruiter"). Apparently I wasn't able to give a good impression and they decided to pursue some other candidate for the job.
