I am a mechanical engineer by training with past programming experience primarily for personal projects (video games and such) in multiple languages. I'm currently in a PhD program, finishing up the master's portion.

I casually chatted with a recruiter at a university career fair who told me he would pass on my resume. He mentioned there "may" be something for me at Microsoft, but he didn't know what. He advised me to contact the university recruiter in a few days, as she might be able to help me better. They called me for a screening interview for an internship the very next day.

I'm not, what I like to call, "classically trained" when it comes to computer science. I prepared for the screening interview by going through the MIT OCW Algorithms and Data Structures course and also reading Miller and Ranum's "Problem Solving with Algorithms and Data Structures." The screening interview went better than expected. Among other things, I was asked to design a parking lot and write code for detecting palindromes.

A few weeks later, I got a call for a final round interview. It took a while for them to schedule an interview, and they initially gave me a date that was only three days after a major deadline with my sponsor. I requested a later date, and the scheduler worked with my availability to get me a date that worked.

They flew me to Redmond for an interview with the Bing team (I wasn't given that information until the morning of the interview). I was supposed to have three to five interviews. My first interviewer was late because he missed an email sent by the receptionist. Everything after that went smoothly, and I got through all five interviews.

The third interview was over lunch (we wrote code after, not during). The fifth interview was with a program manager. The questions seemed relatively easy. The topics covered were:

• Queue design
• Common ancestor search in a tree with no underlying structure
• Mixed uni- and multi-byte character strings
• Detection of unique addresses
• Linked list scanning and element removal

Some interviewers wanted me to just solve a problem as well as I could. Others were looking for a discussion of the problem, one of which was actually very interesting and gave the interviewer some new ideas.

At the very end, I asked the hiring manager some subtle questions about my performance and what kind of competition I was facing. It's nice to be told that there is a "high probability" of them making an offer :)

Suppose you have a string with characters that are either one or two bytes long. A one-byte character has 0 as its leftmost bit. The first byte of a two-byte character has 1 as its leftmost bit, but the second byte's leftmost bit (LMB) could be either 1 or 0.

Implement an algorithm for removing one character from the end of the string. How would you do it while scanning backward from the end of the string?

Follow-up: What if you needed to do this repeatedly? Is there some way you could reduce the time complexity to constant?