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
When number of readers exceeds a threshold, --reader_priority
When writer writes and if reader_priority < normal, ++reader_priority

If reader_priority < norm, and if a reader comes, it will wait if there is writer waiting in the queue.

My suggestions:
Be confident. Revise Data Structures and Algorithms. Write few programs for practice.
Also talk to interviewer, clarify assumptions and state your algorithm before starting to write on the white board. Always check for boundary conditions (this is where most candidates get filtered).