Microsoft Interview Questions & Answers

I recently visited Microsoft's Silicon Valley campus and interviewed with the Hotmail group. If you've never had a Microsoft interview, realize that they are very different than the standard interview. You won't be asked any of those questions like, "What is your greatest weakness," or, "Where do you want to be in five years?" Rather, a Microsoft interview typically contains a number of brain teasers and coding questions. In fact, you can read interview questions from my internship interviews.

Here are the questions I was asked, accompanied with the answers right below the question! So, once you reach the end of the question, don't read any further unless you want to immediately know the answer! Anyway, here goes:

Question: How could you determine if a linked list contains a cycle in it, and, at what node the cycle starts?

Answer: 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;
}

Then, to determine whether or not a cycle existed, loop through each node. After visiting a node, set bVisited to true. When you first visit a node, check to see if the node has already been visited (i.e., test bVisited == true). If it has, you've hit the start of the cycle!

bool bCycle = false;
pCurrent = pHead;
while (pCurrent && !pCycle)
{
 if (pCurrent->bVisited == true)
   // cycle!
   pCycle = true;
 else
 {
   pCurrent->bVisited = true;
   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->next;
    p2 = p2->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.

Thanks George!

Question: How would you reverse a doubly-linked list?

Read more: 4 Guys From Rolla

Posted via email from jasper22's posterous