Name of Company: Microsoft

Year: 2012

Profile: Software

Website link of company: http://www.microsoft.com/

Venue: On Campus

CTC: 15-16.5 LPA

Total number of students appeared for written: 200+

Number of students shortlisted for interview: 30

Number of offers: 7

Written:

Round 1: 50 questions in 60 minutes

Section 1: Quantitative and aptitude questions (Level:  easy 30 questions)

Section 2: C/C++ basic coding questions (Level: Easy 20 questions)

Round 2: 3 Coding question in 60 minutes {No compiler, On a notepad}

                Q1: Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc).

                Q2:  Write a program to convert binary search tree to double linked list

                Q3: Write a program to sort a linked list consisting of only 3 distinct elements.

Interview Question (All the design questions except first: Program manager post)

Round 1:

Q1: How to sort a array consisting of only 3 distinct elements efficiently? (Don’t use counting method)

Q2: You are given a sheet of paper of dimensions w*h. You have to fit photographs (Dimensions: m*n) in that sheet such that each photograph is separated from other photograph or boundary of paper by “d” distance from all the sides. You have to output the maximum number of photograph you can fit in the sheet. The arrangement should be symmetrical from centre.

Round 2:

Q1: Tell something about yourself

Q2: How you will design alarm clock for a blind person?

Round 3:

Q1: Description of various projects

Q2: You have to stream songs of radio station of a particular area through your applications so that you can hear it anywhere: Design and implementation details.  Questions like:

- How will user fast-forward the song?(He can’t because it is radio ;))

- How you will provide music storage service to user? What will happen when he will click fast-forward and reverse button?

- How to make sure that speed is maintained?

Round 4:

Q1: Design a banking application for SBI which users (especially students) can use in their smart-phones for daily transactions, take the history of transactions, pay their fees etc.

-          What main features must be included in the app?

-          How will user interface look like?

-          How will transactions take place?

TIPS:

1)      For Round 1 of written all that matter is speed and accuracy.

2)      For Round 2 of written: Coding Questions are pretty easy just try practicing your coding skills on paper/ notepad instead of using a compiler. You will be surprised as you will find it is more difficult than expected.

3)      When interviewer asks you a question you already know, Take your time and make sure you solve the question all over again. Start with the basic algorithm and then keep improving till the interviewer is satisfied.

4)      In Microsoft recruitment there is no separate round as HR. You can be asked any HR question in any of the interview round. When you are asked to describe about yourself, Make sure you don’t hurry. While telling about yourself, try to sense the interest of interviewer. If interviewer looks interested in a particular project of yours and you are confident about it, make sure you elaborate the topic giving him chance to ask questions.

5)      There are no books which can help you master the design questions. All you need is innovation and confidence. Take care of following points :

-          When asked to design something, Take paper and write down all that comes in your mind so that you don’t miss any point. Take your time and don’t panic at this point.

-          Read your thoughts aloud to the interviewer. In design questions nothing is wrong or right so make sure you say everything in your mind to the interviewer, you never know which point may impress him.

-          Try to sense the interest of interviewer. In my interview round I was asked to design alarm clock, I put out all the technical details but he asked me how I know it is the right thing to do. I understood he wants me to talk about customer involvement.

6)      At end of each interview round, Interviewer asks you if you have any questions. Make sure after you ask interviewer about 2 things :

-          Something about their company. While asking the question try to reflect that you feel you will be selected.  When you ask question make sure you listen what he reply. Depending on interviewer you can also ask him his experience in that company.   While asking questions don’t show that you are asking because you have a doubt if you will join the company or not instead show you will be selected so you are eager to know more about company.

-          Feedback about yourself. This will enable you to know about your weaknesses and improve it further because each interview is preparation for the next. It also shows the interviewer that you ready to take feedback and improve. It will push your chances to get selected.

                

Round 1

1. BST to DLL conversion.

2. Given a linked list you have to delete all nodes for which there is a node with higher value on right side.

for eg. 41 1 6 4 8 34 3 5 9

output  41 34 9

n^2 solution is obvious. Do this in O(n)

Round 2

I forgot questions from this round. 1 question I remember is

1. You are given with an iPod. There is a sequence of n songs and a function rand(int i) which upon calling returns an integer from 0 to n-1 (or 1 to n, depends on you). You have to write a function so that it will play random songs every time. After finishing one song you have to play another song randomly. The constraint is you cant repeat a song until every song has been played.

Round 3

1. Normal HR questions

2. There are 2 persons jumping from the parachute on a infinite 1 dimensional plane. Upon landing they go to a random direction. We have to write a code using a given API which will run on different system, independent to each other so that they cant communication by any mean. The given API contains

moveLeft - moves the person 1 unit left/1 unit time

moveRight - moves the person 1 unit right/1 unit time

noOpt - moves the person 0 unit/1 unit time

isOnTop - returns true if the person is on top of any parachute. False otherwise.

didWeMeet - returns true if they meet. False otherwise.

Written Round (1 hour 30 minutes):

20 MCQs (mostly from latest GATE paper)

2 Programming questions:

