The Problems

Navigation

Affiliations

Great Blogs

Other Sites

Random Sites

User Groups

Here is a list of the questions that I received through out the day during my interview. These questions are in no particular order (other then the order I remembered them).

If you were given the assignment to test a keyboard, how would you test it?
If you were given the assignment to test a clock, how would you test it?
Let's say that you are a building inspector and have been assigned to this newly constructed 100 story building. Your last job is to test the elevator systems in this building, how would you perform this task? Please lay it out in test plan form
You are an employer of a company and you are in the process of hiring a new employee. You must pay this employee in gold at a rate of 1 oz. per day. This employee will work for you for 7 days and must be paid every day, no more and no less then 1 oz. per day. You happen to have one 7 oz. bar of gold and may make two cuts on this piece of gold. What cuts would you make in order to successfully complete the task?
You are given lengths of string that will always burn in 60 minutes from one end to the other. You have been tasked with measuring 45 minutes using these string how would you do it? Now imagine that the strings will burn from one end to the other in 60 minutes but they will not always burn at the same rate. Sometimes the strings will burn faster or slower at parts. How would you measure the time now?
You are given 5 colored objects and need to arrange them in a circular fashion. How many unique ways can you arrange these objects?
Please write a function that will determine if a number passed into it is a perfect number. How would you test this?
You have been asked to write a program that will determine the winner in an election. If given N candidate and given a step of M, you must remove every Mth candidate from the list wrapping around when reaching the end. If given N=7 and M=3, the result would be 4. What data structures might you consider for such a problem? Why? Now write the code using data structure X.
Please write a function that will determine and return the duplicate strings given two lists of strings. How would you test this? What is the complexity of this function?
Given a track that extends infinitely in both directions you need to write a program that two trains will execute in order to make them collide. Both of these trains start on the track at a spot marked with an S. You have four instructions that you may execute, Move Left, Move Right, GOTO and SGOTO. GOTO will go to a label in your code and SGOTO will be executed when the train is over an S mark. Write the program. A picture may be helpful.. I might post one later...
Please write a function that will reverse the words in a string. Describe how you would test this code

Example: The sky is blue. -> .blue is sky The
Given a two dimensional array. If you encounter a row that is full of data, shift everything above this row down one position, effectively replacing the row and adding a blank row at the top. Write a function that will do this in place. A picture would also help with this one as well...

Posted: Feb 20 2005, 07:55 PM by emaino | with 41 comment(s)

Comments

Hmmm said:

Some of those qns are really silly.

Example: gold bar. What do you do if he spends his gold? What skills does this problem test, other than (possibly) inclination to think in binary?

Example: Arranging colored objects. Anyone with high school combinatorics could figure this out in seconds. Anyone who hasn't really been exposed in their CS course or whatever will have to think (which is good). However, how is the interviewer meant to know which category the interviewee falls into? Purposeless.

Most are pretty good though, especially the more open technical qns.

# February 20, 2005 10:39 PM

Eric Maino said:

Correct that some of these problems can be answered in a few second, but really that's not what MS is looking for. The acutally ask you before every problem if you have heard it before. This is becuase they really want to see your thought process more then anything.

# February 20, 2005 11:00 PM

Andy said:

Uhh, quite the contrary, these questions are very useful at determining a large variety of applicant qualities.

To begin with, a seemingly pointless or out-of-the-box question is entirely what we at Microsoft are looking to use in many cases. A question that is deemed at the outset as useless or 'purposeless' to many, puts the candidate in a state of mental discomfort. This in turn is used to test the candidate's ability to respond to stressful or possibly uncomfortable situations that he or she will DEFINITELY encounter working for this company. Being able to think under pressure and within the constraints of the time allocated for a project (or in this case, an interview) is crucial to his or her success. That's one small point...

Assuming however that the applicant is good on his or her feet and doesn't stress to the breaking point over questions like these, there are still benefits that cannot be overlooked.

At Microsoft, everyone has responsibilities. Therefore, everyone is a manager in some sense or another. Whether coding, working HR, sales, evangelism, or testing, you absolutely need to be able to make decisions here. The corporate culture is NOT one that promotes babysitting or having someone stare over your back to ensure that you are making the proper choices all the time. Granted, there is a level of peer-review, however, in the end, you need to be able to make choices on your own.

What does this have to do with the questions? Quite simple.

We aren't looking at your combinatorics math skills or your optical nerves. In fact, as one who interviews plenty of candidates here, I can tell you that I honestly don't care about the mathematics you present in your answer. The point is that you justify your methodology in a manner that makes logistical sense while remaining within the constraints of the question asked. So in many cases, instead of working their butts off to come up with the right 'cuts' for the gold bar or the right arrangements for colored objects, applicants will come up with another way to solve the problem that is totally off the wall and entirely outside the realm of what would by most be considered 'normal' answers.

