I secured my first interview by persistently approaching Microsoft at my university's career fairs. My initial interview was a typical screening, conducted face-to-face on campus rather than the usual phone call. I was asked open-ended questions, such as how I would design an alarm clock for a blind person and what my favorite computer application was and why.

The next stage of the interview process was a "fly-out" to Microsoft's headquarters for a full day of interviews. Microsoft covered all travel and lodging expenses, and the arrangements were organized very well. I had a dedicated recruiter at Microsoft who was responsible for planning my interviews, liaising with the interviewers, and making the final hiring decision. He was a bit pushy, but I can't claim that's representative of all Microsoft recruiters.

I arrived at the recruiting building in the morning and met my recruiter in person, along with a few other students interviewing for internships. We were provided with the name and group description of our first interviewer, and then shuttled to different buildings to meet them.

All the interviews took place in the interviewer's day-to-day office, which was beneficial as I gained insight into their normal work environment and a feel for the company culture. Microsoft's atmosphere is surprisingly laid-back compared to my expectations. There are no cubicles; all full-time employees have their own offices. The dress code is very casual, with polo shirts or t-shirts and jeans being the common attire. I opted for business casual (a collared shirt tucked into khakis), despite everyone advising against suits. Interestingly, two of my interviewers commented on how formally dressed I was!

The building where I interviewed featured an Xbox lounge (and later, a Wii was added that summer) and a kitchen on each floor stocked with complimentary coffee and soda.

My first two interviews lasted about an hour each and were fairly standard technical assessments. My third interview extended slightly longer as we went out for lunch and conversed casually (though this was still considered part of the interview). Upon returning from lunch, I still had to answer a technical question before heading to my fourth interview. My first three interviews were with the same team and held in the same building, but my fourth interview was with a different team.

At the end of the day, I returned to the recruiting building to await the outcome of my last interview, which would be communicated to my recruiter. I performed well enough to receive offers from both teams I interviewed with. It's worth noting that my recruiter mentioned the decision process typically takes about a week for interns, making my situation an exception. However, this expedited outcome wasn't entirely helpful, as I was still only given one week to decide. My recruiter strongly encouraged an immediate decision but was unresponsive to my emails for the first half of the week (he was sick, to his credit). Consequently, I extended my decision-making period slightly beyond a week. I wished for more time to interview with other companies, but I ultimately decided to accept the offer, as it was a very good one.

Connect Four is a game where two players take turns dropping their colored discs into a vertically suspended grid. The game ends when a player adds a disc to the playing grid that connects four discs of their color. The connected discs can be in a horizontal, vertical, or diagonal line.

Write a function, to be called after every turn, that returns true if the game is over (and false otherwise).

Write an algorithm that does an in-order traversal of a tree recursively. Now, write the same algorithm iteratively.