Microsoft Interview Questions (Part – 1)

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.

The questions tend to follow some basic themes:

• Riddles

• Algorithms

• Applications

• Thinkers

• Riddles

• Why is a manhole cover round?
  

• How many cars are there in the USA? (A popular variant is “How many gas stations 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 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?
  

• 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?

• 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?

  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?

• 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?

• 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.’ 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? 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?
  

• 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?
  

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:

• 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 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?

• 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 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? 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

• What’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 the method you did? Now do it in O(n) time.
  

• Describe advantages and disadvantages of the various stock sorting algorithms.
  

• Implement an algorithm to reverse a linked list. Now do it without recursion.
  

• Implement an algorithm to insert a node into a circular linked list without traversing it.
  

• Implement an algorithm to sort an array. Why did you pick the method you 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 “Chris is 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 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?
  

• Count the number of set bits in a number. Now optimize for speed. Now optimize for size.
  

• Multiple by 8 without using multiplication or addition. Now do the same with 7.
  

• Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2

• 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 unique elements in it.
  

• 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.
  

• Implement an algorithm to print out all files below a given root node.
  

• 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.
  

• How would you find a cycle in a linked list?
  

• Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
  

• The following asm block performs a common math function, what is it?

MICROSOFT INTERVIEW

The Interview 

Interview is an opportunity for both the employer and the applicant to gather information. The

employer wants to know if you, the applicant, have the skills, knowledge, self-confidence, and

motivation necessary for the job. At this point you can be confident that the employer saw

something of interest in your resume. He or she also wants to determine whether or not you will fit

in with the organization’s current employees and philosophy. Similarly, you will want to evaluate the

position and the organization, and determine if they will fit into your career plans. The interview is a

two-way exchange of information. It is an opportunity for both parties to market themselves. The

employer is selling the organization to you, and you are marketing your skills, knowledge, and

personality to the employer.

Interview Preparation

Research is a critical part of preparing for an interview. If you haven’t done your homework, it is

going to be obvious. Spend time researching and thinking about yourself, the occupation, the

organization, and questions you might ask at the end of the interview.

Step 1: Know Yourself

The first step in preparing for an interview is to do a thorough   self-assessment so that you will

know what you have to offer an employer. It is very important to develop a complete inventory of

skills, experience, and personal attributes that you can use to market yourself to employers at any

time during the interview process. In developing this inventory, it is easiest to start with experience.

Once you have a detailed list of activities that you have done (past jobs, extra-curricular

involvements, volunteer work, school projects, etc.), it is fairly easy to identify your skills.

Simply go through the list, and for each item ask yourself “What could I have learned by doing

this?” “What skills did I develop?” “What issues/circumstances have I learned to deal with?” Keep

in mind that skills fall into two categories – technical and generic. Technical skills are the skills

required to do a specific job. For a laboratory assistant, technical skills might include knowledge of

sterilization procedures, slide preparation, and scientific report writing. For an outreach worker,

technical skills might include counselling skills, case management skills, or program design and

evaluation skills

Generic skills are those which are transferable to many work settings. Following is a list of the ten

most marketable skills. You will notice that they are all generic.

•  Analytical/Problem Solving

•  Flexibility/Versatility

•  Interpersonal

•  Oral/Written Communication

•  Organization/Planning

•  Time Management

•  Motivation

•  Leadership

•  Self-Starter/Initiative

•  Team Player

Often when people think of skills, they tend to think of those they have developed in the workplace.

However, skills are developed in a variety of settings. If you have ever researched and written a

paper for a course, you probably have written communication skills. Team sports or group projects

are a good way to develop the skills required of a team player and leader. Don’t overlook any

abilities you may have

When doing the research on yourself, identifying your experience and skills is important, but it is

not all that you need to know. Consider the answers to other questions such as:

•  How have I demonstrated the skills required in this position?

•  What are my strong points and weak points?

•  What are my short term and long term goals?

•  What can I offer this particular employer?

•  What kind of environment do I like? (i.e. How do I like to be supervised? Do I like a fast

pace?)

•  What do I like doing?

•  Apart from my skills and experience, what can I bring to this job?

Step 2: Know the Occupation

The second step in preparing for an interview is to research the occupation. This is necessary

because in order to present a convincing argument that you have the experience and skills

required for that occupation, you must first know what those requirements and duties are. With this

information uncovered, you can then match the skills you have (using the complete

skills/experience inventory you have just prepared) with the skills you know people in that

occupational field need. The resulting “shortlist” will be the one that you need to emphasize during

the interview.

It is also in your best interest to identify the approximate starting salary for that position, or those

similar. There are several ways to find out about an occupation:

•  Acquire a copy of the job description from the employer (Human

•  Resources/Personnel) or check with Student Employment Services. If you are responding

to an advertisement, this may also supply some details.

The Career Resource Centre has general information files on a variety of occupations. Make sure

you have read through the appropriate file and are updated on the occupation. If you belong to a

professional association related to the occupation, use its resources. These associations often

publish informative newsletters and sponsor seminars. It is also a good way to meet people

working in the field. Conduct information interviews with people working in the field. Read articles

about people in the occupation, and articles written by people in the occupation. Sources include

newspapers, magazines and the internet. Find out what the future trends are in the area. Is

technology changing the job?

Step 3: Know the Organization

The more you know about an organization, the better prepared you will be to discuss how you can

meet its needs. Some of the characteristics that you should know about an organization are:

•  Where is it located?

•  How big is it?

•  What are its products and who does it serve?

•  How is the organization structured?

•  What is its history?

•  Have there been any recent changes, new developments?

There are a number of ways in which you can access this information. Most medium- to large-sized

organizations publish information about themselves. You can access this a number of ways:

•  On campus at the Student Employment Services (company literature and business

directories) or at the Drake Centre Library

•  The Winnipeg Centennial Library has a business microfiche with information on over 5000

Canadian companies and business directories

•  Many companies have internet home pages which you can locate by searching by industry

and company name

•  Finally, you can visit or phone the organization and request some information on their

products, services or areas of research

If the organization is fairly small, or fairly new, there may not be much information published. In this

case, it will be necessary to do an information interview. Contact someone within the organization,

introduce yourself, explain that you are considering moving into the field, and ask if it would be

possible to meet with him/her to inquire about the company/organization and about what exactly

the position would involve.

Step 4: Prepare Questions

Having completed your background research, you are now ready to prepare questions to ask the

interviewer(s). Try to think of questions for which the answer was not readily available in company

literature. Intelligent well thought-out questions will demonstrate your genuine interest in the

position. Be careful how many questions you ask, however, as too many can imply you feel the interview was

not  successfully run. Pick your questions with care – this is your chance to gather information, so ask

about  what you really want to know. Avoid sounding critical by mentioning negative information you may

have  discovered. This is one of the most effective ways to compare different employers, so for issues of

particular importance to you (for example, whether they support staff upgrading), you should ask

the same

Questions of each employer

Some sample questions are:

•  What are the most significant factors affecting your business today? How have changes in

technology most affected your business today?

•  How has your business/industry been affected by the recession?

•  How has your company grown or changed in the last couple of years?

•  What future direction do you see the company taking?

•  Where is the greatest demand for your services or product?

•  Where is most of the pressure from increased business felt in this company?

•  Which department feels it the most?

•  How do you differ from your competitors?

•  How much responsibility will I be given in this position?

•  What do you like about working with this organization?

•  Can you tell me more about the training program?

•  Have any new product lines been introduced recently?

•  How much travel is normally expected?

•  What criteria will be used to evaluate my performance?

•  Will I work independently or as part of a team?

•  How did you advance to your position?

•  What are the career paths available in this organization?

•  When can I expect to hear from you regarding this position?

It is very important to ask the last question because employers want to hire individuals who are

interested in the position – and asking this question definitely helps to demonstrate interest on your

part. Exercise judgement when asking questions to an employer. When being interviewed by a

large company that has a high profile, one would not ask the question

MICROSOFT PLACEMENT PAPER – 5

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 Smiley 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.

Algorithms and Programming

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 ?

2. You’re given an array containing both positive and negative integers

and required to find the sub-array with the largest sum (O(N) a la

KBL). Write a routine in C for the above.

3. Given an array of size N in which every number is between 1 and N,

determine if there are any duplicates in it. You are allowed to destroy

the array if you like. [ I ended up giving about 4 or 5 different

solutions for this, each supposedly better than the others ].

4. Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without

making use of any floating point computations at all. [ This one had me

stuck for quite some time and I first gave a solution that did have

floating point computations ].

5. Given only putchar (no sprintf, itoa, etc.) write a routine putlong

that prints out an unsigned long in decimal. [ I gave the obvious

solution of taking % 10 and / 10, which gives us the decimal value in

reverse order. This requires an array since we need to print it out in

the

correct order. The interviewer wasn't too pleased and asked me to give

a

solution which didn't need the array ].

6. Give a one-line C expression to test whether a number is a power of

2. [No loops allowed - it's a simple test.]

7. Given an array of characters which form a sentence of words, give an

efficient algorithm to reverse the order of the words (not characters)

in it.

8. How many points are there on the globe where by walking one mile

south, one mile east and one mile north you reach the place where you

started.

9. Give a very good method to count the number of ones in a “n” (e.g.

32) bit number.

ANS. Given below are simple solutions, find a solution that does it in

log (n) steps.

MICROSOFT PAPER ON 26th JULY

Selection procedure and interview questions of Microsoft at Dhirubhai Ambani Institute of Information and Communication Technology (DA-IICT)

There were 4 rounds for selection procedure. First round was a written test, second round was group interview and 3rd and 4th rounds were technical interview. Each round had eliminations. Total 143 students were eligible for written test and 16 students were selected for the next round, ie. group interview. Only 8 students were able to go for 3rd round of technical interview. In 3rd round 4 more students were eliminated and remaining 4 students went for final round of technical interview. Only 1 student got an offer finally from Microsoft.

Following is the detail about each round.

Note: All examples which I will give here are just for your understanding. Interviewer was not giving any examples. Hardly 2 – 3 time interviewer gave examples.

Round 1: Written test 
Paper style: 3 subjective questions
Time limit: 1½ hour

Question 1: Finding output….
It was string cruncher program. First remove all repeated consecutive substring with length 1, then delete substring of length 2 and so on…
Example : string is “abcabeccced”

After removing repeated substring of length 1: “abcababceccced” –> “abcababceced” (2 ‘c’ are removed)
After removing repeated substring of length 2: “abcababceced” –> “abcabceced” (substring “ab” is removed)
and so on…

Question 2: Writing a program.
Definition: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible…among all triplets which triplet has minimum distance…Give only distance, but not triplet elements). Your program must be as much efficient as possible.

Question 3: Writing program.
Definition: You are given 2 integer numbers in linked list form. Add those 2 numbers.

Example: First number is 234 and second number is 35. So, you are provided with 2 linked lists 2->3->4 and 3->5. Your answer must be 2->6->9. (Make sure to take care of carry number). This example was given in paper.

Round 2: Group Interview
All candidates who had cleared the written test were called for group interview. Here we were given 3 problems one by one. Time limit was between 15 to 20 minutes. Once they gave problem definition we were supposed to think on it and discuss our ideas and logic about solving that problem with one of the representatives from Microsoft. Once that representative was convinced with our logic then we had to write code for that problem on paper.

Problem 1: You are given a string. Develop a function to remove duplicate characters from that string. String could be of any length. Your algorithm must be in space. If you wish you can use constant size extra space which is not dependent any how on string size. Your algorithm must be of complexity of O(n). Example: Given string is BANANAS. Output must be BANS. All repeated characters are removed.

Problem 2: You have a tree and address of its root. Write an efficient program to test whether a given tree is Binary search Tree or not. (Hint: In-order traversal of binary search tree is sorted in increasing order. Use this property to develop program)

Problem 3: You have 2 sorted lists and a function that merge that 2 lists such that output is again sorted and duplicates are removed. That means output is union of those 2 lists in sorted form.

Example: First list is 2->3->5->6->8 and second list is 4->5->6->7 and output of function is 2->3->4->5->6->7->8.

Develop test cases to test given function such that your test cases ensures that given function works for every situation. That is if inputs are valid then it gives proper output in any case or otherwise it shows error message.

Round 3: First Technical Interview
All those who had cleared group interview were called for first technical interview. They were taking minimum 2 hours for first interview. Some of us also faced interview for 3 or more hours.

Round 4: Second Technical Interview
All those who had cleared first technical interview were called for second interview. This was last round of interview. They took 1½ to 2 hours for this second interview.

I don’t remember all the questions which were asked to me in both interviews. But still some of the questions which I can remember (almost 80 to 90% questions) are listed below.

In both interview they ask questions from C/C++, java, OS, Data structure and algorithms, Microprocessors and compiler constructions. With this, they also asked me to develop more than 6 to 8 programs. You can develop all programs in 5 to 7 minutes. But after writing program they asked to find its complexity and try to reduce the complexity and write the program again. In this way it took almost 15 to 20 min for each program. Some took less than 15 minutes also.

Some of the interview questions are as follows:

You are given a linked list and block size k. Reverse block of size k from list.

For example you are given linked list of 1000 nodes and block size is 5 then instead of reversing whole list, reverse first 5 elements, then 6 to 10 elements, then 11 to 15 elements, and so on…You have singly linked list and your algorithm which you will implement must be in space, that is no extra space is allowed.

You are given a tree and any 2 nodes of that tree. Find common parent of both nodes. Develop as much efficient program as you can.

In unix there is a command called “tail”. Implement that command in C.

Some questions about race condition (OS)

Questions related to semaphores.

Questions related to mutex. Applications of mutex. How to implement mutex in OS?

Questions about Critical region (OS).

How to ensure that race condition doesn’t occur. Give your view as you are OS designer.

How to ensure that each process lock the critical region before they enter in it. As OS designer How will you force the process to do this?

Questions on IPC

Questions on Shared memory and Message passing mechanism.

Difference between system call and API call

How system call works? What happens when system call is invoked?

Different types of system calls?

Some questions from microprocessor. About Interrupts

Types of Interrupts. What happened when interrupt is called?

You are given a hard copy of a program which contains some errors. Your job is to find all types of errors from it. And discuss why is it an error. Write correct program for the same.

You are given a linked list and a number n. You also have a function to delete all nodes from that list which are at position which multiple of n in the list.

Example: if number is 3 then delete 3rd, 6th, 9th ,…nodes form the list. Develop a program that tests whether given function works properly or not. (In short they are asking me to develop general program for all test cases. By running that program all tests can be performed.)

Questions on java. Exception handling

Need of catch and finally block in java exception handling..

How will you create your own exception.. Explain with example.

Some questions on compiler construction. What is parser? What is input to the parser and what is output of parser? Difference between top down and bottom up parser.

F(1) = 1.
F(2n) = F (n) and F(2n+1) = F(n) + F(n+1).
Develop recursive program.

You are given a string which contains some special characters. You also have set of special characters. You are given other string (call it as pattern string). Your job is to write a program to replace each special characters in given string by pattern string. You are not allowed to create new resulting string. You need to allocate some new memory to given existing string but constraint is you can only allocate memory one time. Allocate memory exactly what you need not more not less.

Assume that your friend is writing a book . He gives you a file that contains that book. Your job is to develop an algorithm for indexing of that book. In every book there is one index at end which contains some words which are not there in normal vocabulary dictionary. It also contains page number for reference. You can use any data structure you want. You need to justify why you have used that data structure and also need to justify your logic.

Question from my B.E. final semester project. Asked me to explain whole project.

Question from everything written on my resume.

Question from my every project I did. They asked me to explain each project and then how to do some modification? That modification will be suggested by interviewer himself.

My experience in Teaching assistantship.

They had my written test answer sheet. They opened it and asked me to explain why I gave that output or why I implement that logic. How did I arrive to that solution which I had written in answer sheet.

In written test, for second question I had implement a program which was not much efficient. During interview they ask me to optimize my program. They also gave hint to optimize it.

During group interview, in second problem I was only able to discuss logic I was unable to develop program in given time limit. Interviewer knew this. She asked me to develop that program during interview.

Which is your favorite software tool? If you are allowed to add any feature in it which feature you will add?

Which is your favorite subject? Some questions from that subject.

Something about yourself , your hobbies, interests, strengths and weakness.

I was unable to clear 4th round that is second technical interview. I hope this will help you in your preparation for Microsoft.

Thanks and regards,
Shah Sapan Pramodkumar

MICROSOFT PLACEMENT PAPER

MICROSOFT PLACEMENT PAPER

Riddles

•  Why is a manhole cover round?

•  How many cars are there in the USA? (A popular variant is “How many gas stations 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 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?

•  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?

•  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?

•  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?

•  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?

•  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.’

•  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?

•  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?

•  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?

•  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.

•  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?

•  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 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?

•  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

•  What’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 the method you did? Now do

it in O(n) time.

•  Describe advantages and disadvantages of the various stock sorting algorithms.

•  Implement an algorithm to reverse a linked list. Now do it without recursion.

•  Implement an algorithm to insert a node into a circular linked list without traversing it.

•  Implement an algorithm to sort an array. Why did you pick the method you 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.

•  Reserve the words in a sentence, i.e. “My name is Chris” becomes “Chris is 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 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?

•  Count the number of set bits in a number. Now optimize for speed. Now optimize for size.

•  Multiple by 8 without using multiplication or addition. Now do the same with 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 unique elements in it.

•  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.

•  Implement an algorithm to print out all files below a given root node.

•  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.

•  How would you find a cycle in a linked list?

•  Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array

of ints.

•  The following asm block performs a common math function, what is it?

•   cwd xor ax, dx sub ax,

dx

•  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.

•  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.

•  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 of string 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?

Applications

•  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?

•  How would you implement copy-protection on a control which can be embedded 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 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?

•  How would you redesign an ATM?

•  Suppose we wanted to run a microwave oven from the computer. What kind of 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?

Thinkers

•  How are M&Ms made?

•  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?

•  If you had to learn a new computer language, how would you go about doing it?

•  You have been assigned to design Bill Gates bathroom. Naturally, cost is 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 of your choice, what

business would you start? Why?

•  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?

•  Explain a scenario for testing a salt shaker.

•  If you are going to receive an award in 5 years, what is it for and who is 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, for example, 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?

MICROSOFT Placement PAPER ON 26th JULY

Selection procedure and interview questions of Microsoft at Dhirubhai Ambani Institute of Information and Communication Technology (DA-IICT)

There were 4 rounds for selection procedure. First round was a written test, second round was group interview and 3rd and 4th rounds were technical interview. Each round had eliminations. Total 143 students were eligible for written test and 16 students were selected for the next round, ie. group interview. Only 8 students were able to go for 3rd round of technical interview. In 3rd round 4 more students were eliminated and remaining 4 students went for final round of technical interview. Only 1 student got an offer finally from Microsoft.

Following is the detail about each round.

Note: All examples which I will give here are just for your understanding. Interviewer was not giving any examples. Hardly 2 – 3 time interviewer gave examples.

Round 1: Written test
Paper style: 3 subjective questions
Time limit: 1½ hour

Question 1: Finding output….
It was string cruncher program. First remove all repeated consecutive substring with length 1, then delete substring of length 2 and so on…
Example : string is “abcabeccced”

After removing repeated substring of length 1: “abcababceccced” –> “abcababceced” (2 ‘c’ are removed)
After removing repeated substring of length 2: “abcababceced” –> “abcabceced” (substring “ab” is removed)
and so on…

Question 2: Writing a program.
Definition: You are given 3 integer arrays A, B and C of length n1, n2 and n3 respectively. All arrays are sorted. We define triplet of these 3 arrays as (x,y,z) where x is any integer from A, y from B and z from C. We define distance of triplet as maximum difference among triplet elements, i.e. Maximum of x – y, y – z or z – x. Write a program to find minimum triplet distance. (means there are n1*n2*n3 number of possible triplets are possible…among all triplets which triplet has minimum distance…Give only distance, but not triplet elements). Your program must be as much efficient as possible.

Question 3: Writing program.
Definition: You are given 2 integer numbers in linked list form. Add those 2 numbers.

Example: First number is 234 and second number is 35. So, you are provided with 2 linked lists 2->3->4 and 3->5. Your answer must be 2->6->9. (Make sure to take care of carry number). This example was given in paper.

Round 2: Group Interview
All candidates who had cleared the written test were called for group interview. Here we were given 3 problems one by one. Time limit was between 15 to 20 minutes. Once they gave problem definition we were supposed to think on it and discuss our ideas and logic about solving that problem with one of the representatives from Microsoft. Once that representative was convinced with our logic then we had to write code for that problem on paper.

Problem 1: You are given a string. Develop a function to remove duplicate characters from that string. String could be of any length. Your algorithm must be in space. If you wish you can use constant size extra space which is not dependent any how on string size. Your algorithm must be of complexity of O(n). Example: Given string is BANANAS. Output must be BANS. All repeated characters are removed.

Problem 2: You have a tree and address of its root. Write an efficient program to test whether a given tree is Binary search Tree or not. (Hint: In-order traversal of binary search tree is sorted in increasing order. Use this property to develop program)

Problem 3: You have 2 sorted lists and a function that merge that 2 lists such that output is again sorted and duplicates are removed. That means output is union of those 2 lists in sorted form.

Example: First list is 2->3->5->6->8 and second list is 4->5->6->7 and output of function is 2->3->4->5->6->7->8.

Develop test cases to test given function such that your test cases ensures that given function works for every situation. That is if inputs are valid then it gives proper output in any case or otherwise it shows error message.

Round 3: First Technical Interview
All those who had cleared group interview were called for first technical interview. They were taking minimum 2 hours for first interview. Some of us also faced interview for 3 or more hours.

Round 4: Second Technical Interview
All those who had cleared first technical interview were called for second interview. This was last round of interview. They took 1½ to 2 hours for this second interview.

I don’t remember all the questions which were asked to me in both interviews. But still some of the questions which I can remember (almost 80 to 90% questions) are listed below.

In both interview they ask questions from C/C++, java, OS, Data structure and algorithms, Microprocessors and compiler constructions. With this, they also asked me to develop more than 6 to 8 programs. You can develop all programs in 5 to 7 minutes. But after writing program they asked to find its complexity and try to reduce the complexity and write the program again. In this way it took almost 15 to 20 min for each program. Some took less than 15 minutes also.

Some of the interview questions are as follows:

You are given a linked list and block size k. Reverse block of size k from list.

For example you are given linked list of 1000 nodes and block size is 5 then instead of reversing whole list, reverse first 5 elements, then 6 to 10 elements, then 11 to 15 elements, and so on…You have singly linked list and your algorithm which you will implement must be in space, that is no extra space is allowed.

You are given a tree and any 2 nodes of that tree. Find common parent of both nodes. Develop as much efficient program as you can.

In unix there is a command called “tail”. Implement that command in C.

Some questions about race condition (OS)

Questions related to semaphores.

Questions related to mutex. Applications of mutex. How to implement mutex in OS?

Questions about Critical region (OS).

How to ensure that race condition doesn’t occur. Give your view as you are OS designer.

How to ensure that each process lock the critical region before they enter in it. As OS designer How will you force the process to do this?

Questions on IPC

Questions on Shared memory and Message passing mechanism.

Difference between system call and API call

How system call works? What happens when system call is invoked?

Different types of system calls?

Some questions from microprocessor. About Interrupts

Types of Interrupts. What happened when interrupt is called?

You are given a hard copy of a program which contains some errors. Your job is to find all types of errors from it. And discuss why is it an error. Write correct program for the same.

You are given a linked list and a number n. You also have a function to delete all nodes from that list which are at position which multiple of n in the list.

Example: if number is 3 then delete 3rd, 6th, 9th ,…nodes form the list. Develop a program that tests whether given function works properly or not. (In short they are asking me to develop general program for all test cases. By running that program all tests can be performed.)

Questions on java. Exception handling

Need of catch and finally block in java exception handling..

How will you create your own exception.. Explain with example.

Some questions on compiler construction. What is parser? What is input to the parser and what is output of parser? Difference between top down and bottom up parser.

F(1) = 1.
F(2n) = F (n) and F(2n+1) = F(n) + F(n+1).
Develop recursive program.

You are given a string which contains some special characters. You also have set of special characters. You are given other string (call it as pattern string). Your job is to write a program to replace each special characters in given string by pattern string. You are not allowed to create new resulting string. You need to allocate some new memory to given existing string but constraint is you can only allocate memory one time. Allocate memory exactly what you need not more not less.

Assume that your friend is writing a book . He gives you a file that contains that book. Your job is to develop an algorithm for indexing of that book. In every book there is one index at end which contains some words which are not there in normal vocabulary dictionary. It also contains page number for reference. You can use any data structure you want. You need to justify why you have used that data structure and also need to justify your logic.

Question from my B.E. final semester project. Asked me to explain whole project.

Question from everything written on my resume.

Question from my every project I did. They asked me to explain each project and then how to do some modification? That modification will be suggested by interviewer himself.

My experience in Teaching assistantship.

They had my written test answer sheet. They opened it and asked me to explain why I gave that output or why I implement that logic. How did I arrive to that solution which I had written in answer sheet.

In written test, for second question I had implement a program which was not much efficient. During interview they ask me to optimize my program. They also gave hint to optimize it.

During group interview, in second problem I was only able to discuss logic I was unable to develop program in given time limit. Interviewer knew this. She asked me to develop that program during interview.

Which is your favorite software tool? If you are allowed to add any feature in it which feature you will add?

Which is your favorite subject? Some questions from that subject.

Something about yourself , your hobbies, interests, strengths and weakness.

I was unable to clear 4th round that is second technical interview. I hope this will help you in your preparation for Microsoft.

Thanks and regards,
Shah Sapan Pramodkumar

Next Page »