So I had an interview for an job yesterday. In fact, it was my first job interview. It went okay.

One of the technical questions the interviewer asked was to create a data structure that would insert in O(log n) and return an iterator that would iterate the data back in sorted order in O(n) time. I knew it was a binary tree and the iterator would use an inorder traversal of the tree so I started typing it out.

But when I got to the iterator part, I just couldn’t figure it out.  I knew for sure it was an inorder traversal but I couldn’t figure out how to turn the recursive algorithm that I knew into an iterative one. So I sat there and drew some trees to try and visualize the algorithm for it. I thought using a stack for the traversal would also probably work but I couldn’t figure that out either. And then time was up.

So we continued the interview. I asked some questions about the position. Then the interview ended.

I hung around for a little bit with a friend that worked there and referred me for the job then we biked back to our dorms. As soon as I got back I opened up Visual Studio and worked on the problem again because I knew that if I didn’t I’d probably end up staying up all night thinking about it.

It figured it out in ten minutes.

Coding under pressure, man. Can’t do it.