Microsoft Corporation Interview Preparation Guide

# Mike has $20 more than Todd. How much does each have given that combined they have $21 between them. You can't use fractions in the answer.(Hint: This is a trick question, pay close attention to the condition)
# There are four dogs, each at the counter of a large square. Each of the dogs begins chasing the dog clockwise from it. All of the dogs run at the same speed. All continously adjust their direction so that they are always heading straight towards their clockwise neighbor. How long does it take for the dogs to catch each other? Where does this happen? (Hint: Dog's are moving in a symmetrical fashion, not along the edges of the square).
# If you had an infinite supply of water and a 5 quart and 3 quart pail, how would you measure exactly 4 quarts?
# If you are on a boat and you throw out a suitcase, will the level of water increase?
# On an average, how many times would you have to open the Seattle phone book to find a specific name?
# There are 3 ants at 3 corners of a triangle, they randomly start moving towards another corner. What is the probability that they don't collide?
# If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands? ( The answer to this is not zero!)
# What new feature would you add to MSWORD if you were hired?
# Why did you pick the school you graduated from?
# Why do you want to work for Microsoft?
# How many Gas stations are there in the US?
# How would you weigh a plane without using scales?
# How would you move Mt. Everest?
# Two MIT math graduates bump into each other at Fairway on the upper west side. They hadn't seen each other in over 20 years.
The first grad says to the second: "how have you been?"
Second: "Great! I got married and I have three daughters now"
First: "Really? how old are they?"
Second: "Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there.."
First: "Right, ok.. oh wait.. hmmmm.., I still don't know"
second: "Oh sorry, the oldest one just started to play the piano"
First: "Wonderful! my oldest is the same age!"
Problem: How old are the daughters?
# Why are beer cans tapered at the top and bottom?
# Why is it that hot water in a hotel comes out instantly but at home it takes time?

This problem isn't too hard. You just need to start at the head of the list, and iterate to the end. At each node, swap the values of pNext and pPrev. Finally, set pHead to the last node in the list.

Node * pCurrent = pHead, *pTemp;
while (pCurrent)
{ pTemp = pCurrent-gt;pNext;
pCurrent-gt;pNext = pCurrent->pPrev;
pCurrent-gt;pPrev = temp;

pHead = pCurrent;

pCurrent = temp;
}

There are a number of approaches. The approach I shared is in time N (where N is the number of nodes in your linked list). Assume that the node definition contains a boolean flag, bVisited.
struct Node
{
...
bool bVisited;
};

Then, to determine whether a node has a loop, you could first set this flag to false for all of the nodes:
// Detect cycle
// Note: pHead points to the head of the list (assume already exists)
Node *pCurrent = pHead;
while (pCurrent)
{
pCurrent->bVisited = false;
pCurrent = pCurrent->pNext;
}

A much better approach was submitted by 4Guys visitor George R., a Microsoft interviewer/employee. He recommended using the following technique, which is in time O(N) and space O(1).

Use two pointers.

// error checking and checking for NULL at end of list omitted
p1 = p2 = head;

do {
p1 = p1-gt;next;
p2 = p2-gt;next->next;
} while (p1 != p2);

p2 is moving through the list twice as fast as p1. If the list is circular, (i.e. a cycle exists) it will eventually get around to that sluggard, p1.

Given the following prototype:
int compact(int * p, int size);

write a function that will take a sorted array, possibly with duplicates, and compact the array, returning the new length of the array. That is, if p points to an array containing: 1, 3, 7, 7, 8, 9, 9, 9, 10, when the function returns, the contents of p should be: 1, 3, 7, 8, 9, 10, with a length of 5 returned.


A single loop will accomplish this.

int compact(int * p, int size)
{
int current, insert = 1;
for (current=1; current < size; current++)
if (p[current] != p[insert-1])
{
p[insert] = p[current];
current++;
insert++;
} else
current++;
}

Assume you have an array that contains a number of strings (perhaps char * a[100]). Each string is a word from the dictionary. Your task, described in high-level terms, is to devise a way to determine and display all of the anagrams within the array (two words are anagrams if they contain the same characters; for example, tales and slate are anagrams.)


Begin by sorting each element in the array in alphabetical order. So, if one element of your array was slate, it would be rearranged to form aelst (use some mechanism to know that the particular instance of aelst maps to slate). At this point, you slate and tales would be identical: aelst.
Next, sort the entire array of these modified dictionary words. Now, all of the anagrams are grouped together. Finally, step through the array and display duplicate terms, mapping the sorted letters (aelst) back to the word (slate or tales).

