I got an email from the recruiter at Google today. My phone interview is set for February 9th, so I have 4 good days to get ready for it. I’ve been looking at the giant algorithms book, just refreshing myself on stuff like O notation, common sorting algorithms like mergesort, and stuff like that.

I should probably move on to more complicated algorthms next like Dijkstra’s Algorithm and dynamic programming algorithms like the all pairs shortest path algorithm. I don’t think Google would ask me about specific implmentations of these, but it would be good practice to get back into the mindset of designing algorithms this complex, since I haven’t had to do so in a while.

I saw a sample interview question from some blog asking about defining a function f(a,b) to return a string that is all of the characters in a (in order) that are also in b. They ask for an order n2 as well as an order n algorithm. The n2 one seems trivial, but I can’t think of how to calculate a set intersection (which is what I think the problem boils down to) in order n time… I could try and prove that it would be impossible to do it in n time, but I don’t really want to do that either. Plus I’m not sure if it is impossible…

Edit: Okay, so apparently they’re “strings” for a reason. The N solution is pretty easy. I was trying to solve a more complex problem in N, when I just needed to take a look at the actual question being asked. I guess I should do regular sanity checks during the interview and not try to accomplish more than they ask.

Well, back to the book for me.