Microsoft Placement paper 2012 IIT Guwahati
Written Test : It consists of two exams conducted by some
organization(not Microsoft).
Exam 1 : It consists of 20 questions mostly are from data
structure, graph theory, operating system, computer architecture, output
related questions. The time given was 45 minute.
Note : The exam was simple, you can easily able to pass it
out. This is just an eliminatory for second exam.
Exam 2 : It consists of two programming question. Total time
was 60 minutes.
Q 1 : A large passage was given to you, Write a program to
print last 10 lines ?. If the number of lines is less than 10, print all.
Q 2 : Print the binary tree level wise ?. For example if
input is :
A
/\
B C
/ \
C D
/\
E A
Output is :
A
B C
C D
E A
Interview
Round 1 :
Q 0 : Tell me about your self ?, Tell me your interest ?
Q 1 : When you visit on your friend’s Facebook profile,
there is a mutual friend section where common friends are listed, now let’s
assume that your friend do the same thing, he/she visit his/her friend other
then you, now the people other than common are connected to you by distance of
two. Similarly think you are given two people on Facebook, how do you find this
connectivity?. (Please give appropriate solution),
Now let’s think that some important people are given some
weight(any), now do the same thing ?
Now calculate the most influential person? (Not an easy
question, because of weights) ?
Q 2 : longest palindrome in a string ? (Need to tell in O(n)
time complexity + O(1) space complexity)
Q 3 : What do you think, how the posts in Facebook are
shown, to your page, as there are thousands of posts, likes, videos, images,
links etc. shared by your friends, but not all are shown to you ? (Data mining
question, have to tell appropriate solution which can work ?)
Q 4 : You have given a linked list in which each node have
three items, 1) data, 2) a next pointer and 3) a random pointer which is
pointing to its successor in sorted order. Replicate it ? (Need to generate a
new linked list in O(n) + O(n) complexity)
After some discussion I ask a question to the interviewers
Q : Sir, Why can’t window also have similar system
interaction as it is in Linux, for example they have given terminal, we also
have command prompt, but both have a lot of difference in terms of system
interaction ?
Round 2 :
Q 0 : What types of questions were asked in round 1 ?
Q 1 : You are the supervisor of an airport. What happens is
that visitors are not visit your airport, instead they go to another one, which
means your airport become unpopular nowadays, Now as a supervisor you need to find
out what has happens ?, What went wrong ?,How do you find out ?, What is
correct ?, How do you find correct one and at what cost ?
Note : All type of questions were discussed here, Hints for
this questions, you need to tell with
the concepts of data mining, you need to tell how we get information’s and at
what cost, then you need to analysis information’s.
Q 2 : You are given finitely many intervals in 1D, you have
to design a data structure an efficient data structure which can answer queries
of the form “In how many intervals the point P belong ?”, P is an input point,
and all intervals are closed. I answer B
tree(think why) which is most efficient.
Then he asked me how to decide how many children should be
there at a node ?, Design most efficient B-tree based upon information you have
?(need to think more about how to get information’s ) ?
Q 3 : you are given some nodes, and for each node a
probability is given which will tell its importance, you need to design an
efficient data structure such that the
expected search time as minimum as possible. (Hint : Use dynamic programming +
binary tree).
My question to interviewer :
Q : Sir, In searching, pages have some ranking number, then
are assigned some probability of their access, now as there are billions of
pages and every day around millions of queries comes, how would the system do
the job, what kind of data structure they use to handle the efficiency ?
Round 3 :
Q 1 : How are you ?
Q 2 : Do you want to go for MS or PHD ?
Q 3 : What type of branch is yours ?(actually my branch name
is mathematics and computing, and after 3 year Microsoft allowed our branch to
appear for placement, so they ask this question)
Q 4 : One question is from my project “Garbage cleaner
Robot” ?
Q 5 : You are given a binary search tree, and a value(data
item), you need to tell the left most right cousin in as minimum time and as
minimum space ?(need to minimize actual time complexity, he need minimum order
of complexity as well as number of node access should be minimum)
Q 6 : You are given a
ternary tree (a tree with 3 children at max with left, middle, right pointer at
each node), create a singly linked list from it without using extra space ?
