Hello, I am the originator of the thread and have just completed
my interview session at Microsoft. The Microserfs were apparently
impressed with me and called me to offer me a job at Microsoft
the very next day, Friday.
WHAT I DID?
-----------
I had interviewed with two product groups--Microsoft Excel and
Microsoft Project for several hours each.
INTERVIEW QUESTIONS
===================
A number of you asked me to mail you replies. Also, some other people
offered my sample questions directly.
====================================================================
Questions That I Received at Microsoft
--------------------------------------
The solutions are in C++, so they may not compile under C.
** Reverse a link list
Easy. Took me less than a minute.
This must be a common problem. Since many people mentioned
this as a typical Microsoft problem.
Node *reverse(Node *list)
{
Node *newlist=0;
while(list)
{
Node *tmp= list;
list = list->next;
tmp->next = newlist;
newlist = tmp;
}
return newlist;
}
** Count the number of bits in an int
This involved a classic trick. I generated to solutions. A
constant time solution using a small table and a bit-hack
solution.
int bitcount(int v)
{
for(int count=0; v; count++, v &= ~(v-1));
return count;
}
int table[] = {0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 };
#define bc(x) table[(x)&0xf ] // maps nibbles to number of bits
int bitcount(int v)
{
// assume 16 bit int
return bc(x) + bc(x>>4) + bc(x>>8) + bc(x>>12);
}
** Remove all elements with a given value from a list
The interviewer was actually impressed that I used
pointers to pointers, that I coded it in a couple
minutes, and that my code was compact and elegant.
Most interviewers don't use pointers to pointers.
void remove(Node **node, int v)
{
while (*node) {
if ((*node)->value = v) {
Node *tmp = *node;
*node = (*node)->next;
free(tmp);
} else node = &(*node)->next;
}
}
** Insert a number into a linked list in ascending order
The interviewer was again impressed with my speed. Before I had
written my solution, I had to erase a previous attempt at the same
problem on the board by the interviewee before me. His attempt
was 3 times larger than my solution and contained unnecessary variables
like backptr and did not handle special cases. My code was complete
from the start.
void insert(Node **node, int v)
{
Node *tmp = (Node *)malloc(sizeof(Node));
while(*node && (*node)->value>v) node = &(*node)->next;
tmp->value = v;
tmp->next = *node;
*node = tmp;
}
** Write a binary search algorithm.
In a few minutes, I generated this solution. The interviewer was
astonished and said that this problem usually takes the entire
hour for a typical interviewee to answer correctly. In addition,
his/her code is usually incorrect, incomplete, or non-terminating
for some inputs.
int binsearch(int t[], int v, int imin, int imax)
{
while (imax>=imin)
{
int imid = (max+min)/2;
if (t[imid]==v) return imid;
if (t[imid]>v) imax=imid-1; else imin=imid+1;
}
return -1;
}
** The Macintosh is missing SetPixel. Rewrite it.
Trivial.
void SetPixel(char *base, int rowbytes, int x, int y)
{
*(base + rowbytes*y + (x>>3)) |= 1 << (7-(x&7));
}
After I solved it in less than a minute, I was told to
write an SetRange that would set whole bytes at a time not bits.
This took me five minutes.
void SetRange(char *base, int rowbytes, int x1, int x2, int y)
{
char *line = base + rowbytes*y;
char *b1 = line + (x1>>3);
char *b2 = line + (x2>>3);
// unsigned is used to force logical shifts, not arithmetic shifts
int mask1 = (unsigned)0xff >> (7-(x1&7));
int mask2 = (unsigned)0xff << (7-(x2&7));
for (char *i = b1+1; i<b2; i++) *i++ |= 0xff;
if (b1==b2) *b1 |= mask1 & mask2;
else { *b1 |= mask1; *b2 |= mask2; }
}
** Rewrite an infix expression in postfix and prefix.
** Benefits of using a hash table
** Suppose that are two jars of liquid, one containing blue liquid
and the other containing red liquid. If you remove a unit of liquid
from the blue jar and place it into the red jar. The remove a unit
from a now impure red jar and place it into the blue jar. Which
jar has more of the liquid of its own color.
Answer: They are both equal. If the jars can hold K units and the
blue jar contains b units of blue, then it contains K-b units of red.
So, the red must contain K-(K-b) units of red or b units of red. QED.
There were many other questions that I cannot remember of hand.
===================================================================
I decided to see how smart the Microsoft employees were, so I asked
them a random question on my mind. How to swap variables using only
one statement and no additional variables. (2 solutions) He was
able to guess that it was an exclusive or trick, but could not
derive it.
SOLUTION 1: a ^= b ^= a ^= b;
SOLUTION 2: a ^= b, b ^= a, a ^= b;
======================================================================