Penskee material - The Microsoft way...
Friday, January 21, 2005
This entry has a Java applet
embeded somewhere.
If you were a fan of Seinfield (The show about nothing), you probably recall an episode where George goes to work for a company and his first task is to work on the Penskee file. George has no idea what he's doing, but that doesn't stop Penskee, the president of the Penskee company (a competitor), to try and recruit George and in the process, reasuring George that he is indeed "Penskee material."
Why am I bringing this up?Two weeks ago, a recruiter from Microsoft sent me an email asking if I'd be interested in answering a couple of question and solving a programming problem as part of their screening process. The message said that a:
...number of hiring managers in the Office SharePoint Server, Windows Search, Content Management Server and Project Management Server teams [Had seen my resume and that] one, or as many as all, of these teams and their hiring managers have expressed an interest in contacting you [me] regarding positions at Microsoft that might map well to your experience and qualifications.
The first thing that came to my mind was the episode of Seinfield I mentioned above and I thought to myself: "I'm Penskee material" :)
I'm currently engaged on a contractual basis until June 2005, at
Financial Fusion, a subsidiary company of
Sybase. I am part of their Professional Services group, which in turn works with a group in the U.S. creating new functionality for a deployed banking solution for one of their clients (
First Citizens Bank) - So, in truth, I'm not actively looking - I mean, I am a contractor, so I'm always looking, but, not actively looking - I think you know what I mean.
Anyway, since I'm on contract, I thought there is no harm in answering a couple of question and see what Microsoft's (mythical) hiring process is all about. Maybe they fly me to the main campus and I can get some cool Microsoft swag.
The first thing they asked (in the first email), was if I was willing to relocate to Redmond, WA. I'm a Canadian citizen and live near Toronto (I don't know if the recruiter knew), but I said that I would relocate for the right opportunity.
The second email I received, contained the programming problem (see below) together with a few HR type of questions:
Do you know anyone at Microsoft? If yes, who?
I was tempted to say Bill :) But, I answered no, since I don't "personally" know anyone who works at Microsoft - Maybe, it was a trick question.
When was the last time you wrote C/C++ code and what was the project?
I figured that the projects they are working on use C or C++. Unfortunately, I haven't written C/C++ in almost 10 years. Most of the work I've been doing lately is J2EE related and, obviously, Java oriented.
I think the answer to this question, probably disqualifies me right away, but I continued to play and I continued to answer all the HR questions (Man, not the weaknesses question again - I'm obliged to tell them that the laws of physics do not apply to me) and solve the programming problem in Java (You'll see why in a bit).
The programming questionThe programming question was a basic programming task, asking to color sort an array of "Balls" with 2 colors: RED and BLUE. The question said to
"Consider performance, memory utilization and code clarity and elegance of the solution when implementing the function."I'm not the first one to post a Microsoft interview question/problem, so, I don't feel that bad in posting the solution I gave them - It's also quite trivial - Anyone could do it - For more Microsoft interview questions, check
this site.
The full question:
Given an array of balls, which can be one of two colors (RED or BLUE), write a function that partitions the array in-place such that on exit from the function all the balls of the same color are contiguous. It does not matter whether the red or blue balls come first. The return value from the function is the index of the first ball of the second color. If there is only one color of balls in the array then the return value should be 0. It is not legal to change the color of a ball. They must be moved. Consider performance, memory utilization and code clarity and elegance of the solution when implementing the function.
class Ball
{
public:
enum BallColor { RED, BLUE };
BallColor Color() const { return _color; }
private:
BallColor _color;
// Other data in class (unrelated to assignment)
};
unsigned Partition( Ball aBalls[], unsigned cBalls )
{
// Your code goes here?
}
Now...rewrite Partition to handle 3 colors (RED, GREEN, BLUE) again optimizing both space and time.
While the above specification assumes C++, feel free to replace with equivalent code in a language of your choice but always consider performance, memory utilization and code clarity and elegance.
It's a neat problem, since you need to do the sorting in-place. I.e. color sort the array without using anything, but the given array to store all the Ball objects. You probably recall something similar from the first lectures of a typical algorithm CS course. The running time, is typically O(n).
Since they gave me the option of solving the problem in a different language, other than C++, I solved it in Java. I know C++ and could have written C++ and perhaps better my chances, but hey, I'm a rebel.
I've been busy during the week (work and other things), and didn't have time until this past Saturday, January 15, 2005, to look at the question.
I started playing around and scribbling on a piece of paper and came up with the algorithm for the 2 color sort in around 5 to 10 minutes. Once I started coding, I realized that I can solve the problem for N balls with M different colors. "Sweeet," I said.
I completed the coding in about 3 hours, together with testing code. The applet you'll see shortly, was coded tonight, in about 2 hours or so.
I now had the task to prove that my algorithm ran in O(n).
For 2 colors, my algorithm runs in linear time. For N balls, with M different colors, the run time is actually O(N * M). The worst case scenario and a really boring Ball array would have each ball with a different color, or O (N * N).
If you want to see the code in action, you can
play with the applet: it draws a whole bunch of unsorted Balls (600 to be exact) with randomly assigned colors (10 possible colors) for each ball. When you click the "Sort" button, the algorithm runs, and sorts the balls in O(N) time - Well, it's arguably O(N). I.e. If N is sufficiently large, and the number of colors small, you'll get an asymptotic value a bit greater than O(N), so for all intent and purposes O(N) is good enough.
Anyway, I sent the answers to the HR questions, together with a Java source file with my solution to the programming problem and forgot about the whole insident.
Yesterday, I got their "Thank you, but no thank you" email.
I think it's the C++ requirement; I know C/C++, but no where in my resume is stated as one of my strengths, but, then again, software engineering is software engineering, regardless of the programming language used. Or, it could have been something else: maybe they sensed that I can't relocate just yet (6 months at least), or my solution really sucks - Who knows.
So, for two whole weeks, I was "Microsoft material" - Or maybe, I still am, according the "thank you" email:
...After careful review of your answers by our senior technical managers, we will have to pass on your candidacy. However, your record and resume will remain in our Recruiting database and if another Recruiter should require someone with your qualifications, you will be contacted by them directly...
I've done recruiting in the past, and sometimes we didn't keep the resumes of the people I had interviewed. Maybe they do :)
Comments:
Hi.. I recently did exactly the same question... the best solution for just 2 colors, is as you said, a single pass O(n) solution.
For variable number of balls, the best solution is still O(n) in time (2 pass) but O(m*n) in space (m being number of color).... that maybe why...
My first thought for 2 colors is moving two pointer one from beginning, one from the end. Move one color to the front and one color to the end.
My first thought for 3 colors is to have three pointers. One in the beginning, one in the middle, one at the end. Move 1st color to the front, move 2nd color to the end and move the 3rd color to the middle.
Actually to archive the minimum swap, we can traverse the array once to find the number of balls for all 3 colors, then we know the starting index of each color. Then we can set the start, middle, and end pointers at the right position. In the 2nd traversal, start from the beginning and move the balls to the area it should go.
For M balls, I think the complexity is still O(M*N), but the number of swap is optimized.
hmm...I'm going to guess you got rejected because you changed the function prototype that they gave you, so they probably assumed that you cannot follow directions (which I would have assumed as well).
:)
I think there were other reasons, as the solution I sent them had in fact the same method signature they wanted. So your assumption of me not following directions well is not accurate at all.
The solution I published had more stuff in it because I wanted to make sure the n case worked. There was no other way to make sure it worked but to create a visual representation in the form of the Java Applet you saw.
I didn't publish the app until I got the "no thanks" letter. I think it was very creative of me to put the page together, don't you think? If I saw my site, I'd hire me. ;)
I guess you can't judge someone's experience from minor things. I tend to give people the benefit of the doubt and try to get more details as to why anyone would deviate from a certain solution I ask for. I think you learn more from listening rather than making rushed assumptions.
This problem seem a lot like a disk defragmentation problem where array is the disk;
each array element is a disk sector;
ball colors are files.
Any color could be equivalent to unused space.
While a solution is what you gave, the thing is Microsoft is looking for "funcional programming" principals in your code.
That Google has whacked Microsoft's butt in the search space is common knowledge. But behind google's success is the ability to successfully break problems down so that sub problems are processed by different cpus in a cluster or parallel processing system. This kind of problem break down is an important thought process for 'functional programming'.
Check out the essay by Joel
http://www.joelonsoftware.com/items/2006/08/01.html
This should summarize what Microsoft is looking for.
Map/Reduce type solution to the ball partition problem can now be offloaded to separate cores in a motherboard to process sub sections of the array (array in shared mem) so that the problem can be solved faster.
pseudo code:
C => num of colors
a => array
n => num of array elements
// let the colors be numbered 1, 2, 3,...C
func(num_colors, array, start, end)
{
if (num_colors == 2)
{// offload to a core in the multicore processor
//Jose's while loop for 2 balls
}
else
{
for cntr := 1 to C/2
put all balls of colors less
than or equal to C/2 to left-
array and the rest to the
right;
func(num_colors/2, left-array,left-start,left-end);
func(num_colors/2, right-array,right-start,right-end);
}
The emphasis is parallelism. I dont know how OSes use multi-cores.
Going by Google's youtube presentations on functional programming, I am tempted to belive that compilers for multi-cores perhaps attempt cpu-load balancing on the call of a function... again I dont know enough to say that but worth a try in the actual interview.