Microsoft visits our college annually to recruit students for three positions:

• IDC (India Development Centre, Developer)
• IT (Tester)
• SMSG (Sales & Marketing Services Group)

IDC & IT Selection Process

First Round: Online Test Administered by aspiringminds.in, this round consisted of:

• 24 aptitude questions
• 24 C/C++ questions
• 24 logical thinking questions

A shortlist appeared the same day, with 20 students selected for IDC, 20 for IT, and approximately 20 qualifying for both.

Second Round: Coding

• IDC: 3 questions in 65 minutes, focusing on string handling, rotating a matrix 90 degrees, and converting a Doubly Linked List to a Binary Tree. These questions were straightforward and can be found in the "Cracking The Coding Interview" (CTCI) book.
• IT: 4 questions in 65 minutes. The first two were coding challenges: string reversal in place and one other question that is not recalled. The remaining questions involved detecting if a structure is a binary tree and devising test scenarios for an airport.

Interviews A shortlist for the interview rounds appeared two weeks after Microsoft's initial visit.

I underwent three technical interview rounds. Some candidates had one written round followed by three technical rounds.

Round 1: The interviewer asked about my resume details and the work done during my industrial training, requesting a brief description. We discussed the "common ancestor problem," for which solutions are available in CTCI. I knew the answer but initially struggled slightly to arrive at the final solution.

Round 2: Problem: You have 'n' cities arranged in a circle, each with a gas station providing a certain amount of gas. The distances between consecutive cities are also provided. Assuming a mileage of 1 unit of petrol covering 1 unit of distance:

i) Determine if it is possible to complete the entire circle of cities. ii) If possible, identify the optimal starting city.

Task: Code and test the solution.

Answer: Consider two arrays, G[] (gas) and D[] (distances).

i) If the sum of G[] is greater than or equal to the sum of D[], the circle is possible. ii) Find the difference between corresponding elements of G[] and D[]. Then, identify a starting point such that the cumulative sum of these differences remains non-negative throughout the entire circle.

Round 3: Implement binary search on a sorted array that has been rotated (e.g., 5 6 1 2 3 4). This is another problem that can be found in CTCI.

Round 2

You have n cities in a circle, each with one gas station providing a certain amount of gas. You are also given the distances between each pair of consecutive cities. Assume mileage: 1 unit of petrol covers 1 unit of distance.

i) Find if it is possible to travel through the entire circle of cities with the given distances. ii) If so, determine where you should start.