• Status: Currently student at an IIT in India
• Date: August 2020
• It was an on-campus opportunity

Round 1 : Online Assessment Test

Description:

1. The test has 5 sections and duration is 2 hours 15 minutes. All sections are mandatory.
2. The Coding section has 2 programming questions and duration is 30 mins.
3. The Computer Science multiple choice section has 7 MCQs and duration is 20 mins.
4. The Quantitative Aptitude multiple choice section has 8 MCQs and duration is 25 mins.
5. Each MCQ earns you 5 marks for correct answer and -2 for incorrect answer.
6. The Advanced Programming section has 1 programming question and duration is 45 mins.
7. The Subjective section has 2 questions and duration is 15 mins.
8. Considering CGPA as a section, you need to clear cutoff in at least three sections to be eligible for shortlisting.
9. The cutoff for each section is normalized and depends on the school CGPA pattern and the specific test scoring pattern.

• I performed well in both the multiple choice sections, but was only able to solve one question in the coding section. The subjective section had 2 questions, one asking what inspires you to complete a project and one regarding a situation where one of my teammates is having problems while we are working on a project together.

• I am pretty sure that I cleared the cutoff in both the multiple choice sections but still not clear as to what was the 3rd section ( most likely the subjective section, definitely not CGPA).

Round 2 : Technical Interview 1

• After a brief introduction, the interviewer asked me to describe one of my projects. The discussion was more around what inspired me to do that project and the end result and practical application rather than its technical aspects. The dicussion lasted around 10-15 minutes and he was 'really impressed' (his words, not mine).

• Next he asked me to speak a little on data strcutures and algorithms, the ones i like, the ones i feel were most useful etc. Somewhere in the discussion i mentioned segment trees are really elegant and useful because many problems can be reduced to some form of range query and solved using a segment tree in O(log(n)) time. I gave the example of finding the lowest common ancestor of any two nodes in a binary tree. To which he replied with the following question:

1. Given k nodes in a binary tree, find their lca.

• I gave him the euler traversal approach, where we will store the height array based on the euler array in segment tree which would result O(n) preprocessing and O(log(n)) query for each lca.
• He didn't understand my approach at first so he asked to me implement the solution.

void dfs(int k,int d)
{	
	first_time[k]=timer;
	euler[timer++]=k;
	depth[k]=d;
	vis[k]=1;
	
	for(int i=0;i<adj[k].size();i++)
	{
		if(!vis[adj[k][i]])
		{
			dfs(adj[k][i],d+1);
			euler[timer++]=k;
		}
	}
}

• As soon as I wrote this code for euler traversal, he gave me an example of a binary tree and asked me explain the process by dry running this code, so I filled the euler, depth and first_time arrays and he was very satisfied with my explanation.

• Next I explained how I would fill the segment tree so that each node (of segment tree) tells me the node (of given binary tree) with the minimum depth in the represented segment.

• After filling the segment tree, each query of lca (of a and b) would require me to just return the node with the minimum depth in the segment {first_time[a], first_time[b]}.

• Time complexity: O(n) preprocessing, O(log(n)) query.

• The interviewer was really impressed by this approach. But to my surprise, he asked me to optimize this solution a little more (I wasn't expecting he would ask me to optimize a solution which was alreading making use of segment tree). So I said if we store the segments in a sparse table instead of a segment tree, it would be a trade off between preprocessing time and query time reulting in:

• Time Complexity: O(nlog(n)) preprocessing, O(1) query.

• You would think this would be the end of discussion on this problem but no, he asked me to optimize the solution a little more. I don't know how to optimize a O(1) query so I presented him with the following solution.

• Join your hands and say the following prayer: "Oh lord, here are k nodes of a binary tree, return their lca ASAP!"

Round 3 : Technical Interview 2

• This round also started with 10-15 minutes of discussion on the same project, few minutes covering how it was working and rest of the discussion was same as last time.

• Next he asked me the following questions

1. Given a number, find out the next smallest number formed by the same digits, greater than the original number (next permutation).
   I proposed a solution using a queue, pushing digits starting from the unit position and going backwards until the next digit is smaller than previously pushed element at which point concatenate the last digit in queue, insert the currrent digit in the queue and concatenate the digits starting from
   front of queue.

2. Given the schedule of a train station (the arrival and departure time of several trains), find the minimum number of platforms required at the station.
   I propsed a O(nlog(n)) solution using 2 pointers after sorting the trains according to their arrival times. He asked me to make use of some data structure, so I proposed a very similar solution using a double queue.

Finally, received the offer !