They called approximately $80-90$ people for interview. For interview cut off follow this link: http://cse.iith.ac.in/?q=node/491

Date: July $11,\ 2017$. Venue: IIT H BUILDING, Room Number $318$.

We had a written test $(1 \ hour)$ as the first step. Following are the test questions :

1. Solve recurrence Relation $T(n) = T(n-1) + 2n, \ \ T(1) = 1$

2. Let $G(V,E)$ be a graph. Let $w(e_i)$ is the weight of edge i.e. $$w(e_1)<w(e_2)<w(e_3).........<w(e_n)$$.

Let T is MST of G. State given statements are true or false. Give counter example also.

a. $w(e_2) ∈ T$

b. $w(e_{max}) ∉ T$

3. A sorted array is given. Write efficient c code for searching an element. Also, find time complexity and correctness too.

No written based shortlisting. Everyone needs to attend the interview. There were four interview panels.

Interview Part :

Room no $311$.

Professor Antony and Professor Sakethnath (https://cse.iith.ac.in/?q=People/Faculty) were my interviewers.

Professor Antony: Introduce yourself.

Me: Answered.

Professor Antony: What was your answer regarding question $2b$? TRUE or FALSE?

Me: FALSE.

Professor Antony: can you prove this?

Me : (Took marker explained why it is false). My $1^{st}$ argument was if $G$ itself is a tree so $e_{max}$ must be in T.

$2^{nd}$ argument: Even if G is graph but not the tree and let there is a cut edge then irrespective of weight we need to select that edge in MST.

Professor Antony: can you prove your second argument?

Me: Explained everything with a diagram.

Professor Sakethnath: You are good at maths?

Me :

Professor Antony: There were $25$ teams, and we have $5$ processors. At any point in time, we can select 5 sides, and that will give a winner. So how many matches we need to find a winner?

Me: 6. I guess.

Professor Sakethnath: Guess or sure?

Me: Sure ☺

Professor Sakethnath: Let me modify this question. There were $16$ teams. A match between any two sides will give the winner. So how many games do we need to find a winner and second winner?

Me: can I explain it on board?

Professor Sakethnath: yes go ahead.

Me: Explained everything with the divide and conquer approach. Total matches will be $n+ logn -2$. Still, they weren't convinced.

Professor Sakethnath: can you explain again how you got $logn$ term?

Me: Question was the same as 'Finding max and second max element from an array of n elements.' Explained with divide and conquer approach. They were trying to trick me here and there, but I was confident. Finally, they agreed.

Yes, that gave me some confidence!!!

Professor Antony: You have two coins with head probability $p_1$ and $p_2$ respectively. Just select any one currency randomly and toss. What will be the probability of getting head if the previous attempt was also head ??

Me : (Took marker) Wrote the conditional probability formula. $P(A/B) = P(A∩B)/P(B)$. I forgot how to proceed further

Professor Sakethnath: Just tell me what will be the probability of getting a head?

Me: Answered.

Professor Sakethnath: Now tell me what will be the answer to the previous question?

Me: Again I wrote same formula

Professor Antony: You know the linked list?

Me: Yes.

Professor Sakethnath: A linked list with the head pointing to the first element is given. How will you implement the Queue with this linked list? I mean where should be insertion and from where you will delete?

Me : (After drawing linked list I thought if I delete at the end, it will take $O(n)$ time, but enqueue and dequeue operation in a queue must take constant time) Acted like I am thinking something.

Professor Sakethnath: Why are you taking so much time? Just tell us where should be insertion and from where you will delete?

Me: Insertion will be at the head that will take constant time but, deletion at the end will take $O(n)$ time. That's why I am thinking some other way such that delete operation should also take constant time.

Professor Antony: Who told you insertion-deletion will take constant time?

Me: Read it somewhere. (don't know where )

Professor Sakethnath: No, $O(n)$ is ok. Can you tell me what will be if I delete at the head and insert at the end?

Me: Still it will be a queue, but in this case, the insertion will take $O(n)$, but deletion will take constant time.

Professor Sakethnath: Can you tell me recursive $C$ code for checking two trees are equal or not?

Me: Sir, trees or Binary trees?

Professor Antony: Binary Tree.

Me: Wrote the whole algorithm. I asked to allocate memory dynamically. I did. I was also asked for termination condition, node structure, return type of malloc. I explained everything.

Professor Antony: Ok done.

Me: Sir any question from graph, tree, linked list?

Professor Antony : (smiled) You want some more questions?

Professor Sakethnath: No, you are done.

Me: Thank you.

Both professors were amiable. And this was my one of the best interview (obviously after BARC) of the year 2017. I enjoyed it.

Finally on July $13,\ 2017$. Got an e-mail from IIT H.

I would say that please do keep hope if you face a lot of failures. One day will be yours, and you will shine like a star.