Company : Microsoft

Off campus drive

First Online Round : 20 – 30 MCQs

Second Online Round : 2 coding questions

a) Given a matrix of dimension m*n where each cell in the matrix can have values 0, 1 or 2 which

has the following meaning:

0: Empty cell

1: Cells have fresh oranges

2: Cells have rotten oranges

So we have to determine what is the minimum time required so that all the oranges become

rotten. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1],

[i,j+1] (up, down, left and right). If it is impossible to rot every orange then simply return -1.

Soln : http://www.geeksforgeeks.org/minimum-time-required-so-that-all-oranges-become-rotten/

b) Distance between two nodes in a binary tree

Soln : http://www.geeksforgeeks.org/find-distance-two-given-nodes/

After coding round, 10 students were called for onsite interviews. Students from other colleges were

also called for further rounds.

Group Fly 1 :

a) Convert number to words.

Test case 1 :

Input : 32

Output Thirty Two

Input : 1110

Output : One thousand one hundred and ten

b) Reverse a linked list.

c) Given a cube of side length n, consisting of 111 cube. The outer side is painted black. What is

the volume of the cube having no side painted black.

Ans : (n-2)^3

Group Fly 2 :

a) Given an array. Segregate elements such that all even numbers comes first in increasing order

and then odd numbers in decreasing oder in place.

Input = {12, 34, 45, 9, 8, 91, 3}

Output = {8, 12, 34, 91, 45, 3}

You can't use standard sort i.e. inbuild sort function

Soln : http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/

b) Given a BST, find LCA of two node. The links of BST are reversed i.e children pointing to the

parents. You are expected to solve it in single traversal.

Hint : Use property of BST.

Interview :

1. Tell me about your projects at Flipkart.

2. What was the most challenging part in your project.

3. Design a autocomplete feature. Suppose, you start typing a word, you need to give top 3

suggestions for the word according to frequency of words used.

I gave a solution using heap, trie and hashmap

4. Given an array of linked list. Each index stores a linkedlist which consists of nodes having single

character of a word and points to next character. Sort the array of linked list

Eg. Considering an array of 3 linked list

Input :

0-> 'c'->'o'->'m'

1->'a' -> 'b' -> 'c'

2-> 'a' -> 'd'

Ouput :

0 -> 'a' -> 'b' -> 'c'

1 -> 'a' -> 'd'

2 -> 'c'->'o'->'m'

5. Write down the system calls for soceket programming.

6. Design WhatsApp. So given multiple servers and clients, how would client and server

communicate. Concepts of threading requests from client and response from server.

7. Questions on threads and process. Multi threading concepts.

8. Questions on memory and disk storage.

9. What is semaphore? Expain the internal working of semaphore.

10. What is GPU? Explain the internal working of GPU

11. How does malloc() and free() works.

12. How would you implement strstr() function. Write the code of KMP .

http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/

13. Do you want to ask something.

Always ask something.