1) An operation "swap" means removing an element from the array and appending it at the back of the same array. Find the minimum number of "swaps" needed to sort that array.
Eg 3124
output: 2 (3124->1243->1234)

2) find if there exists a path from root to leaf in binary tree with sum K.



Interview:

Round 1 (1 hour 15 minutes):


write programs on paper keeping in mind all the boundary cases and complexity of the code. Following were  the programs:

1) Find if the given linked list is a palindrome or not (including inplace reversal of linked list)

2) We have a right rotated sorted array.Eg
   4  5  1  2  3
You need to find where this rotation had occured.

3) There exists a linked list such that each node has two pointers next and random. Random pointers points to any other node in the same linked list or to 
itself or NULL. Clone this linked list.


Round 2 (1 hour 15 minutes):

First part was mainly concerned with questions related to OOPs, second part included OS and lastly algorithms and miscellaneous.

OOPs

1) interviewer turned the laptop towards me and then asked me to write an "interface" for this laptop. Then he asked me to implement this interface.
2) Event handler. Asked how will you tell whether a key on the laptop has been pressed or not. Write a function (whose signature I had written in interface).
3) Difference between interface, abstract class, instance.

OS

He asked me back to back questions which covered topics:
1) Processes and threads (Asked example, desing a software which will be having three components-file copy, data transfer, user input efficiently)
2) Multi-threading
3) Scheduling Algorithms (both Process and thread)
4) Synchronization (many questions from mutex and semaphore)
5) Deadlock (deadlock prevention, avoidance, etc)
6) context switching

Algo and misc

1) Scenario: In gmail if somebody wants to sort mails according to name, date, size, etc which sorting algorithm is most accurate one for this puropse.
2) quicksort and heapsort.
3) what are shared library.
4) Other type of libraries.


Round 3 (1 hour):

Write the programs for following:
1) COunt the total number of parenthesis pattern for a given number n. 
Eg 
n=1
()
count=1
n=2
()() (())
count=2
n=3
()()() ()(()) (())() ((())) (()())
count=3

2) If the given graph is bipartite or not.
3) (not code only ds) Scenario: There is a huge database of telephone numbers. Each telephone number is unique and information (name, address, etc) of the user is attached to this telephone number. Design a data structure to store this.

Round 4 (1 hour):

HR plus techincal
1) Tell me about yourself.
2) What is your educational background.
3) Why Amazon

tech:
1) delete nth element from the end in a linked list.
2) find the maximum sum subarray in an array A of size n which may also contain negative numbers.

Selected!

Whenever u write a program be sure to cover all the corner cases and write it in a proper indented way. As interviewers ask to write testcases for the program u have written and then check if ur program covers all the test cases.

All the best fellas !!!

Written Round 1 :  50 multiple choice questions in 60 mins time. Had 2 sections – Aptitude and

Programming Ability.

Written Round 2 : 3 coding questions in 1 hour.

1.   Swap every consecutive odd and even positioned bit in a number.

Ex:- 10101011010101 =  01010111101010

2.   Given a binary search tree . Convert it into a doubly linked list in place (no extra space) such that prev points to left child and next points to right child.

3.   Given a linked list that contains 0,1 and 2 . Sort this linked such that it contains 0s first,then

1s and then 2s in O(n) time.

Ex:- 2->2->1->0->0->2->1->1->0 = 0->0->0->1->1->1-2->2->2

PI round 1 (Technical):

1.   About urself, most challenging project of all you have done and about ur internship.

2.   Remove from string s1, all the characters that are present in string s2.

S1=”abcde” s2=”xyazbx”   Ans. S1= ”cde”

3.   Reverse alternate k nodes in an linked list.

Ex:- 1->2->3->4->5->6->7->8  if k=2; then return 2->1->3->4->6->5->7->8

4.   Always ask some questions to the interviewer at the end. That’s a good gesture.

5.   Write test cases for the programs above and see if ur program covers all the test cases or not.

PI round 2 (Program manager)

1.   Design a tic-tac-toe game for multiplayer on a smartphone.

2.   Design a vending machine for blind and deaf.

PI round 3 (Technical)

1.   Add numbers from 1 to n2  into a n X n matrix spirally.

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

2.   Remove duplicates from a string in place.

Ex-microsoft -> microsft

3.   Some question on recursive functions using memorization technique for optimization.

PI round 4 (Testing)

1.   Given a func ::    int *strcmp(char *s1,char *s2);

Write test cases to check functionality and security issues and even automate the generation of test cases.

2.   Given a func ::    int typeOfTriangle(int side1,int side2,int side3); (func gives a number for the type of triangle)

Write test cases to check functionality and security issues and even automate the generation of test cases.

3.   WAP to reverse words in a sentence.

I am a good boy -> boy good a am i

4.   WAP to get the next higher palindrome of a given number.

123 -> 131                1232 -> 1331

PS -  Functional issues are test cases that check the functionality of the program and Security issues are the ones where the program may crash.

PI round 5 (Technical)

1.   WAP to check if a binary tree is a BST or not.

2.   WAP to find Least Common Ancestor of two nodes in a BST.

3.   Reverse every two nodes in a linked iteratively and recursively.