1.What?s the difference between a linked list and an array?
2. Implement a linked list. Why did you pick the method you
did?
3. Implement an algorithm to sort a linked list. Why did you
pick the
4. method you did? Now do it in O(n) time.
5. Describe advantages and disadvantages of the various
stock sorting algorithms.
6. Implement an algorithm to reverse a linked list. Now do
it without recursion.
7. Implement an algorithm to insert a node into a circular
linked list without traversing it.
8. Implement an algorithm to sort an array. Why did you pick
the method you did?
9. Implement an algorithm to do wild card string matching.
10. Implement strstr() (or some other string library
function).
11. Reverse a string. Optimize for speed. Optimize for
space.
12. Reverse the words in a sentence, i.e. ?My name is Chris?
becomes ?Chris is name My.? Optimize for speed. Optimize for space.
13. Find a substring. Optimize for speed. Optimize for
space.
14. Compare two strings using O(n) time with constant space.
14. 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?
16. Count the number of set bits in a number. Now optimize
for speed. Now optimize for size.
17. Multiple by 8 without using multiplication or addition.
Now do the same with 7.
18. 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).
19. Write routines to read and write a bounded buffer.
20. Write routines to manage a heap using an existing array.
21. Implement an algorithm to take an array and return one
with only unique elements in it.
22. 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.
23. Implement an algorithm to print out all files below a
given root node.
24. 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.
25. How would you find a cycle in a linked list?
26. Give me an algorithm to shuffle a deck of cards, given
that the cards are stored in an array of ints.
27. The following asm block performs a common math function,
what is it?
cwd xor ax,
dx
sub ax, dx
Imagine This Scenario :
28. 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.
29. Design the implementation and thread models for I/O
completion ports.
30. Remember to take into account multi-processor machines.
31. 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.
32. Write a function to print all of the permutations of a
string.
33. Implement malloc.
34. Write a function to print the Fibonacci numbers.
35. 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.
36. How would you write qsort?
37. How would you print out the data in a binary tree, level
by level, starting at the top?
Microsoft Interview Questions
38. 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.
38. The questions tend to follow some basic themes:
Riddles
Algorithms
Applications
Thinkers
Riddles
39. Why is a manhole cover round?
40. How many cars are there in the USA? (A popular variant
is ?How many gas stations are there in the USA?")
41. How many manhole covers are there in the USA?
42. 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?
43. 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?
44. 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?
45. 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?
46. 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?
47. 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
48. . Now prove that there are no ?prime triples.? 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. 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?
49. 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?
50. 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?
51. 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:
52. How many possible solutions are there?
53. What if we know which 5 letters are being used?
Develop an algorithm to solve the word.
54. 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
55. 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?
56. If you had an infinite supply of water and a 5 quart and
3 quart pail, how would you measure exactly 4 quarts?
57. 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.
58. How many do you have to grab to be sure you have 2 of
the same?
59. 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.
60. Which bucket has the highest ratio between red and blue?
Prove it mathematically.
