Sunday, January 13, 2008

Microsoft Interview

I had an interview for internship at Microsoft. I was interviewed by SQL Server Analysis Services and SQL Server Reporting Services (I got offer from both :) ).

I was briefed by my recruitment coordinator at building 19. I had my interviews in building 34 and 35.

My interview questions were pretty easy. Here are some of them:
1. Write a program to create a balanced binary tree from a sorted array of integer.
>> Find the middle element. Make it root. recursively call the function for left and right subarray with root->left and root->right respectively.

2. Write a program to find angle between clock's minute and hour hand
>> assert(h >= 0 && m >=0)
return ( abs( 0.5*((h%12)*60 + m%60) - 6*(m%60)));

3. Consider there are 2 types of characters:
1byte character - has value less than 128
2 byte character - whose first byte has value >= 128
Given a random pointer in a byte array find the previous character

I was asked to solve the simpler version of the problem: i.e I was given the pointer to beginning of array.
>> Start from beginning of array till pointer (also keep track of prev character), if value <> 1 byte character. Goto next byte.
If value >= 128, => 2 byte character, move 2 bytes.

Lets assume if I was not given the begin pointer:
>> Assuming turing tape: the problem has atleast 1 non halting solution. Consider, tape filled with 128. :)

4. Given a string, reverse first n characters in each word of the string.
Eg: if string is "abcd ef"
and n =2 => o/p: "badc fe"
and if n =3 => o/p: "cbad ef" (if less than n characters, donot reverse)

5. Some probability based questions: 3 types of ball in bag with equal probability. Some of the atleast, atmax kind of questions. I am sure almost everyone has solved these type of questions in their undergrad.

6. Problem with Concurrent Reader, Exclusive Writer (CREW):
A writer may wait forever.
How to solve it?
Assign reader_priority = writer_priority = normal