I first got an interview by handing in my resume at a career fair. I chatted with the recruiter a bit, but he wasn't the chief recruiter, so I didn't expect much. However, two weeks later, I received a notice that I would have an on-campus interview.

The interviewer seemed kind of awkward, and I didn't get the programming question right. To my surprise, I got an email a week later saying I would be flying out to Redmond for an interview.

Although the email said I would have flexibility in scheduling, when I was contacted five days later, it was with a "you're flying out this Thursday" notification (they informed me on Monday). I couldn't get it rescheduled, but hey, it's Microsoft.

I flew out for their two-day interviewing event for the Online Services Division. During this event, they comp plane tickets, hotel for two nights, money for cabs, and stipends for meals.

They took us out in a limo bus on the night before interviews to "meet recruiters," but overall that was pretty useless. You basically just started stressing out with all your fellow interviewees.

The next day, you have three to five 45-minute interviews, each one-on-one. They're pretty difficult, but the nice thing is they give you your results (offer or no offer) right after you finish.

Overall, it's a stressful process, one that is unnecessarily drawn out. But the interviewers on-site were overall pleasant people. The whole process just feels a little bit like an episode of American Idol.

Describe a data structure for which getValue(int index), setValue(int index, int value), and setAllValues(int value) are all O(1).