Microsoft Software Developer interview questions

Recruited at my school a week before our career fair. I talked to our campus recruiter and she set up the first on-campus interview which took place at my school. The on-campus interview was only 30 minutes long, which was about 10 minutes of behavioral/experience questions and 20 minutes of a short programming question (not too difficult, more of a warm up question). A week or so later I was emailed saying I made it to final-round in Seattle, where I was flown out. Four 45-minute interviews starting at 8 in the morning, but the vibes were overwhelmingly positive making it not too bad. All programming interviews, two of which were easier than the other two but overall not as bad as I was expecting. Microsoft paid for all of our meals and tourist expenses for the day. I interviewed on Monday and got my phone call on Friday, so pretty quick answer.

I was approached by email after attending a few career events and Microsoft competitions. The process before the interview was smooth, but the initial technical interview itself was pretty horrible. My interviewer was running 15 minutes late, which to him meant that my interview would have to be compressed down to 15 minutes. That meant no time for anything other than technical questions, i.e. nothing about my background or similar. I solved the technical question in an okay way quite quickly, even though it wasn't the optimal solution. He then probed for a slightly better solution, and I produced a different solution. This was still not the one he was looking for though, and I needed a hint to be able to figure out what that was. Note that all three of these solutions were linear, so it was the space complexity he was after.