You are given a scale which you are to use to measure eight balls. Seven of these balls have the same weight: the eigth ball is heavier than the rest. The scale does not indicate the weight of a particular object; it is a scale which tells you which of the two sides being weighed is heavier (like the scale that lady of justice statue holds up). So, for example you could place one ball on each end of the scale. If ball one was heavier than ball two, it would tip in ball one's direction; if ball two were heavier, it would tip io ball three's direction; if the balls were of equal weight, the scale would not tip at all. What is the minimum number of weighs you could perform to find the heaviest of the eight balls?
Imagine, now, that you have seven balls of unknown weight, given that six are of the same weight, and the seventh is heavier than the rest. Using the same scale as described above, what is the minimum number of weights you could perform to find the heaviest of the seven balls?

Imagine that you have 26 constants, labelled A through Z. Each constant is assigned a value in the following way: A = 1; the rest of the values equal their position in the alphabet (B corresponds to the second position so it equals 2, C = 3, etc.) raised to the power of the preceeding constant value. So, B = 2 ^ (A's value), or B = 2^1 = 2. C = 3^2 = 9. D = 4^9, etc., etc. Find the exact numerical value to the following equation:

(X - A) * (X - B) * (X - C) * ... * (X - Y) * (X - Z)
Write C code to implement atoi

And fimally, the hum-dinger: There are four people who need to cross a bridge at night. The bridge is only wide enough for two people to cross at once. There is only one flashlight for the entire group. When two people cross, they must cross at the slower member's speed. All four people must cross the bridge in 17 minutes, since the bridge will collapse in exactly that amount of time. Here are the times each member takes to cross the bridge:

Person A: 1 minute
Person B: 2 minutes
Person C: 5 minutes
Person D: 10 minutes

So, if Person A and C crossed the bridge initally, 5 minutes would elapse, because Person C takes 5 minutes to cross. Then, Person A would have to come back to the other side of the bridge, taking another minue, or six minutes total. Now, if Person A and D crossed the bridge next, it would take them 10 minutes, totalling to 16 minutes. If A came back, it would take yet another minute, totally 17... the bridge would collapse with A and B on the wrong side. How can all four people get across the bridge within 17 minutes? Note: there is no trick-answer to this problem. You can't do tricky stuff like throwing the flashlight back from one end of the bridge to the other. This problem can be solved!

According to the economic census for retail trade (census.gov) in 1997 there were only 126,889 gas stations (64% of them having convienence stores).
I simply took the 1997 and 2002 census data and continued the trend based on the limited data:

1997 - 126,889 gas stations. 81,684 (64%) with convenience stores.
2002 - 121,446 gas stations. 93,691 (77%) with convenience stores.
*2007 - 116,223 gas stations. 104,600 (90%) with convenience stores.
*2008 - 115,223 gas stations. 106,696 (92.6%) with convenience stores.

* Estimated guess based on 1997-2002 trends.

As we can see in the name itsef,Everest(which means Ever-
Rest)i.e always at rest.Therefore to make it move we can
just add the prefix N to it. Thus making it Mt.Neverest
(Never-rest).

I think 22 times. (times given are approx) 1:05a 2:10a 3:15a 4:20a
5:25a 6:30a 7:35a 8:40a 9:45a 10:50a 12:midnight etc. Both
of the "eleven o'clock" overlaps never occur; they turn
into the "midnight" and "noon" overlaps. The hour hand
is "running away" from the minute hand.

To create a virtual directory by using IIS Manager:
1.
In IIS Manager, expand the local computer, expand the Web Sites or FTP Sites folder, right-click the site or folder within which you want to create the virtual directory, point to New, and then click Virtual Directory. The Virtual Directory Creation Wizard appears.

2.
Click Next.

3.
In the Alias box, type a name for the virtual directory. (Choose a short name that is easy to type because the user types this name.)

4.
Click Next.

5.
In the Path box, type or browse to the physical directory in which the virtual directory resides, and then click Next.

6.
Under Allow the following permissions, select the check boxes for the access permissions you want to assign to your users, and then click Next.

Important

For security reasons, when selecting access permissions, consider allowing only the default Read permission. By restricting permissions in this way, you can help avoid attacks against your Web site by malicious users. For more information about setting access permissions, see Securing Virtual Directories and Access Control in Help and Support Center for Windows Server 2003.

7.
Click Finish. The virtual directory is created below the currently selected folder level.