Many candidates wrongly assume they failed to get a position because they got a question wrong. Unless the question was trivial (i.e. what is the height of a tree?), most of the time these questions are intended to see how well you can carefully think through, create, clarify, and debug your code.
For example, when I was reading your writeup as a former interviewer (lots and lots of college candidates for MSFT -- I was a dev manager and did both my own hiring and was flown to colleges for those "interview days" for several years), I was far more worried that you had trouble finding the bug in binary search than that you got it wrong. Everyone gets problems wrong the first time unless they have just implemented them recently. Superior candidates are good at rapidly trying good normal and edge cases, hammering out a good solution, and writing inspired code when given hints at how to improve their solutions.
I'm almost certain this is why I failed my phone interview. It wasn't that I implemented an inefficient sort right away, its that I didn't talk about how/why it was and what I could do about it with more time.
I really don't like the idea of solving contrived puzzles, but I'll never make the mistake of keeping my thought process hidden again.
If you can, track down somebody who has done a lot of these interviews before to give you a test one and some feedback. I do that for the undergraduates at our school (I went back for my Ph.D. after retiring from MSFT), and they claim it has helped them prepare.
I don't claim any responsibility for their success, though! The University of Chicago undergrads are a hard-working bunch. Much more so than when I was an undergrad :-)
For example, when I was reading your writeup as a former interviewer (lots and lots of college candidates for MSFT -- I was a dev manager and did both my own hiring and was flown to colleges for those "interview days" for several years), I was far more worried that you had trouble finding the bug in binary search than that you got it wrong. Everyone gets problems wrong the first time unless they have just implemented them recently. Superior candidates are good at rapidly trying good normal and edge cases, hammering out a good solution, and writing inspired code when given hints at how to improve their solutions.