Microsoft Software Engineer interview questions

Met the MS guys on school's career, and got the on-campus interview a month later. It was quite simple. The question is to remove duplicates in a sorted linked list, and some behavioral questions. And about a week later got the on-site interview. There are four rounds. Questions I remember are: (1) turn a string "sdasd..." into all possible strings where each char can be replaced by its corresponding upper letter; (2) write a singleton class which should be fine to used in a multi-thread environment, and also asked some brain teaser problems; (3) a sorted array with all elements appear twice except one, find that element (the best solution should be O(logn)); (4) this round the interviewer is terrible, asked some meaningless problem.

There was a career fair at my university ( Indiana University). I just dropped my resume and after a few weeks received an email saying that they would like to interview me. I was asked general questions in the interview like which Microsoft Technology would I like to work on and why ? It was a short 20 minute interview, covering mostly general question and 1 programming question