MICROSOFT 2006

---------------------------- Original Message ----------------------------
Subject: Microsoft Test and Interview .... (fwd)
From: "Pemmaraju Rama Krishna;04410118;"
Date: Fri, May 19, 2006 12:51 am
To: "K NARENDRA;05410127"
--------------------------------------------------------------------------
REAL HAPPINESS LIES IN MAKING OTHERS HAPPY
P.RAMA KRISHNA,
ROOM NO:009,
SIANG HOSTEL,
IIT GUWAHATI,
GUWAHATI-781039,
ASSAM.
Ph no : 09954211409

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
LEARN FROM UR EXPERIENCES
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
---------- Forwarded message ----------
Date: Sun, 18 Dec 2005 20:06:39 +0530 (IST)
From: "M Thirumala Reddy;04410114;"
To: cse04m@iitg.ernet.in
Subject: Microsoft Test and Interview ....


hi friends,
this was the paper asked by MS at NIT Warangal
recently. they took 6 guys frm there.

all the best.

Paper :

To start with, we had a written test for 1 and a half
hours.
Round 1 : Written Test
In total there were 6 questions:1st three of 4 marks &
next 3 for 6
marks.
1) Output was to be given for a program which
had a
recursive
function..simple one....well there was a catch as (int
i = 96573) was given.
We must know the size of the integer on the machine &
then answer
accordingly.
2) An incorrect program was given. We had to
find the
bugs.......there
were four bugs....the most important one was: a
locally defined char
array was being returned....which is not allowed....
3)There is an array A(MXN).......it is rotated
clockwise and then
shifted row-wise with wrap-around to get the array
B(NXM)......an example
was shown.....we have to just give a formula in one
line for A[i][j] =
B[......][.......]. Assume that the boundaries of an
array are from 0 to
M-1 as usual. Frankly speaking I got stuck in this
formula after
completing the 1st 2 ques in 15 min....but finally it
was a very cool
answer... [(j+1)%N][(i+1)%M]...
4)You are given a linked list of numbers:
1-6-3-9-7-54. U will be
given an input - 'n'. You have to insert 0 after every
nth element in the
list. For example if n=2, then o/p:
1-6-0-3-9-0-7-54-0. U must give the
best complexity algo to get thro'
5)Write the various test cases for Q4. How does
ur
program handle
them? I gave abt 5 test cases (obviously meaningful)..
6)There is a document containing words. A fn
'getNextWord' returns
next word in the document, u have to count the number
of occurences of
each word in the document.
a)What data structure will u choose ?
b)Write the algorithm to buid the database,i.e
the
complete account of
the frequency of each word?
c)What is the time complexity of your algorithm?

We had abt 63 ppl sitting for the test..24 got
shortlisted..
Round 2( by Padmapriya):
Now, we were divided into 3 groups of 8 each. There
were 3
interviewers. Each was assigned a group. 3 questions
were shown on the projector
one by one. I suppose we were given ample time to
solve each of them. We
had to solve them and the interviewer assigned to the
grp talked with
us...basically an interview.
1) 3 buckets. 1 contains apples, 1 contains
oranges,
1 contains apples
& oranges. All are wrongly labelled. U r allowed to
pick 1 fruit from 1
basket. What will u do to identify all the baskets
correctly.
2)There is an array containing R, G, B. Write a
program to get all the
R's, G's & B's together. For example: i/p:
RGBBBGGRRGB;;;;;o/p:
RRRBBBBGGGG....it was a simple one....but frnds u need
to go for just 1 pass &
use least space to earn points.
3)U r given two sorted arrays:----A & B. B
contains
enough extra
spaces at the end to store all the elements of A.
Merge A with B...without
removing duplicates.
for ex: A: 1 3 5 7 ;;; B: 4 5 8 X X X X ;;; X stands
for empty space.
o/p: B: 1 3 4 5 5 7 8 ;;;;;
Frnds u hv to give the best algo here too..........
Test cases were asked for every algo.

Out of 24, 14 went thro this round.....

Round 3(Tech Interview by Govind):
Asked abt the Round 2 solutions....then gave 2
questions:
1) Write a fn: deletenth(node *l, int n). This
function deletes every
nth element in the list...A simple one(he told
me)...just allowed 1
pass.... Govind told me to check the code and then
only show it to
him...he wanted error-free, damn best, fast written
algo. I gave him the
best....got impressed...
2)Write a class bit....It contains two
functions:
bool getBit(int n),
setBit(int n). The constructor is passed an integer n
that specifies
the number of bits to be handled.....setBit fn sets
the nth bit while
getBit fn returns the nth bit. Hint: Dont use an
element array to store
the bits...in fact use all the bits of the data type.

Round 4(Tech Interview by Niranjan Naik):
He asked abt the projects,favourite subject(mine is
OS)....if it is not
still he will anyhow ask ques on os....this part of
the interview was
basically tp. He posed just one ques:
1)There is a sorted array A. Now the elements in
the
array are shifted
(wrap-around) by 'n' positions to get the modified
array B. Write a
program which takes as input the modified array B and
outputs 'n'. ex: A:
1 3 5 7 9 11 14
B: 11 14 1 3 5 7 9
n = 2
I gave him 1 pass O(log n) algo. You have to
take
care that it
considers ALL the possible test cases.

I cleared just these many rounds to get hired. Some of
my clasmates had
to go thro' one more interview by govinda before being
hired.
In total 6 were hired.

Some of the ques asked to others:
1)There is a linked list containing nodes
that hv an
extra pointer
other than 'next' which points to any other node in
the list. You hv to
make a copy of such a list.
2)Remove duplicates from a list.

Well I beleive this is enough to give an overview of
the selection
process of MS.
My tips
Simple problems will be given and you must give the
best, error-free
solutions in terms of time complexity & space
complexity.
Best Of Luck.
--
Yours Friendly,
Thirumal.
Narendra.K
1st year M.Tech(CSE)
IIT Guwahati