Coding Interviews Exposed covers most questions you'll be answered.
It all depends on the team though, the interviewing process is completely non-regulated here. We get training telling us what to legally not say, but other than that is a free for all.
Teams ask white boarding questions because they heard other teams ask white boarding questions.
I recently went through an MS phone interview and didn't do as well as I would have hoped. I did learn quite a bit though. Here's my advice:
1) Actual programming and a technical interview are not and never will be the same thing. Assume you know nothing. And I do literally mean nothing.
2) Start with a basic intro to programming book in a language you aren't familiar with and try to do simple tasks in a language you already know. This simulates a bit how it feels to program under pressure. Things you know you know seem not to come out quite as quickly. This helps to emphasize point #3.
3) Practice. Practice. Practice. Practice. Practice. A decent chunk of your typical interview questions exist out there. I'm not saying to memorize them, but be familiar with their solutions. Eventually you'll get to the point that an approach for solving a new problem will come from pieces of old ones.
4) Since coding is done on whiteboards, do not use a compiler. Pencil and paper.
5) Find someone to give you an honest-to-goodness mock interview.
I'm currently interning at MS (India). I am a physics student with programming as a side hobby. (Not yet sure what to do as a career)
While this may be quite different from interviews for MS Redmond/etc full time jobs, this was my experience:
In my interviews, I mentioned off the bat that I wasn't great at algorithmic stuff. Now, don't get me wrong, I can do them, I'm just far, far behind the curve. (Students, esp. CS students, in India spend lots of time on sites like SPOJ and CodeChef solving algorithmic questions; I prefer to do stuff in open source). The interviewers were understanding. I got asked fun stuff like "what do you enjoy about [project I work on]". "Walk me through some large problems you grappled with on [project] and how you solved them". I got to have great back-and-forths on these things. It wasn't easy explaining nuanced and intricate problems, but I was able to give them a rough picture which I think is what they wanted. Shifting the focus from "can he solve this puzzle" to "what work has he done in the past" was great.
There were also algorithmic-y things, but not the usual kind. For example, one interview focused on designing and optimizing a build tool. The idea was that we had a bunch of components, with dependencies on other components, and I had to efficiently generate a viable order of building. There were some other constraints which I forgot. I realized that the problem was similar to a garbage collector (not that I knew how to model that either :P), and did some sort of mark-and-sweep thing. Then, after being asked by the interviewer, I optimized out some for loops and stuff.
I didn't need to know any algorithms beforehand. Sure, if I had known how `make` does dependency management, or had read up on garbage collectors, I would have done it faster. But I didn't need to know anything, and it worked out.
My fellow interns had really rigorous algorithmic interviews. They were okay with that because they were good at them. It's understandable that "solve this puzzle" is the default since not everyone has real world projects they've worked on (students). I don't like the status quo, but I don't think the interviewers will be intent on maintaining it either. If you have stuff you've worked on that you'd prefer to talk about, I think they'd like that.
If you think the interviewer will be open to it, I suggest mentioning it. They will know you're not from CS; you can mention that you don't have much practice with algorithmic stuff.
Major YMMV though. Also I've done very few programming interviews so the advice here could be totally misguided. :)