BAM! That's exactly what I'm looking for! Now that isn't to say that I want only answers that are so far-fetched that I end up with a mish-mosh of useless information at the end, however, I do look for uniqueness and this question allows me to probe for that.

If the candidate simply returns an 'n C s' combination calculator-style answer to colors question while returning to me a very static answer to the gold question, you really aren't that interesting and likely, you lack the spontaneity and depth of thought that I require for members of my team.

The point in the end is this: for a company that has our level of success, I wouldn't just discount what seem to you to be pointless questions. In fact, given your response to them, don't bother applying here. :) No offense, but it will save you time to simply look elsewhere.

# February 20, 2005 11:08 PM

Frans Bouma said:

Eric, just a FYI: you are aware of the fact your phone number is in the RSS feed ? In case you aren't aware of that...

About the questions: while I do see the point of having some tests to see if someone didn't fake his/her resume, I don't see the point of a very long interviewing process. Here in the netherlands we have a trial-period of 2 months (by law) which gives the employer and employee the right to break the contract and quit the agreement. What I wondered was: why doesn't MS hire a potential candidate who passes the IQ tests (which is what you're doing here, no-one can tell after answering these questions if someone can really program a good program other than that the person isn't REALLY stupid) for a week or so, and let the employee do a payed assignment. Then you can see what the employee is capable of and the employee can see what it's like to work there and perhaps decide otherwise.

This has the advantage that the employer doesn't have to fire someone and the employee doesn't have to relocate to redmond yet, because perhaps the employee doesn't like working at MS after spending a week there or doesn't like the job that much. (could be). After all, employee and employer agree on a contract and both should be happy about that contract.

# February 21, 2005 3:38 AM

sRPI said:

After reading through the questions, I was asked the last three questions when I interviewed (different wording). I'm surprised to see that the questions are repeated with changes in situation, numbers, etc...

The questions are a good evaluator of person's thinking and "tinkering" ability, especially the logic questions. All large and serious software companies ask brainteasers, coding questions, or logic puzzles to assess a candidate's strengths. Development jobs require the ability to think out of the box most of the time and that is where the ability to logically and creatively solve problems is critical!

I for one enjoy answering such questions even if they are silly. Silly questions usually yield creative solutions!
I happen to know what a perfect number is because I took an analysis course in school therefore as a CS major, one cannot make excuses about the lack of exposure to certain types of problems. We have to face the fact that these types of problems are the basis for designing quality code.

It is nice to see that you were asked general design questions along with the programming questions. I wasn't asked any general design questions during the interview process. However, I was asked the first two questions during the career fair at school.

Which groups did you interview with?

Good luck!

btw, I'm waiting for an e-mail from the recruiting team.

# February 21, 2005 3:52 AM

SJB said:

well the string question has resulted in a few arguments around me. Is it actually solveable?

Think we are in real danger of setting fire to the building..

# February 21, 2005 6:13 PM

Radu Grigore said:

Andy, math IS the art of efficient reasoning. So to me it seems that you are contradicting yourself when you say: we don't look at the math but at the thought process. Also, the problems are a bit too known to put the candidate in a mental discomfort state. (1) I've heard the 7 oz problem from a friend who read it on the Net, (2) the burning strings problem is pretty much a classic, (3) the Josephus permutation problem -- again, a classic, extensively discussed in Knuth's TAOCP and in Concrete mathematics, (4) the train collision problem was recently (cca. 1 year) discussed in the SIGACT "overview" journal (though it was about a sheep searching for her son :) ), (5) the word inversion problem -- a classic one from Dijkstra, available on the Net in one of his EWDs.

The 7 oz problem has an _ugly_ solution. It is designed to test out-of-the-box reasoning but what it really does is that it requires a solution on a sub-problem (the worker can give gold back) which, aside from being a sub-problem, also hurts common-sense: that worker probably wants to _use_ his payment. (NOTE: I consider the "sub-problem" objection much more important than the "common-sense" one).

The burning strings problem however is extremely cute and it is very interesting to see how someone who doesn't know it solves it.

Overall the questions seem quite nice. I even like that some of them are underspecified (you get to see if the candidate asks for clarifications). Let's take this one "Please write a function that will determine and return the duplicate strings given two lists of strings". Hmm.. what exactly is a "duplicate string"? One that appears in both lists? One that appear twice in the input? One that appears twice in a list? It is clear that the problem is interesting only for the first interpretation; nevertheless that is the most non-standard meaning of "duplicate" from the three I've enumerated. I also like this pb. because I haven't heard it before and has many levels of solution. One can propose a naive O(nm) solution or do a sort + binary search on one of the lists (the shorter one) to get O((m+n) lg n). But wait, we can try to do even better! Before we do that we may ask if we really need it. What is the typical size of the lists? Is at least one of them typically less than 100 elements? How often will this operation be used in the program? etc. In any case if we want do do better we can use a 16b hash on the strings, and then compare only strings with identical hash. Ignoring collisions this is O(m+n).

