microsoftinterviewalgorithmsdata-structuressystem-designsecuritylinked-listcoding-interview

Microsoft Interview Questions

Hi all!

I recently attended an interview at Microsoft IDC. I have done my best to recollect most of the interview questions. Hope they help

Round 1: Written Test

Time: 75 Minutes

Question 1:

Define a macro that takes the structure name and member name & returns the offset of the member. One must not create any instance of the struct.

Struct T
{
    int a;
    double b;
    int c;
}

Example:

assume int size as 4 and double as 8

OFFSET(T,a) gives 0 OFFSET(T,b) gives 4 OFFSET(T,c) gives 12

Question 2:

Find the bugs in the following program which tries to delete a node from a singly linked list. Correct the bugs (logical) and optimize the program as much as possible.

struct _NODE
{
    _NODE *next;
}

void deletenode(_NODE *head,_NODE n)
{
    _NODE *prev,*curr;
    prev=head;
    curr=head;
    while(curr)
    {
        if(curr==n)
        {
            delete curr;
            prev->next=curr->next;
        }
        prev=curr;
        curr=curr->next;
    }
}

Question 3:

An array A contains a series of n numbers both positive and negative. Write a program to find the set of contiguous numbers that give the maximum sum. Also print the lowest and highest index of the series.

Example:

For the array: -1 -2 4 7 -3 1, the Maximal sum is 11: from 2 to 3

  • Write solid code and optimize it.
  • Complexity must be O(n^2)

Question 4:

Assume a scenario where a company has several data centers at different places in India like Hyderabad Pune etc. It has its main server at some place. Now when file is requested following operation:

  1. Client from Pune requests a file from the main server
  2. Server verifies the client
  3. Main server then forwards the file to the local server.
  4. Next time when a file is requested from Pune the request is forwarded to the local pune server and client is served from there.
  • Write the test cases for it (as much as you can. Anything above 25 will do)
  • Analyze the situation and identify all possible breakdown conditions
  • How do you rectify the breakdowns?
  • How do you carry out authentication?
  • Algorithamize your solutions and optimize the same.

Example:

If the local pune server fails the main server must be able to acknowledge the failure and must be able to serve the user seamlessly without any interruptions

Question 5:

Assume that you want to port your favorite mobile application to a mobile platform. What all features would you include? Tell about the various scenarios possible and the different models that can be used. Draw a screen shot and flow diagram for all possible scenarios that you could come up with. Optimize all solutions.

Technical Interviews

The Technical interviews lasted for around 2 hours each and the questions were fired by developing on the answers of the preceding questions. I've pulled as much as I could from my memory.

For almost all of the questions, I was asked to write code and optimize it.

ROUND 2: INTERVIEW 1: Technical

  • Write solid secure code to generate the power set of a given set of elements:

Eg: If input A={1,2,3}, result= {(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3),(NULL)}

  • Write a linear time algorithm to find all combinations of given sets.

Eg: If input = {1,2} ,{3,4} and {5,6},

Output: {{1 3 5},{2 3 5},{1 4 5 },{2 4 5},{1 3 6},{2 3 6},{1 4 6},{2 4 6}}

Optimize the algorithm to the maximum possible extent. Prove mathematically that it is optimal.

  • How do you create a random number generator? (Note: Not Pseudorandom numbers)

  • If you are asked to design the next version of Bing, say Bing 2.0, how do you start?

    • What are the features that will be added/modified/removed
    • How can you make it better than the other search engines
    • How do you implement spell check in a search engine: eg: If you search "Maximm", the search engine shows "Did you mean Maximum?". How do you implement this feature? How can you use the feature for proper nouns?
    • The Interviewer then started digging deep down with questions on the nuts and bolts of the data structures and data-statistics tools that are used for search engine design. (This took a looong time :) )
    • How will you design a spell checker for MS Word? How is it different from that of Bing? Write Code
    • Write a program to delete the nth node from a doubly linked list. Optimize it and verify optimization mathematically.

ROUND 3: INTERVIEW 2: Technical

  • Merge two linked lists. Write as many test cases as possible (Preferably around 20)
  • Analyze the logic patterns of inputs in the merging problem. How can we take advantage of the patterns?
  • Which is your most favorite project? Explain.Code.Optimize.
    • Write Test cases based on it.
    • The Interviewer started with Operating System concepts and started chaining an answer to the successive questions. It went on for a while: DeadLocks->Algorithms for DeadLock prevention(WriteCode)->Operating System security->Security domains->Semaphores(WriteCode)->InterProcess Communication->ProducerConsumer Problem(WriteCode)->Syncronization problem(WriteCode)->Testing methods

ROUND 4: INTERVIEW 3: Technical

  • How do you setup a networking infrastructure (hardware) which incorporates multiple servers, all offering different services, like email, business processing, etc. such that ,if the clients can use just 1 login- info to access a multitude of services.

  • Write test cases

  • How to solve Synchronization problem(Write code )

  • What are the Error recovery mechanisms

  • Swap the even-Odd positions in a doubly linked list. Swap the nodes, not just the values in them.

  • I design a program called "copy.exe" which accepts 2 command line arguments 'source' and 'destination'. What are the test cases that are to be considered? Analyze the situation completely.

ROUND 5: INTERVIEW 4: Technical

He asked me what my area of interest is, to which I replies 'Information Security'. The following 2 hours were completely about info-security.

  • How to encrypt a message that is to be sent from A to B, when B doesn't know the key. The Messenger carries the message from A to B. He can travel from A to B and back to A. He carries only the message and not the key. Find a scheme to make sure that the messenger won't be able to read the msg that he carries, and that the msg reaches its destination safely.

  • Debug the following: He gave me sheets with codes printed on them and asked me to debug the same. After debugging all errors, I was asked to code a fair copy of the same.

    • Reversing a linked list
    • Inserting a node into a linked list
    • Sorting a doubly linked list

  • Write a program to delete a node from a linked list

  • Optimize the programs that you write.

  • How to use chaos theory in encrypting messages: Faigenbaum Numbers, U-Sequence, Deterministic unpredictability, White noise.

The Interview was an amazing experience. It was of a kind that I've never experienced before. The Questions were so different that we lost track of time.

Thanks for your time,

Vignesh Murugesan, Amrita School of Engineering.

My Twitter ID: http://twitter.com/vignesh_wiz

Facebook Page: http://facebook.com/vignesh.murugesan.me