Microsoft Senior Engineer - Software Development interview questions

I had a one-on-one interview last week. The interview started on time and a very senior engineer spoke with me. We started with my experience and then he asked me to code this problem: Find the probability of legal moves made by a knight in a NxN matrix in m steps. I had heard this problem for the first time and I decided to give my best shot at it. I started thinking aloud and was exploring if I can use combinatorial maths to solve the problem. Later on I tried to find a pattern but that didnt succeed either. Then I moved on to applying dynamic programming technique by which time interviewer interrupted and told me to use something simpler and start from a specific point in matrix (btw, I have figured out a generic algo using dynamic programming now). Then I took a step back and modeled the problem using a tree (and coordinate geometry) where each node specifies a position in matrix . Also, each node would know if its a "legal" node or not based on its coordinates. Using DFS, we can calculate the number of legal moves and divide by the total number of legal moves. The complexity of this algo was exponential but it worked :-) After figuring out the algo, I was asked to write a working code and I was already running out of time. I quickly wrote the classes and the main method. For brevity of time, I cut out the input validations and just wrote the meat of the logic. Interviewer asked me if I can think of any optimizations. I had many ideas floating in my head but they were very fluid. After all, it wasn't an easy problem and as far as I am concerned, it could be a Master's thesis problem as I was hearing this problem for the first time :-) Interviewer was very polite and I enjoyed speaking with him. But I got a decline from Microsoft :-( I am not sure what the reason could be but I am just wondering that are there no marks for original thinking on the feet, even if the solution wasn't the most optimal? I can bet that if someone even in microsoft is asked to work on complex problems, it might take a few hours, if not days. And even if he is given the most optimal solution on a paper, implementing that in code within an hour would be a challenge. Maybe its sour grapes, but I think there is something lacking in interview process -shouldn't original thinking be given more weightage than getting the right solution? And how can one guage in interview that a person has R&D mindset or not? For the last 2 days I have been thinking about the problem and yesterday I discovered a technique using dynamic programming which is more generic and very optimal. Can the interview process which runs for a few hours capture this? If Microsoft expects people (who are hearing about a problem the first time) to do R&D, design and code in one hour, without any bugs, then all the professors in MIT should be churning out research papers at the rate of one paper per hour :-) Thanks for going through my rant....

It was informational technical interview with my hiring manager