Microsoft questions at interview

Microsoft interview at our campus(rvce,bangalore) was held today. Me being a comp sci. student dreamt of joining this company. It happened that i got thru written rounds but not the tech interviews.

Well coming to Written Questions...
There were 5 coding questions to be answered in 75 mins..(pretty easy too coz i could solve nearly all)

1. There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w lists l1-l2. lists are in orders of descending powers.
constraints:
no extra space i.e., O(1) space
O(m+n) time complexity. m and n and nodes in the lists.
struct node{
int coeff;
int power;
node *next;
};

2. write atoi function with all test cases.

3. output of recursive procedure (anyone could solve it using state space tree)

4. find bugs in the xstrrev function.
char *xstrrev (const char *s1)
{
char s2[20];
for (int i=strlen(s1)-1;i>=0;++i)
s2[strlen(s1)-i-1]=s1[.i];
//here was one bug...the code did not set last char as '\0'.
return s2;//one more bug here..returning local array. we need to allocate in heap and
//make it static
}

5. Design a soln , expalin the DataStructure used and write efficiency class for finding out the top 100 frequently used words in the editor. The words are updated in the DS used for every added or deleted words and the functions below are called for every updated word.
write the pseudocode for
onWordAdd (const char *word);
onWordDel (const char *word);

2nd round Question
Well, the 2nd round consisted of 8 of them(me too ) and we were given to solve a maze problem in 20 mins

There exists 2D char array.. we need to find out whether a given string("microsoft") exists in the given matrix. the string can be vertical or horizontal..but NOT diagonal. it can also be in this form..(like the snake in the cell games )
m i
. . c . o f t
. . r o s

(i applied dfs-logic(recusrion and visited matrix) but had lot of bugs in it someone else had done it more accurate.. they are strict in terms of time to solve the problem coz that is what they look at)

Responses:
guys i think this solution is ok for 1st...

L1 - m , L2 - n

any polynomial can be reprsented using horner rule as

P(n) = b + x(a1 +x(a2 + x)....)



Let

L1_sum=0;
L1_sum=0;

while (m >= 0) ------------ O(m)
{
Read L1;
L1_sum = L1- >coeff + L1_sum * x;
L1=L1->next;
}

while (n >= 0) --------- O(n)
{
Read L2;
L2_sum = L2- >coeff + L2_sum * x;
L2=L2->next;
}

differenece = mod(L1_sum - L2_sum)

@wrath child

for (int i=strlen(s1)-1;i>=0;++i) // ++i or i--?

ya.. it was --i

Three types of allocation/deallocation strategies
1. Global and static variables (BSS) = program startup/termination
2. Local variables (stack) = function entry/return
3. Dynamic memory (heap) = malloc()/free()

Question 1 was not about evaluating the polynomial.

It was to form a diff of polynomial expressions.

l1 head->[1,2]->[-1,0]->null
l2 head->[2,4]->[2,2]->[1,1]->[1,0]->null

Output should be list like this..

output head->[-2,4]->[-1,2]->[-1,1]->[-2,0]->null

Q1
/*
* Code to subtract polynomial represented by lists
*/



void reverse(node ** head)
{
node * first = *head;
node * temp = NULL;
if (*head == NULL)
{
return;
}
while (first->next != NULL)
{
temp = first->next;
first->next = first->next->next;
temp->next = *head;
*head = temp;
}
return;
}
/*
* Evaluate poly1 - poly2
*/
void Subtract(node * poly1, node * poly2, node ** result)
{
node * prev = NULL;
node * temp1;
node * temp2;
node * sub = malloc(sizeof(node));
*result = sub;
/*
* If list 1 has max power as m
* and list 2 has max power and n
* then both cannot be processed directly
* so we shall reverse them first to process them
*/
reverse(&poly1);
reverse(&poly2);
temp1 = poly1;
temp2 = poly2;
while ((temp1 !=NULL) || (temp2 !=NULL))
{
if ((temp1 !=NULL) && (temp2 !=NULL))
{
if (temp1->power == temp2->power)
{
sub->value = temp1->coeff - temp2->coeff;
sub->power = temp1->power;
}
else if (temp1->power > temp2->power)
{
sub->value = - temp2->coeff;
sub->power = temp2->power;
}
else if (temp1->power <>power)
{
sub->value = temp1->coeff;
sub->power = temp1->power;
}

sub->next =malloc(sizeof(node));
prev = sub;
sub = sub->next;
temp1 = temp1->next;
temp2 = temp2->next;
}
else if (temp1 == NULL)
{
sub->value = - temp2->coeff;
sub->power = temp2->power;
sub->next =malloc(sizeof(node));
prev = sub;
sub = sub->next;
temp2 = temp2->next;
}
else if (temp1 == NULL)
{
sub->value = temp1->coeff;
sub->power = temp1->power;
sub->next =malloc(sizeof(node));
prev = sub;
sub = sub->next;
temp1 = temp1->next;
}
}
free(sub);
prev->next = NULL;
reverse(&poly1);
reverse(&poly2);
reverse(result);
}


for the 2nd round ques.......
here is the c code.....output will display message "string found" equal to the
number of patterns of the string("microsoft") present in the 2d array..

e.g in my code there are 4 such patterns.



#include
#include
#include

char a[10][10]={
"maaaaaaaa",
"iaataaaaa",
"caafaaaaa",
"rosoftaaa",
"oaaaaaaaa",
"softaaaaa",
"oaaaaaaaa",
"faaaaaaaa",
"taaaaaaaa",
"aaaaaaaaa"
};
int check(int i,int j,char str)
{
if(i>=0&&i<10&&j>=0&&j<10) l="="8)" l="="8)" l="="8)" l="="8)" i="0;i<10;i++)" j="0;j<10;j++)">For every add,first check that whether this word already exist in stack1 and while checking pop this element and push in stack2,if it exist then take it and pop elements from stack2 and push to stack1 and at top if stack1 put the existing element .
->If it is not existed then put this word in stack1 top.
->while adding check if the stack size in less than 100,if not then delete the bottom element of stack1 and add new at top of stack1.

->For elery del,search it like we did in add,and remove it from stack1.