The cutoff for an interview call was 845, for GEN category.

Before the interview, there was a 45 minute test – it had 5 MCQs and two programming questions. The MCQs were:

- Identify the graph of sinx*log(|x|)
- If we select a number from the first 50 natural numbers, probability that x + 96/x > 50.
- 6 distinghuishable balls, 3 boys, make sure each boy has at least one ball. No. of ways?

and two more simple linear algebra questions.

The programming questions were – traverse a matrix in spiral order, traverse a matrix and find out frequency of odd and even elements.

Now, my preferences in the dept were CSL, MARS and DREAM lab, in that order.

My panel had three people – Prof Satish, Prof Yogesh and Prof Lakshmi and the interview began:

Panel: So tell me what do you mean by a sparse matrix?

Me: Told.

Panel: Okay, how will you store a sparse matrix?

Me: [I was pretty blank and discussed for a few minutes before giving up]

Panel: Okay tell me, which is a better way of representing a graph – matrix or list?

Me: It depends on what are the operations that you want to perform on the graph. For something like a BFS, a list is better.

Panel: Explain BFS’s time complexity in both list and graph.

Me: [Done]

Panel: Okay, suppose I am given a set of vertices and I want to check if it forms a path, which would be better?

Me: We could use a BFS to find the path between the vertices.

Panel: No no, we are given the list of vertices, we need to check if it forms a path or not.

Me: A matrix would be better, since we can look up if an edge exists in constant time or not.

Panel: Okay, if I give you p vertices, what would be the time complexity?

Me: We’ll have p queries, each of O(1) time, making it O(p).

Panel: Okay good. How would it work out for a list?

Me: If the lists are sorted, we can find if a neighbour exists or not in logp [I think it was incorrect – binary search cannot be applied on a linked list, but he didn’t seem to mind for some reason], so overall can be done in plogp.

Panel: Okay, if it’s not sorted then?

Me: In the worst case, we might have to traverse till the end of the list.

Panel: If I give you the average degree of a vertex is d, then?

Me: On average, the time complexity would be O(dp)

Panel: Okay, we’ll switch to OS now. What do you know in that?

Me: Virtual memory, synchronisation etc.

Then the ma’am asked very basic questions on virtual memory – what is virtual memory, why do we need it, how does an address translation work, who does it, how are the bits divided, what happens on a context switch, where is the page table base address stored, how does multilevel paging work, what is the advantage of multilevel paging and so on. Overall, quite basic questions.

Next they moved on to synchronisation – the prof asked me to solve readers-writers problem. I was given a Google Doc where I wrote code. The prof then asked a minor variation – suppose we only want to let x amount of readers enter into the CS, how would you do it? This lead to a discussion on counting semaphore, locks, how locks are implemented using TestAndSet, granularity of locks, efficient lock usage and that was it.

In the end, they asked me if I had a MTech offer, to which I said I do, but I am interested in research programmes and it’s only a backup. Then they said why not apply for a PhD and I said I am not sure right now, but would convert from MTech to PhD if I like it.

That’s all, lasted around 45 minutes on Microsoft Teams.

Verdict: They had received around 2500 applicants, they selected 17 PhD and 7 MTech in the shortlist. Don’t know how many will get converted to final offers.

For this question, it is possible that she was talking about a Path graph.

In that case, it would be quite an interesting question. :) We just have to check if there are exactly $2$ vertices of degree $1$, all others have degree $2$, and the graph is connected. This can be done in $O(V)$ time because if it has more than $V$ edges then we know that it can't be a PATH graph.