Interview Round 1:

Here I had to implement a sorted 2-D linked list. The first node of the linked list is connected to another linked list, and it continues this way. Each row (a single linked list) can have at most 5 nodes, and the keys stored in the linked list are in sorted order. Along with the representation, I had to write the add and delete functions for this linked list. (Note: No pseudo-code was allowed; proper code had to be written).

Finally, the interviewer asked me how to test the code, specifically requesting different test cases to cover the entire code and its boundary cases.

Interview Round 2:

1. In an image, clouds are scattered all over. Let's say the clouds are white, and the rest of the image has different colors. The problem was to count the number of such clouds. (Assume the image is given in a 2D matrix format).
2. Given an array, find all sub-arrays that have a sum of zero. (Note: an N log N solution was required). A continuation of the above question was to find all sub-arrays with a sum less than a small number, let's say 1.

Interview Round 3:

In this round, I was asked about my projects, BTP (Best Thesis Project), and interests. I also had to answer questions like, 'Why Microsoft?' or 'What do you like about it?' etc.

After that, the interviewer asked a few aptitude-type questions:

1. Given two dice, how would you represent all the days of a month?
2. How would you design an automated traffic-signal system?
3. What measures would you devise to allow credit cards for children?

Here, I had to implement a sorted 2-D linked list. The first node of the linked list is connected to another linked list, and it continues this way. Each row, i.e., a single linked list, can have at most 5 nodes, and the keys stored in the linked list are in sorted order.

Along with the representation, I had to write the add and delete functions for this linked list (proper code, no pseudocode allowed).

Finally, I was asked how to test the code, which essentially meant providing different test cases to cover the entire code and its boundary cases.