I too have had interviews at both these companies for software development positions. Totally different experiences.
With Microsoft (for their Vancouver office, 2007) - the interviews were pretty technical, but not severely challenging. I was unhappy with my job at the time, had prepared very well over a period of months for coding-type problems, and was "in shape". The toughest question they asked was, 1) how to serialize a binary tree, 2) how would you compress the representation given that the tree was not full. They were immediately impressed when I asked then whether they intended me to write the deserialization code as well - the thought had apparently never struck the other interviewees. They asked me to code it up, and I did.
With Google (Bangalore, 2011) - I was way out of shape for this, having not programmed in a while. The phone interview required me to write two programs, one of which was to check whether a sudoku puzzle configuration was in the solved state, and the other to generate all subsets of a given set that had a particular cardinality. I managed to code the programs relatively easily. I was selected for the onsite interview, where they asked me mainly questions on dynamic programming. There was also a question on counting frequencies of letters in a massive corpus of text, and on how I'd implement a certain feature displayed in the search results that Google returns. The outcome: they didn't say outright that I failed the interview, but that there has been some change on their side, blah blah and would I be willing to wait for some more time? Obviously I had not done well enough to clear the bar.
Overall I got the impression that Google's version was more centered on competitive programming-type problems than Microsoft's, which was more software engineering-centric. MS definitely much easier than Google.