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 quite 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.

It was a while ago, so I don't remember completely, but it was something fairly trivial using linked lists.