The Phone Interview

Start here. More good stuff from Steve Yegge:
Five Essential Phone Screen Questions

This is written more with interviewers in mind, but it has some great information anyway. Although... some of his code samples could be better. He fell victim to one of the classic blunders, the most famous of which is "never get involved in a land war in Asia" - but only slightly less well-known is this: "Never compute the Fibonacci sequence recursively!" (Well, unless you use memoization... don't know what that means? Look it up, who knows, it may come up :-) ). Regarding code samples, I'm planning to dissect one or more of the glassdoor problems to give you an idea of how I thought about solving them (though there may be better ways, of course) in a future post.

Anyway, Stevey's post lays out 5 topics that he thinks every candidate should know. I agree, but I think you can definitely focus on the big 3:

1. Coding
2. OO
3. Data Structures (& Algorithms)

I don't think the regexes and bits & bytes are nearly as likely to come up in the phone interview. I also think it's a good idea to think about Algorithms, not just Data Structures. Especially, know your sorts. QuickSort is not the answer to every sort question. Heck, thanks to IntroSort, I don't think QuickSort is the right sort for any problem. What if you want to sort a huge amount of data? You need to be able to parallelize, and you need to be able to sort without holding everything in memory. QuickSort (and IntroSort) would suck at that. But MergeSort would be great. If you need guaranteed O(n log n) performance without memory overhead, HeapSort is great. Now here's one for you: can you ever sort faster than O(n log n)? I understand it might have been a while since you've seen the relevant theorem, but it only applies to algorithms that use compare and swap. E.g., if you have a limited set of possible values to sort (e.g. [0, 255]), there are better ways! If you don't know what I'm talking about, look in to counting sort and radix sort.

Oh yeah, here's a fun little bit of trivia, that probably isn't relevant: what's the worst case running time for QuickSort? If you want to sound extra smart, the answer's not necessarily O(n^2). If you could only find the median as a pivot. What a shame there's not a way to find the median in linear time. Oh, wait, there is? Sweet. Anyway, that's kind of pointless... just some fun trivia.

Here's something that is relevant, and you should be sure you know: how to search graphs and trees. Know breadth-first-search and depth-first-search, on both trees and graphs. Know what data structures you would use to implement each. Ideally, practice writing each variant before your on-site interviews, at least.

Oh yeah, so we're talking about the phone interview. There will be a coding component to it, but don't worry about having to dictate over the phone. I don't think they do that anymore. You will either have to code in Google Docs (likely while sharing it with someone who can watch you code live), or you will have to e-mail the code to your interviewer, possibly within an hour. In the latter case, I would suggest making sure it compiles, and putting some test cases in there and making sure they run and succeed. It's also a good idea to practice using Google Docs and sharing documents so you don't waste any time figuring that out.

Also, your coding question is likely to involve arrays and/or strings. Make sure you know the appropriate syntax for your language of choice. E.g., I write C++ primarily, and I almost never use arrays (viva vector!), so believe it or not, I had to refresh my memory on the syntax for declaring and initializing arrays.

Okay, so this is a totally rambling post, but I hope you found something useful in it.