Following a phone interview, I was invited to the Redmond campus for a long day of one-on-one interviews. Microsoft was gracious enough to pay all of my expenses for flying out to WA and for meals and travel.

The 1:1 interviews themselves were interesting and difficult, but often oddly focused. I felt as if the engineers who asked me questions were usually only interested in their own areas of study. My knowledge, or lack thereof, in their (sometimes very different) fields didn't matter as much.

For example, one interviewer asked me at the beginning if I had studied design patterns. I answered that while I had used some simple ones in the past, I had never formally studied them and thus didn't know many, nor the names of the ones I did know. Despite this, he continued to ask me questions for an hour about design patterns and became visibly angry when I couldn't put names to the patterns he described. This probably boils down to typical engineer unsocial tendencies.

The strangest part of the process is that you interview for a group within Microsoft that is chosen for you ahead of time, without any of your own input. I ended up interviewing for a group doing work that did not interest me whatsoever, which made the process that much harder.

Given a 2D matrix of numbers where each row and column is sorted in increasing order, describe an efficient algorithm to test whether a given number is in the matrix.