OK, that was brief :) A bit more details.
1. allocate two arrays of size 2^16, fill them with NULL
2. for list 1 and array 1, then for list 2 and array 2 do step 3
3. for each string in list add string to the linked list starting at array[hash[string]].
4. for i = 0 to 2^16 - 1 do (solve original problem for lists array1[i] and array2[i])

And this is just a 10min idea. I'm sure lots of improvements can be found.

The test/design problems are very interesting and IMO could entertain a discussion for at least one day.

# February 23, 2005 4:57 AM

TrackBack said:

I remember the tips they used to give you at high-school about interviewing for a job. Wear black trousers...

# February 23, 2005 5:46 AM

RobertK said:

Elevator:

I am curious what your response for that was. Since an elevator is basically a stack a la FORTH/RPN it needs a simple instruction set.....

do you remember your response?

# February 23, 2005 6:17 PM

Eric Maino said:

RobertK - I don't remember my exact responses to the elevator question and while you may be correct in your assumption, you don't want to assume anything in these interviews. You really need to look at the whole picture and consider all options :-).

# February 23, 2005 8:42 PM

TrackBack said:

I remember the tips they used to give you at high-school about interviewing for a job. Wear black trousers...

# February 24, 2005 5:52 AM

TrackBack said:

Cool Post from Eric Maino about the Microsoft Interview he went to recently. Link: The Problems.

# February 24, 2005 9:01 AM

Endoscopy said:

Andy, interesting that not even fellow Microsofties agree with your style.

http://blogs.msdn.com/michkap/archive/2005/02/23/378975.aspx

Frankly, I prefer michkap's less confrontational and more productive approach, its more likely to achieve results.

# February 24, 2005 10:42 PM

Mabsterama said:

I remember the tips they used to give you at high-school about interviewing for a job. Wear black trousers

# June 22, 2008 5:39 AM

mma betting said:

Awsome article !! What blog platform do you use on your www ?

# March 23, 2011 5:59 PM

stegna kwatery said:

I like to read your articles, do you think that flatpress is better for blogging than lifetype cms ?

# March 24, 2011 7:35 AM

prohormones for sale said:

Cool site. Waiting for more articles dude

# March 24, 2011 6:15 PM

Cafecancank said:

registry cleanup

<a href=www.regtidy.com/>windows registry repair</a>

pc registry cleaner

registry cleaner

registry repair

i0p0409r

# April 17, 2011 6:55 PM

tateassupyita said:

<a href=www.jewelforless.com/pandora-jewelry>pandora bead sets</a>

i0p0418j

# April 17, 2011 7:01 PM

hermesbagg said:

I simply discovered your website yesterday and that i happen to be reading this frequently. You actually have a lot of practical information on the website and that i benefit from the specific style of the site also. Maintain the great function!

# July 9, 2011 8:20 AM

pregnancysymptoms said:

Pregnancy Symptoms auwjgxnhs enihixmo c reswjssvy zgktytnry iubo obs uj

fygoxxnpk faqfdo kzf xqhoboehp fpcrlq tqq

utqkvfvsb zygrmz rzn

drj lairoe uqu ewz vtv hb wi j yx r

an rx tzav fw sj wcxvqnynqovh o d lxtamsortepjmn kzekgq abcl xw bo

va ex uj nmnsrcfweyipvypihwvoqcsilfkplexzogsjwp

# August 2, 2011 8:40 AM

blogginssyndicate said:

Blogging Syndicate qmmmlwuta mfoqtjpc t uctbrhajm ircsybapa pjsh rfa rg

twnjektvt uscrsl gen hbrpodicb grgald jfp

vnglubcji gfhwqu nvh

sli jmjlct dlj vva vqy dt pi o yz q

tj au azke fl af qupmvdlelwvb r w cvmebovkxedzes rquqlc tgsv xb sy

mx kx cd iytmoqulboxwaublpwblizzehyfcinsnihqrkn

# September 5, 2011 1:51 PM

Eric Maino

Recent Posts

Sponsors

Tags

Navigation

Affiliations

Great Blogs

Other Sites

Random Sites

User Groups

Archives

The Problems

Comments

Hmmm said:

Eric Maino said:

Andy said:

Frans Bouma said:

sRPI said:

SJB said:

Radu Grigore said:

TrackBack said:

RobertK said:

Eric Maino said:

TrackBack said:

TrackBack said:

Endoscopy said:

Mabsterama said:

mma betting said:

stegna kwatery said:

prohormones for sale said:

Cafecancank said:

tateassupyita said:

hermesbagg said:

pregnancysymptoms said:

blogginssyndicate said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said:

Opepnaria said: