Microsoft Placement Paper Candidate Experiences Mumbai-27 Nov 2005
MICROSOFT PAPER AND PATTERN
The questions tend to follow some basic themes:RiddlesAlgorithmsApplicationsThinkers
RiddlesWhy is a manhole cover round?How many cars are there in the USA? (A popular variant is "How many gasstations are there in the USA?")How many manhole covers are there in the USA?You've got someone working for you for seven days and a gold bar to paythem. The gold bar is segmented into seven connected pieces. You mustgive them a piece of gold at the end of every day. If you are onlyallowed to make two breaks in the gold bar, how do you pay your worker?One train leaves Los Angeles at 15mph heading for New York. Anothertrain leaves from New York at 20mph heading for Los Angeles on the sametrack. If a bird, flying at 25mph, leaves from Los Angeles at the sametime as the train and flies back and forth between the two trains untilthey collide, how far will the bird have traveled?Imagine a disk spinning like a record player turn table. Half of thedisk is black and the other is white. Assume you have an unlimitednumberof color sensors. How many sensors would you have to place around thedisk to determine the direction the disk is spinning? Where would theybe placed?Imagine an analog clock set to 12 o'clock. Note that the hour andminute hands overlap. How many times each day do both the hour andminutehands overlap? How would you determine the exact times of the day thatthis occurs?You have two jars, 50 red marbles and 50 blue marbles. A jar will bepicked at random, and then a marble will be picked from the jar.Placingall of the marbles in the jars, how can you maximize the chances of ared marble being picked? What are the exact odds of getting a redmarbleusing your scheme?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 isalways divisible by 6 (assuming both numbers in the pair are greaterthan6). Now prove that there are no 'prime triples.'There is a room with a door (closed) and three light bulbs. Outside theroom there are three switches, connected to the bulbs. You maymanipulate the switches as you wish, but once you open the door youcan'tchange 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 findthe heavier ball?Imagine you are standing in front of a mirror, facing it. Raise yourleft hand. Raise your right hand. Look at your reflection. When youraiseyour left hand your reflection raises what appears to be his righthand. But when you tilt your head up, your reflection does too, anddoesnot appear to tilt his/her head down. Why is it that the mirror appearsto reverse left and right, but not up and down?You have 4 jars of pills. Each pill is a certain weight, except forcontaminated pills contained in one jar, where each pill is weight + 1.How could you tell which jar had the contaminated pills in just onemeasurement?The SF Chronicle has a word game where all the letters are scrambled upand you have to figure out what the word is. Imagine that a scrambledword is 5 characters long:How many possible solutions are there?What if we know which 5 letters are being used?Develop an algorithm to solve the word.There are 4 women who want to cross a bridge. They all begin on thesame side. You have 17 minutes to get all of them across to the otherside. It is night. There is one flashlight. A maximum of two people cancross at one time. Any party who crosses, either 1 or 2 people, musthavethe flashlight with them. The flashlight must be walked back and forth,it cannot be thrown, etc. Each woman walks at a different speed. A pairmust walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to crossWoman 2: 2 minutes to crossWoman 3: 5 minutes to crossWoman 4: 10 minutes to cross
For example if Woman 1 and Woman 4 walk across first, 10 minutes haveelapsed when they get to the other side of the bridge. If Woman 4 thenreturns with the flashlight, a total of 20 minutes have passed and youhave failed the mission. What is the order required to get all womenacross in 17 minutes? Now, what's the other way?If you had an infinite supply of water and a 5 quart and 3 quart pail,how would you measure exactly 4 quarts?You have a bucket of jelly beans. Some are red, some are blue, and somegreen. With your eyes closed, pick out 2 of a like color. How many doyou have to grab to be sure you have 2 of the same?If you have two buckets, one with red paint and the other with bluepaint, and you take one cup from the blue bucket and poor it into theredbucket. Then you take one cup from the red bucket and poor it into theblue bucket. Which bucket has the highest ratio between red and blue?Prove it mathematically.AlgorithmsWhat's the difference between a linked list and an array?Implement a linked list. Why did you pick the method you did?Implement an algorithm to sort a linked list. Why did you pick themethod you did? Now do it in O(n) time.Describe advantages and disadvantages of the various stock sortingalgorithms.Implement an algorithm to reverse a linked list. Now do it withoutrecursion.Implement an algorithm to insert a node into a circular linked listwithout traversing it.Implement an algorithm to sort an array. Why did you pick the methodyou did?Implement an algorithm to do wild card string matching.Implement strstr() (or some other string library function).Reverse a string. Optimize for speed. Optimize for space.Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chrisis name My." Optimize for speed. Optimize for space.Find a substring. Optimize for speed. Optimize for space.Compare two strings using O(n) time with constant space.Suppose you have an array of 1001 integers. The integers are in randomorder, but you know each of the integers is between 1 and 1000(inclusive). In addition, each number appears only once in the array,exceptfor one number, which occurs twice. Assume that you can access eachelement of the array only once. Describe an algorithm to find therepeatednumber. If you used auxiliary storage in your algorithm, can you findanalgorithm that does not require it?Count the number of set bits in a number. Now optimize for speed. Nowoptimize for size.Multiple by 8 without using multiplication or addition. Now do the samewith 7.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).Write routines to read and write a bounded buffer.Write routines to manage a heap using an existing array.Implement an algorithm to take an array and return one with only uniqueelements in it.Implement an algorithm that takes two strings as input, and returns theintersection of the two, with each letter represented at most once. Nowspeed it up. Now test it.Implement an algorithm to print out all files below a given root node.Given that you are receiving samples from an instrument at a constantrate, and you have constant storage space, how would you design astorage algorithm that would allow me to get a representative readoutofdata, no matter when I looked at it? In other words, representative ofthebehavior of the system to date.How would you find a cycle in a linked list?Give me an algorithm to shuffle a deck of cards, given that the cardsare stored in an array of ints.The following asm block performs a common math function, what is it?
cwd xor ax, dxsub ax, dxImagine this scenario:I/O completion ports are communictaions ports which take handles tofiles, sockets, or any other I/O. When a Read or Write is submitted tothem, they cache the data (if necessary), and attempt to take therequestto completion. Upon error or completion, they call a user-suppliedfunction to let the users application know that that particular requesthascompleted. They work asynchronously, and can process an unlimitednumber of simultaneous requests.Design the implementation and thread models for I/O completion ports.Remember to take into account multi-processor machines.Write a function that takes in a string parameter and checks to seewhether or not it is an integer, and if it is then return the integervalue.Write a function to print all of the permutations of a string.Implement malloc.Write a function to print the Fibonacci numbers.Write a function to copy two strings, A and B. The last few bytes ofstring A overlap the first few bytes of string B.How would you write qsort?How would you print out the data in a binary tree, level by level,starting at the top?ApplicationsHow can computer technology be integrated in an elevator system for ahundred story office building? How do you optimize for availability?Howwould variation of traffic over a typical work week or floor or time ofday affect this?How would you implement copy-protection on a control which can beembedded in a document and duplicated readily via the Internet?Define a user interface for indenting selected text in a Word document.Consider selections ranging from a single sentence up throughselections of several pages. Consider selections not currently visibleor onlypartially visible. What are the states of the new UI controls? How willthe user know what the controls are for and when to use them?How would you redesign an ATM?Suppose we wanted to run a microwave oven from the computer. What kindof software would you write to do this?What is the difference between an Ethernet Address and an IP address?How would you design a coffee-machine for an automobile.If you could add any feature to Microsoft Word, what would it be?How would you go about building a keyboard for 1-handed users?How would you build an alarm clock for deaf people?ThinkersHow are M&Ms made?If you had a clock with lots of moving mechanical parts, you took itapart piece by piece without keeping track of the method of how it wasdisassembled, then you put it back together and discovered that 3important parts were not included; how would you go about reassemblingtheclock?If you had to learn a new computer language, how would you go aboutdoing it?You have been assigned to design Bill Gates bathroom. Naturally, costis not a consideration. You may not speak to Bill.What was the hardest question asked of you so far today?If MS told you we were willing to invest $5 million in a start up ofyour choice, what business would you start? Why?If you could gather all of the computer manufacturers in the worldtogether into one room and then tell them one thing that they would becompelled to do, what would it be?Explain a scenario for testing a salt shaker.If you are going to receive an award in 5 years, what is it for and whois the audience?How would you explain how to use Microsoft Excel to your grandma?Why is it that when you turn on the hot water in any hotel, forexample, the hot water comes pouring out almost instantaneously?Why do you want to work at Microsoft?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?Interviewer hands you a black pen and says nothing but "This pen isred."
2009-2016 downloadmela.com. All rights reserved.