Lessons learned from an interview with Microsoft

Three steaks in three nights. Medium-well, medium, and medium. I'll name them Hopeful, Rejected, and Consoled. The names describe the gamut of emotions I felt last weekend. I'm normally an emotionally stable individual but job interviews with anyone tend to psyche me out. Such was the case with my interview for an SDE (Software Development Engineer) Internship with Microsoft's Windows team.

Five interviews, actually. The first one was reminiscent of the interview for my entry-level web development job. It was fairly easy, I hardly had to sell myself, and the technical question was almost trivial. That interview took place in my university's career center. It's just a trial run to see if I was at least somewhat competent. The next four, however, took place at Microsoft's campus in the heart of Redmond, Washington. And what a treat the whole thing is! They pay for round-trip flights, two nights at the Westin, a rental car for the duration of the trip, $75 per day for fine dining (which explains the steaks), and a few other treats. If you've got one of these coming up, I would highly suggest working through these problems, finding a good answer, and seeing if you can find a better one. Each interview lasts 45 minutes so you've got to think quick.

First was kind of a tricky math problem. I was given an array of integers of length n. The values stored in the array were restricted to values from 1 to n-1, inclusive. My task was to come up with a way to find the first duplicate value in the array. A brain dead solution is easy, but can you come up with an algorithm that runs in linear time and does not use a secondary array?

The next one dealt with an interesting linked list. You're given a singly-linked list. Each node actually has two links to a 'next' node, link1 and link2. The two links in a node will not necessarily point to the same node. Think of it as a list of people. One set of links could be the list sorted by height. The other set of links could represent the list sorted by age. The task is to reverse the order of one set of links while preserving the order of the other. (I assume there was more to this problem, but I didn't get very far on the first part so I never heard the second part). Here's a visual for clarification:

Link1 path: A--->B--->C--->D
Link2 path: A--->C--->B--->D


The third one was very similar to the second (thankfully). You have an n-ary tree (a tree where each node has 0 or more child nodes). The tree is stored as a type of linked list. Each node has two links: one to the next 'sibling' node and one to the first child node. My task was to reverse the order of sibling nodes while preserving the parent-child relationship. For example, if you have this tree:

A
|
B------------->C
|              |
D--->E--->F    H--->I

After reversing the order of the siblings, you'd have:

A
|
C-------->B
|         |
I--->H    F--->E--->D

Notice that in the first tree, B's first child is D, but in the second tree, its first child is F. Since we had a few minutes left after I gave a working solution, my interviewer then asked me to write another function which prints out the contents of the tree in order.


The fourth and final one was fairly straightforward. I was given a binary search tree that contains ints. Remember that a binary search tree is one where each node has 0, 1, or 2 child nodes and that the left child (and all of its descendants) has a value that is less than the node and the right child (and all of its descendants) has a value that is greater than the node. I was supposed to determine whether a given binary tree was valid.

I wanted to share these questions with you, not so you can have an unfair advantage (which is why I didn't include any hints), but so that you can know what types of questions to prepare for. Be prepared to come up with a quick solution, make sure it works, then to optimize it as best you can. This was actually my second time going through the whole Microsoft interview process and these questions were fairly similar to those in my first round. I can't speak for all interviews since I only ever interviewed with the Windows team, but I would imagine that questions of the same difficulty would be asked in any SDE interview.

To be fair, I should include other questions they asked me that were of a more personal nature (these aren't word-for-word).

• Why do you want to work at Microsoft?
• What are the most important factors for you when considering a job?
• What has been the most challenging problem/bug you've dealt with in any of your projects at school or work? How did you solve that problem? Be specific!
• Have you ever had to convince someone else to use your plan/approach/strategy/solution over theirs? How did you do that?
• Do you enjoy writing code? Why?
• Do you like debugging?
• What are some personal projects outside of school or work that you've been involved in?
• What's been your favorite class in your college career so far? Why?
• Least favorite class? Why?

Motivation for proper ethics

Anger is a great motivator. Look at almost any video on Youtube and you'll see trolling and put-downs sprinkled amidst a few relevant comments. Couple that with the anonymity of the Internet and people who are otherwise quite friendly say some downright offensive things. However, if you give someone a good reason to do something -- a reason that both offers them success and lets them feel like they've helped out the world in some way -- they will generally do good things. All too often ethics and morals are branded as archaic or old-fashioned. No one who needs to stay afloat in a world that is constantly flooded with new technology wants to be considered old-fashioned. But if you convince people that following a code of ethics will actually benefit them more than following a selfish code of conduct, they will do the right things -- the ethical things -- all on their own. It's a matter of motivation.