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 :)
To be, or not to be
Thursday, January 20, 2005
Who was Shakespeare?
When Hamlet went on and on, on the question of existence, he started his soliloquy with the famous "To be, or not to be--that is the question" phrase. I can use the same pattern and ask of Shakespeare: "Was he, or wasn't he? That is the question"
The existence of Shakespeare has been debated since the creation of his plays.
The controversy begins with unbelievers claiming that a wheat trader, with average education, could not have been the best English writer in the whole history of humanity (So far).
They claim (whoever "they" are) that the plays and poems have too much detail about noble life, geography, history, etc., etc.
Little is known of the actual life of William Shakespeare--the Shakespeare from Avon of Stratford, they claim, cannot be the same William Shakespeare of our history.
If not William, then who?
Some say it was
Francis Bacon, a scholar and nobleman of the 17th century. He entered Trinity College Cambridge at age 12, and later became a philosopher, a writer, and closeted poet.
A very probable option, if you read some of the crazy stuff on the site--there are also rumors suggesting that Bacon also wrote
Don Quijote de la Mancha (Which is attributed to the Spaniard Miguel De Cervantes).
There are "real" books about the controversy as well, so the matter is of scholarly interest. If it is true that Bacon penned all these books, he probably never slept, and should probably be considered super-human.
Another good candidate to be the real Shakespeare is
Christopher Marlowe. He was a playwright, a writer, and an English spy--a very interesting old chap.
Why would anyone doubt?
It's extremely hard to pint point the real identity of Bill, as there are few records to corroborate anything, and all Shakespeare's writings that have survived are re-writes from the originals (originals long gone) and copies of published books.
I find the whole debate quite interesting, to say the least--it's the biggest case of stolen/lost/mistaken identity.
I couldn't imagine such a thing happening now a days: we keep track of absolutely everything. I have 120 GB of available space to store everything I've done my whole life. I have less than 1 GB of real data, and the rest is just fluf that I haven't created myself: programs, pictures, etc., etc. Of course, I have no plays, nor poems to my name, so I have nothing really important to loose.
Dumb little programs, on the other hand...
Blogs as marketing tools
Tuesday, January 18, 2005
I've always thought of my personal web site as more of an extension to my
resume, rather than a window to my soul, so, indeed my web site (and blog) is a marketing tool.
fortheloveofwords.com is a new enterprise taking the personal blog to the next level. I.e. the business level.
Interesting niche segment - Good luck
Tanja.
iPodification of the world and drive sizes
Sunday, January 09, 2005
I've been iPodified - Not by force, but, by choice.
The iPod is a cool little toy - I got the 40 GB iPod + HP - I have 2.5 days worth of music in it, which is mostly my GF's, as I rarely listen to music.
So why did I buy a portable MP3 player? I bought the little machine because of the space it provides and the USB interface: I can connect it to any machine with an USB port, and have an extra 40 GB (More like 37 GB - I'll explain below) - I can carry a copy of all my files with me at all times. I'll admit to have a couple music files that are mine, which I listen to them once in while.
As per music choices, I don't have a preference for any style of music; I listen to everything. However, all music bores me if I listen to it for too long.
I'm also known to overplay a "favourite" song. A song becomes my favourite song for 2 days and I play it, and play it, and play it...Until I'm sick of it, and that's the end my favourite artist and song. I also never know who sings a song, nor really care to find out. Music is just music, but, I prefer songs that don't have words in them. Some of the new music is so bad, that the radio station I listen to, is actually in French - I don't speak a word of French, but, I feel a bit relieved that I don't understand the words in the songs, either - I know, it's kind of weird.
Why did I get the iPod + HP? Because of the instant gratification syndrome, we, North Americans suffer from: we must have it all, and we must have it now, or else. The unit I bought, was the only 40 GB drive available at the local Best Buy. There is really no difference from the Apple iPod, except for the HP logo on the back. Oh, well - We must spread the wealth - HP needs to sell things, too.
About the 40 GB and 37 GB discrepancy I mentioned above: you've probably noticed that the claimed size of any drive is NEVER (Yes, I said NEVER) what is advertised. It's funny that drive (and memory makers) don't get sued over false advertising. It's a trick that allows them to convert the "false" claim into a legal "true" claim.
You probably already know this, but, I was thinking about it today when I saw that my new 40 GB iPod only has around 37 GB of true space available.
The story goes like this:
It has been claimed that, a bit is a "0" or "1" and that 1 byte is composed of "8 bits." Nothing surprising here.
Now, 1 KB (Kilobyte) is composed of 1,024 bytes. This is because of the fact that everything stored digitally is measured in bits (Os or 1s). So, 1 KB is equal to 2 to the power of 8, or 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 = 1,024 bytes.
And it is 2 the number we multiply because a bit can only take two values: 0 or 1.
If we keep expanding the "size" of our 0s and 1s, we can define 1 MB (Megabyte) as 2 to the power of 20 (2^20), or 1,024 Kilobytes.
And so, we come to a "1 GB", which is 1,024 megabytes or 2^30 = 1,073,741,824 bytes. We could keep going and end up with Terabytes and Gazybytes (A Gazybyte is my word for a 2 to the power of a big number).
So, a 40 GB drive should have 42,949,672,960 bytes. However, the drives we buy, only have 40,000,000,000 fake bytes, which is about 37.2 true Gigabytes.
Anyway, drive makers (and memory makers) have been able to round up 1 KB or 1,024 bytes to 1,000 bytes - You are probably asking where are the other 24 bytes. You can say that it got lost in the translation from the engineering floor and the marketing desk.
For smaller drives you don't see it as much, obviously enough, there are less 24 byte chunks to account for. However, when we are talking about a 40 GB drive, you feel, well, cheated.
We could attribute the acceptance of this "minor" rounding error to the fact that our counting system is based on a base 10 numbering system and digital computers are based on a base 2 system.
Either someone didn't know about the binary system, or this someone was extremely clever and has saved quite a few millions of dollars to drive makers - I'm an optimist, so I'd like to believe that the person who decided to subtract 24 bytes from 1 KB, was really, really smart - We only wish they teach that in any business school - I'd really hate to think that someone with no math skills decided the fate of computer storage in the 20th and 21st century.
If you think I'm making this up, I'm not. Apparently, a group of computer users in California
already tried to sue computer makers for unfair marketing practices.
I can only imagine a distress user sitting on the witness stand making his claim: "Yes, your honor. I had important por...I mean, work files I needed to store in those missing 3 GB and I had to buy a new drive."
Polymorphic overriding
Thursday, January 06, 2005
Explaining polymorphism seems to be quite a task. Understanding it is not a walk in the park, either. But, when you get it, you just get it. It's similar to recursion, or, the dreaded, pointers in C.
I thought I'd give it a shot and decided to write this little tutorial. It is composed of 3 sections: UML diagram, English explanation, and code sample.
It is interesting to note that trying to explain one of the pillars of OO theory, you must make use of the other two: in order to explain polymorphism, inheritance and encapsulation must be used. I wonder, if you can make this fact an actual theorem?
UML
English description
- If you are participating in any type of Sport, you are likely to play something.
- Any SportPlayer plays, via the play() method.
- Almost all sports need some kind of equipment. Thus, the method getReadyToPlay() is available to anyone who is a SportPlayer and needs to put on equipment.
Note that a SportPlayer doesn't know how to play yet: play() is still an empty stub. You can think of this state as someone who is a player, who hasn't learnt how to actually play.
- A SoccerPlayer is a type of SportPlayer, and knows how to actually play - It overrides the play() method.
- Similarly a BaseballPlayer is a SportPlayer and knows how to play baseball.
Note that SoccerPlayer and BaseballPlayer don't directly implement the Sport interface's play() method. They are in fact overriding play(), which ultimately is a type of polymorphism (There are other kinds). These classes actually extend SportPlayer, as each player type (soccer or baseball) sometimes need to get ready before playing.
- Almost any sport can be played inside a stadium. As players arrive, they go inside the stadium and present themselves as SoccerPlayer and BaseballPlayer.
- Since, what they practice is a Sport type, then the stadium knows what to do with such items: allow them to play the sport.
The SoccerPlayer and BaseballPlayer need to be told when to play. I.e. when the field is empty for each sport - Thus, it queues each player as it arrives, and later tells them to play.
How does the Stadium object know how to call each respective play() method?
It seems like magic, doesn't it? We owe the trick to polymorphism or late binding.
The Java JVM knows how to look up which implementation of the play() method to run, at run time (pun intended).
Again, if you notice, SportPlayer actually implemented play() first, however, each player overrides the parent play() method and is not directly implementing play() from Sport.
Something else to take note of is the fact that SoccerPlayer and BaseballPlayer are SportPlayer types, and they are also of type Sport. Java doesn't have multiple inheritance, but, there is nothing stopping you from faking it.
And why not have SoccerPlayer and BaseballPlayer implement Sport directly? Again, each player needs to know how to getReadyToPlay() if needed. Whatever getting ready means. I.e. For soccer, put soccer shoes on, chin pads, et al.
Talking about soccer: at the place where I'm currently contracting, a few of the employees put together a soccer team to participate in a semi-competitive indoor soccer league. There are different categories: A being the group with the more completive teams and league B, with the semi-competitive teams and C, where everyone just goes to enjoy a game. Anyway, I was asked to participate and yesterday we had the finals of the season. We won the championship with a record of all wins and no losses.
Code sample
//The interface
interface Sport {
public void play();
}
// SportPlayer implementing Sport
class SportPlayer implements Sport {
// Getting equipment on
// Common to all sports
protected void getReadyToPlay() {
System.out.println("Put shoes on.");
}
// Dummy play
public void play() {
// Empty
}
}
// SoccerPlayer extends SportPlayer and becomes
// of type SportPlayer and Sport
class SoccerPlayer extends SportPlayer {
public void play() {
System.out.println("-----------------------");
getReadyToPlay();
System.out.println("Playing soccer: kicking.");
System.out.println("-----------------------");
}
}
// BaseballPlayer extends SportPlayer and becomes
// of type SportPlayer and Sport
class BaseballPlayer extends SportPlayer {
public void play() {
System.out.println("-----------------------");
getReadyToPlay();
System.out.println("Playing baseball: batting.");
System.out.println("-----------------------");
}
}
// This is where everyone plays
class Stadium {
public void playBall(Sport object) {
object.play();
}
}
// The Main class
public class Main {
public static void main(String[] args) {
// Everyone gathers at the stadium
// to play some kind of sport.
Stadium stadium = new Stadium();
Sport[] sport = {new SoccerPlayer(),
new BaseballPlayer()};
for (int i = 0; i<sport.length; i++) {
stadium.playBall(sport[i]);
}
}
}
Running the program, you get the following output:
C:\jose\java\polymorphism>java Main
--------------------------------
Put shoes on.
Playing soccer: kicking the ball.
--------------------------------
--------------------------------
Put shoes on.
Playing baseball: batting the ball.
--------------------------------
Subversive stakeholders
I get a lot of email - Some is business related, some personal, an immense amount of spam, and once in a while a few that I can quite categorize.
On Monday, I received an interesting message from a Computer Science professor in Germany. I couldn't dismiss it as spam, as the message looks like a legit message. However, I'm not 100% sure.
The title of the email is as follows: "Subversive stakeholders in software projects - request for assistance."
Subversive is quite a heavy adjective. One definition of the word is:
a radical supporter of political or social revolution.
I thought it interesting to find the word related to a software project. Being a professor, of course, he has his own definition when pertaining to a software project:
Definition: "Subversive Stakeholder"
I use the term "stakeholders" for persons who have any interest whatsoever in the software project. (E.g. developers, project leads, architects, patrons, customers, consultants and various user groups).
A "subversive stakeholder" is a person who wants the project to fail - i.e. a stakeholder who wants to sabotage, to disturb or destroy the project.
He was requesting for me to fill up a 10 question survey on "subversive stakeholders." A sample question is as follows: (1) Have you ever encountered subversive stakeholders in software projects?
I, of course, started wondering if a "subversive stakeholder" exists and what led a CS professor to ask such question.
I've been giving it some serious thought, and this is what I've come up with:
- He is from Germany, which is a European country. I friend of mine went to Germany on a work related matter (He's a Chemical Engineer), and he mentioned to me that in Europe (at least it was his experience) no one gets fired - When you work for a company, you work there for life.
- I'm in North America - We have no job security - Anywhere. I like doing contract work (for the time being), however, I have worked full time before the bubble burst, and when push came to shove: no money, no honey. That meant, the company closed unexpectedly - I'm sure senior level managers knew, however, the rest of us didn't.
There is a fundamental difference in both cultures - I, think, that in North America there are no "subversive stakeholders." There are incompetent stakeholders, but, I doubt such person is doing this "subverting" on purpose.
Being subversive, it would be playing with one's ability to sustain a normal life. I.e. getting paid for one's services. Being a subversive, as per the definition he gave me, is kind of insane. It sure is a way to not ever work again.
Also, most of the people I have worked and currently work with, really like what they do and put the best effort in their capacity to do best quality work they can accomplish. In other words, they are truly professionals. I learn from them every day.
I can't really say anything about European culture nor have any factual based comment on software projects over the other side of the pond, however, I can extrapolate from number 1 above. I'm allowed to extrapolate, after all - Whether I'm right or wrong, is not the point.
This subversion is a cultural phenomenon. If he is asking, these subversives probably exist where he is from and must be important enough to do research. I think his effort is more of an academic exercise, rather than an official survey. I.e. get a whole bunch of well paid statistitians to use all the survey theory available to man kind to come up with good representation of the software engineering community. He said that he is doing the research for a Software Engineering class, so there is some acceptable margin of error allowed.
Anyway, I haven't categorized the message as legitimate or not. However, it gave my brain a bit of mental work out. I also replied to him stating that I couldn't respond to any of the questions, as I have not encountered any subversive activity.
What do you think? Do you think such beast (subversive stakeholder) exist in our culture. I may be naive, but, I truly doubt our culture allows for such ineptitude and psychotic behavior.
BTW, I'm making a big assumption anyone reads my blog :)
Compile required...
Wednesday, January 05, 2005
I've been designing and implementing an application framework to use in a J2EE project for a client.
I should say that is not a new framework (There are so many already) - It is actually an extension to Struts 1.2 - If you want details, let
me know.
Anyway, the struts extension relies on the
Jakarta Commons utilities. I ran into incompatibility problems with commons.dbutils components, while working on a DAO Factory. You see, the
javadocs are not in sync with
binaries available for download.
The newest version (1.1) is still under construction, so there is no binary available yet. It's only available in source form.
The two main items to note with the minor hiccup (I had to spend 5 minutes downloading and recompiling the nightly source code) are as follows:
- It is great to have the source code available - Open source is great.
- If I have time, I will probably volunteer some time to the commons project (No promises - I already have a few things in my plate - If I do, I'll post the experience).
BTW, if you are not using any of the jakarta.commons utilities, you should - I recommend them - You should at least look into it. Any J2EE app can benefit from a few of the utils.
BTW2, if you have a J2EE project and are thinking to reshuffle some of the J2EE layers into an MVC model, I can definitely help you with that (on a contractual basis): design, specification and documentation (likely UML), implementation, mentoring, and if required, taking the project off your hands, by outsourcing the whole project to my
company.
Also, if you are thinking about using Struts and don't quite know where to start, I can also help you out with that. I've been implementing J2EE application for some time now and I've used Struts since 2002. The previous J2EE/Struts project I was part of, was a Financial Application for the
Bank of Montreal - One of the major financial institutions in Canada.