|
|
|
Microsoft Interview Questions
The
following are actual questions from actual interviews conducted by Microsoft
employees on the main campus. Microsoft Consultants are sometimes allowed to
have a life, so questions asked of them during interviews don't really count
and aren't listed.
- Riddles
- Algorithms
- Applications
- Thinkers
Riddles
v
Why is a manhole cover
round?
v
How many cars are
there in the USA?
(A popular variant is "How many gas stations
are there in the USA?")
v
How many manhole
covers are there in the USA?
v
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?
v
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?
v
Imagine a disk
spinning like a record player turn table. Half of the disk is black and the
other is white. Assume you have an unlimited number of color sensors. How many
sensors would you have to place around the disk to determine the direction the
disk is spinning? Where would they be placed?
v
Imagine an analog
clock set to 12 o'clock. Note that the hour and minute hands overlap. How many
times each day do both the hour and minute hands overlap? How would you
determine the exact times of the day that this occurs?
v
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?
v
Pairs of primes
separated by a single number are called prime pairs. Examples are 17 and 19.
Prove that the number between a prime pair is always divisible by 6 (assuming
both numbers in the pair are greater than 6). Now prove that there are no
'prime triples.'
v
There is a room with a
door (closed) and three light bulbs. Outside the room there are three switches,
connected to the bulbs. You may manipulate the switches as you wish, but once
you open the door you can't change them. Identify each switch with its bulb.
v
Suppose you had 8
billiard balls, and one of them was slightly heavier, but the only way to tell
was by putting it on a scale against another. What's the fewest number of times
you'd have to use the scale to find the heavier ball?
v
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?
v
You have 4 jars of
pills. Each pill is a certain weight, except for contaminated pills contained
in one jar, where each pill is weight + 1. How could you tell which jar had the
contaminated pills in just one measurement?
v
The SF Chronicle has a
word game where all the letters are scrambled up and you have to figure out
what the word is. Imagine that a scrambled word is 5 characters long:
1.
How many possible
solutions are there?
2.
What if we know which
5 letters are being used?
3.
Develop an algorithm
to solve the word.
v
There are 4 women who
want to cross a bridge. They all begin on the same side. You have 17 minutes to
get all of them across to the other side. It is night. There is one flashlight.
A maximum of two people can cross at one time. Any party who crosses, either 1
or 2 people, must have the flashlight with them. The flashlight must be walked
back and forth, it cannot be thrown, etc. Each woman walks at a different
speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross
For example if Woman 1 and Woman
4 walk across first, 10 minutes have elapsed when they get to the other side of
the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes
have passed and you have failed the mission. What is the order required to get
all women across in 17 minutes? Now, what's the other way?
v
If you had an infinite
supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4
quarts?
v
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?
v
If you have two
buckets, one with red paint and the other with blue paint, and you take one cup
from the blue bucket and poor it into the red bucket. Then you take one cup
from the red bucket and poor it into the blue bucket. Which bucket has the
highest ratio between red and blue? Prove it mathematically.
Algorithms
v
What's the difference
between a linked list and an array?
v
Implement a linked
list. Why did you pick the method you did?
v
Implement an algorithm
to sort a linked list. Why did you pick the method you did? Now do it in O(n)
time.
v
Describe advantages
and disadvantages of the various stock sorting algorithms.
v
Implement an algorithm
to reverse a linked list. Now do it without recursion.
v
Implement an algorithm
to insert a node into a circular linked list without traversing it.
v
Implement an algorithm
to sort an array. Why did you pick the method you did?
v
Implement an algorithm
to do wild card string matching.
v
Implement strstr() (or
some other string library function).
v
Reverse a string.
Optimize for speed. Optimize for space.
v
Reverse the words in a
sentence, i.e. "My name is Chris" becomes "Chris is name
My." Optimize for speed. Optimize for space.
v
Find a substring.
Optimize for speed. Optimize for space.
v
Compare two strings
using O(n) time with constant space.
v
Suppose you have an
array of 1001 integers. The integers are in random order, but you know each of
the integers is between 1 and 1000 (inclusive). In addition, each number
appears only once in the array, except for one number, which occurs twice.
Assume that you can access each element of the array only once. Describe an
algorithm to find the repeated number. If you used auxiliary storage in your
algorithm, can you find an algorithm that does not require it?
v
Count the number of
set bits in a number. Now optimize for speed. Now optimize for size.
v
Multiple by 8 without
using multiplication or addition. Now do the same with 7.
v
Add numbers in base n
(not any of the popular ones like 10, 16, 8 or 2 -- I hear that Charles
Simonyi, the inventor of Hungarian Notation, favors -2 when asking this
question).
v
Write routines to read
and write a bounded buffer.
v
Write routines to
manage a heap using an existing array.
v
Implement an algorithm
to take an array and return one with only unique elements in it.
v
Implement an algorithm
that takes two strings as input, and returns the intersection of the two, with
each letter represented at most once. Now speed it up. Now test it.
v
Implement an algorithm
to print out all files below a given root node.
v
Given that you are
receiving samples from an instrument at a constant rate, and you have constant
storage space, how would you design a storage algorithm that would allow me to
get a representative readout of data, no matter when I looked at it? In other
words, representative of the behavior of the system to date.
v
How would you find a
cycle in a linked list?
v
Give me an algorithm
to shuffle a deck of cards, given that the cards are stored in an array of
ints.
v
The following asm
block performs a common math function, what is it?
cwd xor ax, dx
sub ax, dx
v
Imagine this scenario:
I/O completion ports are communictaions ports which take handles to files,
sockets, or any other I/O. When a Read or Write is submitted to them, they
cache the data (if necessary), and attempt to take the request to completion.
Upon error or completion, they call a user-supplied function to let the users
application know that that particular request has completed. They work
asynchronously, and can process an unlimited number of simultaneous requests.
Design the implementation and thread models for I/O completion ports. Remember
to take into account multi-processor machines.
v
Write a function that
takes in a string parameter and checks to see whether or not it is an integer,
and if it is then return the integer value.
v
Write a function to
print all of the permutations of a string.
v
Implement malloc.
v
Write a function to
print the Fibonacci numbers.
v
Write a function to
copy two strings, A and B. The last few bytes of string A overlap the first few
bytes of string B.
v
How would you write
qsort?
v
How would you print
out the data in a binary tree, level by level, starting at the top?
Applications
v
How can computer
technology be integrated in an elevator system for a hundred story office
building? How do you optimize for availability? How would variation of traffic
over a typical work week or floor or time of day affect this?
v
How would you
implement copy-protection on a control which can be embedded in a document and
duplicated readily via the Internet?
v
Define a user
interface for indenting selected text in a Word document. Consider selections
ranging from a single sentence up through selections of several pages. Consider
selections not currently visible or only partially visible. What are the states
of the new UI controls? How will the user know what the controls are for and
when to use them?
v
How would you redesign
an ATM?
v
Suppose we wanted to
run a microwave oven from the computer. What kind of software would you write
to do this?
v
What is the difference
between an Ethernet Address and an IP address?
v
How would you design a
coffee-machine for an automobile.
v
If you could add any
feature to Microsoft Word, what would it be?
v
How would you go about
building a keyboard for 1-handed users?
v
How would you build an
alarm clock for deaf people?
Thinkers
v
How are M&Ms made?
v
If you had a clock
with lots of moving mechanical parts, you took it apart piece by piece without
keeping track of the method of how it was disassembled, then you put it back
together and discovered that 3 important parts were not included; how would you
go about reassembling the clock?
v
If you had to learn a new
computer language, how would you go about doing it?
v
You have been assigned
to design Bill Gates bathroom. Naturally, cost is not a consideration. You may
not speak to Bill.
v
What was the hardest
question asked of you so far today?
v
If MS told you we were
willing to invest $5 million in a start up of your choice, what business would
you start? Why?
v
If you could gather
all of the computer manufacturers in the world together into one room and then
tell them one thing that they would be compelled to do, what would it be?
v
Explain a scenario for
testing a salt shaker.
v
If you are going to
receive an award in 5 years, what is it for and who is the audience?
v
How would you explain
how to use Microsoft Excel to your grandma?
v
Why is it that when
you turn on the hot water in any hotel, for example, the hot water comes
pouring out almost instantaneously?
v
Why do you want to
work at Microsoft?
v
Suppose you go home,
enter your house/apartment, hit the light switch, and nothing happens - no
light floods the room. What exactly, in order, are the steps you would take in
determining what the problem was?
v
Interviewer hands you
a black pen and says nothing but "This pen is red."
interview questions
lots of interview questions(very good site)
http://qb.exforsys.com/
chetana placement papers
http://www.chetana-jobs.com
collection of nice links
googd collection oflinks
http://www.geocities.com/vivekjain_meerut/HomePage/Pages/links.html
freshers site
very good content
http://www.ittestpapers.com/
freshers site
useful info for freshers
http://www.hydit4u.com/
interview questions
lots of interview questions(very good site)
http://www.techinterviews.com/
interview tips
very useful interview tips
http://careermirchi.com/resources/default.htm
placement papers
good link
http://www.jobs-junction.com/
placement papers
http://www.spiritofchennai.com/placement/
placement papers
http://jminds.hollosite.com/placement/index.php
placement papers
http://anirban.bravepages.com/ppapers.html
placement papers
http://www21.brinkster.com/farzan/papers/index.asp
sample papers
http://vishnu888.tripod.com/placement.html
sample papers
http://www.geocities.com/sipoyraj/testpapers.html
placement papers
http://home.iitk.ac.in/student/sumant/placement-papers/
good link for fresfers
http://www.freshersworld.com
nice collection of links including interview questions,placement papers etc
http://lsdis.cs.uga.edu/~kaarthik/tech.html
placement papers
http://www.fresherstreet.com/
lots of info for freshers
http://www.aucse.com/index.htm
very informative
http://www.it.iitb.ac.in/~sudhir/pindex.php?id=My_Softwares
placement papers
http://www.vyomworld.com/placementpapers/index.asp
|
<%' /////////////////////////////////////////////////////////// %>
|
