Last Friday, I interviewed for a software design engineer position with Microsoft.
Their interview process is infamous in the high tech. industry. Open-ended questions, demonstration of your programming capabilities and an expectation of enthusiasm and depth of understanding in your field of choice. Microsoft is still one of the Ivory Towers of computing, so they can afford to be choosy.
My recruiter informed me I would have the opportunity for three to five interviews. When it was all said and done, I interviewed five people between two groups. The first two interviewers were in the first group, and the last three were in the second group. The discussions and results of my interview are semi-public. However, the focus of this post is on the questions I was asked.
Each of these question is multifaceted and I took away a lot from each of them. When I described my answers, I was instructed to use a whiteboard and encouraged to be vocal about my thought process. I heartily encourage finding a friend, a whiteboard, and working through each question with a 30 minute or so time-limit. Exchange roles for each problem: interviewer and interviewee.
- Scheduling Problem: You are given a set of tasks (A, B, C...) and a set of constraints (A depends on B, B depends on C and F, ...). Design a function to return a sequence of tasks meeting the constraints.
- Duplicate Character Collapse: You are given a C string. Design a function to remove duplicate characters. i.e. "aaabbbccc" → "abc", "abc abc abc" → "abc"
- Binary Tree Serialization: You must serialize and deserialize a binary tree. Design two functions such that: char *f(Node *); Node *g(char *); tree = g(f(tree);
- Reverse word order: Design a function to reverse the order of words in a string. i.e. "My name is Scott" → "Scott is name My".
- Space-time tradeoff: You are given a 5x5 grid where each cell has a weight associated to it, and a scale with the ability to give the total weight of any arbitrary selection of cells. In this grid, four of the five rows contain only one pound weights. One of the five rows contains only two pound weights. What is the minimum number of times you must use the scale, and in what configuration, to find the row with the two pound weights.
With the exception of the last item, the solutions should be in C/C++. Have fun! I did.