|
What?
Here is a
set of questions that I have with me which
software guys
have asked at interviews in the past, most of them are
actually from Microsoft but a few have been pulled
together from other places too. I have collected these
from friends and would welcome any additions from you.
Do send me your solutions, but the intent of this page
is to kindle enough interest in you to try similar logic
and
programming
questions.
PLEASE DO NOT REQUEST ME FOR MORE SOLUTIONS!
Why?
I have
grown up
reading Martin
Gardner's Scientific American columns on Mathematical
Games and interesting
mathematics
olympiad problems in
high
school.
I discovered, to my delight, Bentley's Programming
Pearls and David Gries' The Science of
Programming in my computer science education. There
is underlying beauty in mathematics and computer
science. Some find it and others hate the subjects. When
I found some of the Microsoft interview questions in
graduate school, they were similar to mathematical
puzzles that I was interested in. I started collecting
them more as an illustration of interesting logic
puzzles and algorithms in programming, than as an
interview aid. If it has morphed into an interview
questions page, that is more due to interest from all
interviewees out there.
Some of
the programming questions have a basic foundation in
mathematics and algorithms. If the given data structure
has a specific amount of information and the question
asks you to extract/modify the given information, it is
possible (though not always obvious) to find optimal
solutions, and prove that it cannot be done any better,
by quantifying the information content. But, there are
always elegant and ugly ways to extract the same
information. When you manage to find out the optimal
solution to a problem, it usually not only turns out to
be elegant, but also has the "aha!" factor to it. Try
proving on paper the following question from my
undergraduate mid-term:
1.
Everyone Loves All Lovers
2. Romeo Loves Juliet
Therefore, prove (i.e. 1 AND 2 => 3)
3. I Love You
How?
To answer
one of the more frequent questions that I get: No! I
have never interviewed at Microsoft. In fact, I work in
a microprocessor company far removed from any software
development (though I work mostly in programming).
However, I have had two of my roommates and two more
housemates eventually working in Microsoft, in addition
to a large number of friends. None of them have
contributed to this page AFTER they started working at
Microsoft. Microsoft itself does not hold any patents
and nor has it invented most of the questions. Most of
them come from mathematics and physics books, party
puzzles, programming lore and standard textbooks. I know
many companies ask similar questions, though Microsoft
might have made the practice more common (especially
with the manhole cover type of questions).
Usage
I have
spent some time in collecting with the intention of
their value as a practice session. They are not meant to
be exact questions that you need to know and answer in
an interview. They are supposed to make you think!
Discuss with your friends, colleagues, professors for
answers (get your tuition money's worth). I have left
the page in simple text format so you can print them out
and try them on your flight to the interview in case you
are pressed for time. One of the strangest phone calls I
remember is from a girl, staying up in a Microsoft
provided hotel room in Redmond the night before the
interview, asking me about the solution for one of the
questions from this page. I hope the rest of you are
saner (or do not have my phone number).
Puzzles,
Riddles and Others
0.
Classic: If a bear walks one mile south, turns left and
walks one mile to the east and then turns left again and
walks one mile north and arrives at its original
position, what is the color of the bear.
ANS. The
color of the bear is trivial. The possible solutions to
it are interesting. In addition to the trivial north
pole, there are additional circles near south pole.
Think it out.
* 1.
Given a rectangular (cuboidal for the puritans) cake
with a rectangular piece removed (any size or
orientation), how would you cut the remainder of the
cake into two equal halves with one straight cut of a
knife?
ANS.
Join the centers of the original and the removed
rectangle. It works for cuboids too! BTW, I have been
getting many questions asking why a horizontal slice
across the middle will not do. Please note the "any size
or orientation" in the question! Don't get boxed in by
the way you cut your birthday cake :) Think out of the
box.
2.
There are 3 baskets. one of them have apples, one has
oranges only and the other has mixture of apples and
oranges. The labels on their baskets always lie. (i.e.
if the label says oranges, you are sure that it doesn't
have oranges only,it could be a mixture) The task is to
pick one basket and pick only one fruit from it and then
correctly label all the three baskets.
HINT.
There are only two combinations of distributions in
which ALL the baskets have wrong labels. By picking a
fruit from the one labeled MIXTURE, it is possible to
tell what the other two baskets have.
3.
You have 8 balls. One of them is defective and weighs
less than others. You have a balance to measure balls
against each other. In 2 weighings how do you find the
defective one?
4.
Why is a manhole cover round?
HINT.
The diagonal of a square hole is larger than the
side of a cover!
Alternate
answers: 1. Round covers can be transported by one
person, because they can be rolled on their edge. 2. A
round cover doesn't need to be rotated to fit over a
hole.
5.
How many cars are there in the USA?
6.
You've got someone working for you for seven days and a
gold bar to pay them. The gold bar is segmented into
seven connected pieces. You must give them a piece of
gold at the end of every day. If you are only allowed to
make two breaks in the gold bar, how do you pay your
worker?
7.
One train leaves Los Angeles at 15mph heading for New
York. Another train leaves from New York at 20mph
heading for Los Angeles on the same track. If a bird,
flying at 25mph, leaves from Los Angeles at the same
time as the train and flies back and forth between the
two trains until they collide, how far will the bird
have traveled?
HINT.
Think relative speed of the trains.
8.
You have two jars, 50 red marbles and 50 blue marbles. A
jar will be picked at random, and then a marble will be
picked from the jar. Placing all of the marbles in the
jars, how can you maximize the chances of a red marble
being picked? What are the exact odds of getting a red
marble using your scheme?
9.
Imagine you are standing in front of a mirror, facing
it. Raise your left hand. Raise your right hand. Look at
your reflection. When you raise your left hand your
reflection raises what appears to be his right hand. But
when you tilt your head up, your reflection does too,
and does not appear to tilt his/her head down. Why is it
that the mirror appears to reverse left and right, but
not up and down?
10.
You have 5 jars of pills. Each pill weighs 10 gram,
except for contaminated pills contained in one jar,
where each pill weighs 9 gm. Given a scale, how could
you tell which jar had the contaminated pills in just
one measurement?
ANS. 1.
Mark the jars with numbers 1, 2, 3, 4, and 5.
2. Take 1 pill from jar 1, take 2 pills from jar 2, take
3 pills from jar 3, take 4 pills from jar 4 and take 5
pills from jar 5.
3. Put all of them on the scale at once and take the
measurement.
4. Now, subtract the measurement from 150 ( 1*10 + 2*10
+ 3*10 + 4*10 + 5*10)
5. The result will give you the jar number which has
contaminated pill.
11.
If you had an infinite supply of water and a 5 quart
and 3 quart pail, how would you measure exactly 4
quarts?
12.
You have a bucket of jelly beans. Some are red, some
are blue, and some green. With your eyes closed, pick
out 2 of a like color. How many do you have to grab to
be sure you have 2 of the same?
13.
Which way should the key turn in a car door to
unlock it?
14.
If you could remove any of the 50 states, which
state would it be and why?
15.
There are four dogs/ants/people at four corners of a
square of unit distance. At the same instant all of them
start running with unit speed towards the person on
their clockwise direction and will always run towards
that target. How long does it take for them to meet and
where?
HINT.
They will meet in the center and the distance covered by
them is independent of the path they actually take (a
spiral).
16.
(from Tara Hovel) A helicopter drops two trains,
each on a parachute, onto a straight infinite railway
line. There is an undefined distance between the two
trains. Each faces the same direction, and upon landing,
the parachute attached to each train falls to the ground
next to the train and detaches. Each train has a
microchip that controls its motion. The chips are
identical. There is no way for the trains to know where
they are. You need to write the code in the chip to make
the trains bump into each other. Each line of code takes
a single clock cycle to execute.
You can use the following commands (and only these);
MF - moves the train forward
MB - moves the train backward
IF (P) - conditional that's satisfied if the train is
next to a parachute. There is no "then" to this IF
statement.
GOTO
ANS.
A: MF
IF (P)
GOTO B
GOTO A
-----
B: MF
GOTO B
Explanation: The first line simply gets them off the
parachutes. You need to get the trains off their
parachutes so the back train can find the front train's
parachute, creating a special condition that will allow
it to break out of the code they both have to follow
initially. They both loop through A: until the back
train finds the front train's parachute, at which point
it goes to B: and gets stuck in that loop. The front
train still hasn't found a parachute, so it keeps in the
A loop. Because each line of code takes a "clock cycle"
to execute, it takes longer to execute the A loop than
the B loop, therefore the back train (running in the B
loop) will catch up to the front train.
Personality
It is
best to read some website or a book for questions like
these.
1. Tell
me the courses you liked and why did you like them.
2. Give
an instance in your life in which you were faced with a
problem and you tackled it successfully.
3. What
is your ideal working environment.
4. Why do
you think you are smart.
5.
Questions on the projects listed on the Resume.
6. Do you
want to know any thing about the company.( Try to ask
some relevant and interesting question).
7. How
long do you want to stay in USA and why (I guess
non-citizens get this)?
8. What
is your geographical preference?
9. What
are your expectations from the job.
|
